「最优化」共轭方向法

从计算效率上来看，共轭方向法位于最速下降法和牛顿法之间。 共轭方向法具体有以下特性：

1. 对n维二次型问题，能够在n步之内得到结果
2. 作为共轭方向法的典型代表，共轭梯度法不需要计算很森矩阵
3. 不需要存储 $n \times n$ 的矩阵，也不需要对其进行求逆

共轭的定义

对于一个n次二次型函数 $f(x)=\frac{1}{2}x^TQx - x^T b,x \in R^n,Q=Q^T >0$ ，最好的搜索方向为Q的共轭方向，如果 $R^n$ 中的两个方向 $d^1$ 和 $d^2$ 满足 $d^{(1)T}Qd^{(2)}=0$ ，则他们是关于Q共轭的。

可以证明共轭的方向都是线性无关的，Q>0时，若存在一组标量 $\alpha_0,\alpha_2,...,\alpha_k$ 使得：

$\alpha_0 d^0 + \alpha_1 d^1 + ...+ \alpha_k a^k = 0$

通过将上式两边同乘 $d^jQ$ 可以得到 $\alpha_j$ 为0，得证。

基本的共轭方向算法

既然有「基本」两个字，说明这个方法适用的范围非常小。接下来介绍的时候都是针对目标函数为二次型函数。

$f(x)=\frac{1}{2}x^TQx-x^Tb$

算法迭代流程

给定初始点 $x^0$ 和一组关于Q共轭的方向 $d^0,d^1,...,d^{n-1}$ ，迭代公式为：

$g^k=f'(x^k)=Qx^k-b$

$\alpha_k=-\frac{g^{(k)T} d^{(k)}}{d^{(k)T}Qd^{(k)}}$

$x^{k+1}=x^k + \alpha_k d^k$

算法性能

对于任意的初始点 $x^0$ ，基本的共轭方向法都可以在n步之内收敛到全局的唯一极小点 $x^*$ ，即 $x^{n} = x^*$ 。

假设已经得到极小点 $x^*$ ，因为n个共轭方向线性无关，所以一定可以使用n个「共轭方向」表示极值点：

$x^*=x^0+\beta_0 d^0 + \beta_1 d^1+ ... + \beta_{n-1} d^{n-1}$

上式将 $x^0$ 移到左边，并两边同乘 $d^{(k)T}Q$ ：

$d^{(k)T}Q(x^* - x^0) =d^{(k)T}Q(\beta_0 d^0 + \beta_1 d^1+ ... + \beta_{n-1} d^{n-1})$

可以解得：

$\beta_k = \frac{d^{(k)T}Q(x^*-x^0)}{d^{(k)T}Qd^{(k)}}$

迭代点 $x^k$ 可以表示为：

$x^k=x^0 + \alpha_0 d^0 + \alpha_1 d^1+...+\alpha_{k-1} d^{k-1}$

由于目标函数是二次型函数，所以 $g^k=Qx^k-b, Qx^*=b$ ，可以得到：

$\begin{matrix}d^{(k)T}Q(x^*-x^0)&=&d^{(k)T}Q(x^*-x^k + x^k -x^0)\\&=&d^{(k)T}Q(x^*-x^k) +d^{(k)T}Q(x^k-x^0)\\&=&-d^{(k)T}g^k \end{matrix}$

因此有：

$\beta_k = -\frac{d^{(k)T} g^k}{d^{(k)T} Q d^{(k)}}=\alpha_k$

梯度和搜索方向的性质

当前梯度和历史搜索方向垂直

「最速下降法」优化过程中，当前点的梯度一定是和等高线垂直，上一步的搜索方向一定是和当前点的等高线相切。所以容易想象 $x^{k+1}$ 一定是和 $d^k$ 垂直的。

由于共轭梯度法在第k步迭代的时候，可以求得当前方向最优，即：

$\alpha_k=arg \min{f(x^k+\alpha d^k)}$

同时也是当前「子空间」最优，此处子空间为共轭方向锁确认的子空间，记为：

$\nu_k=x^0+span[d^0,d^1,...,d^{k}]$

由于共轭方向法可以做到每一次迭代是得到当前方向在全局最优的位置，所以有：

$f(x^{k+1})=\min_{\alpha}{f(x^0+D^k \alpha}=min_{x\in \nu_k}{f(x)}$

其中 $D^k=[d^0,d^1,...,d^k]$ 。

根据负梯度的意义，是描述函数下降方向的，在已经优化过的k个方向已经达到了最优点，所以 $g^{k+1}$ 一定是和每一个「历史共轭方向」垂直。

当前梯度和未来共轭方向线性相关

用反证法，已经和「历史方向」垂直了（线性无关），肯定就和未来方向线性相关了。

共轭方向法的计算效率很高，但是前提是必须能够给一组Q的共轭方向，幸运的是存在一种方法，能够随着迭代的进行，逐一产生Q的共轭方向，无需提前指定。

共轭梯度法

前面介绍了梯度和历史「共轭方向」之间的存在正交关系，那么是否可以利用这个「关系」逐一产生共轭方向呢？

为了生成下一个共轭方向，一种很直观的想法是空间随机生成一个向量，此向量和已有的共轭方向「线性无关」，然后调整向量的方向，使得和已有共轭方向「共轭」，由于 $D^n$ 可以表示整个空间，所以通过 $D^k$ 来调整方向是一种选择。所以新的方向可以用参数 $\beta_k=[\beta_k^0,\beta_k^1,...,\beta_k^k]^T$ 表示为:

$d^{k+1}=-g^{k+1}+\underbrace{\beta_k^0 d^0 + \beta_k^1d^1+...+\beta_k^kd^k}_{history \ span}$

接下来的问题就是确定向量 $\beta_k$ 即可。

因为 $d^{k+1}$ 要满足和历史搜索方向共轭，所以可以得到下面等式：

接下来就是求解上面的线性方程组，很容易求得：

$\begin{matrix}\beta_k^0& = & \frac{d^{(0)T} Qg^{k+1}}{d^{(0)T} Qd^0}\\ \beta_k^1& = & \frac{d^{(1)T} Qg^{k+1}}{d^{(1)T} Qd^1}\\ &\vdots &\\\beta_k^k& = & \frac{d^{(k)T} Qg^{k+1}}{d^{(k)T} Qd^k}\\\end{matrix}$

接下来的求解救水到渠成了，方向确定了之后可以通过直接求导并令导数为0求解：

$\alpha_k=\arg \min_{\alpha>=0}{f(x^k+\alpha d^k)}=-\frac{g^{(k)T}d^k}{d^{(k)T}Qd^k}$

接下来会证明， $d^{(j)T} Qg^{k+1}=0, j \in [0,k-1]$ ，所以 $\beta_k^j=\frac{d^{(j)T} Qg^{k+1}}{d^{(j)T} Qd^j}=\frac{0}{d^{(j)T} Qd^j}=0$ ，那么方向的迭代公式可以写为：

$d^{k+1}=-g^{k+1}+\underbrace{\beta_k^0 d^0 + \beta_k^1d^1+...+\beta_k^kd^k}_{history \ span}=-g^{k+1}+\beta_k^k d^k$

当前梯度和历史梯度垂直

还是反证法，因为梯度不是0，所以如果不垂直那么在历史梯度方向一定会有下降，和前面「子空间最优」结论矛盾。所以这里可以得到更加一般的结论：共轭梯度法中「当前梯度」和历史子空间垂直（这里的历史子空间是 $D^k$ 确定的子空间）。

所以当整个搜索完成的时候，搜索的每一步梯度都是互相「正交」，方向都是互相「共轭」。

当前梯度和历史非相邻方向共轭

这是一个神奇的结论：当前梯度 $g^{k+1}$ 和不相邻的历史方向 $d^j, j \in [0,k-1]$ 共轭。其实就是证明 \(j$j<k$ 的情况下，下面式子成立：

$g^{(k+1)T}Qd^j=0$

由于:

$g^{j+1}=Qx_{j+1}-b=Q(x_j+\alpha_j d^j)-b=Qx_j-b+Q\alpha_jd^j=g^j+\alpha_jQd^j$

将其代入得到：

$g^{(k+1)T}Qd^j=g^{(k+1)T}\frac{(g^{j+1}-g^j)}{\alpha_j}=0$

非二次型中的共轭梯度法

接下来就是套路了，非二次型利用泰勒展开转化为二次型问题即可。同时为了避免计算汉森矩阵， $\alpha_k$ 可以通过一维搜索转化为一维搜索，对 $\beta_k$ 可以进行各种替换计算。

Hestenes-Stiefel公式

利用 $Qd^k=(g^{k+1}-g^k)/\alpha_k$ ， $\beta_k$ 可以改写为：

$\beta_k=\frac{g^{(k+1)T} \ \ Qd^k}{d^{(k)T}Qd^k}=\frac{g^{(k+1)T} \ \ (g^{k+1}-g^{k})}{d^{(k)T}(g^{k+1}-g^k)}$

Polak-Ribiere公式

利用当前梯度和历史方向正交，上式分母可以进一步化简为：

$\beta_k= \frac{g^{(k+1)T} \ (g^{k+1}-g^{k}) \ }{g^{(k)T} g^k}$

Fletcher-Reeves公式

利用当前梯度和历史梯度正交，上式分子可以化简为：

$\beta_k= \frac{g^{(k+1)T} \ \ g^{k+1} \ }{g^{(k)T} \ \ g^k}$

上面三个迭代公式中，虽然对二次型是等价的，但是对非二次型的表现确实不同的。实际应用中，要对共轭梯度法进行一些稍微的调整，首先在通过「最速下降法」中的停止条件（偏导数为0）并不实用，因为可能迭代好多次也不为0。所以需要选择合适的停止条件。

对于非二次型问题，共轭梯度法通常不会在n步之内收敛到极小，随着迭代的进行搜索方向将不再是Q的共轭方向，通常用的解决方法是经过几次迭代之后将搜索方向初始化为目标函数的梯度方向，然后接着搜索。

至于选择哪个公式作为搜索方向，没有定论说哪个公式一定好于另一个，不同的目标函数结论不一样。

参考文献

《最优化导论》Edwin K.P.Chong Stanislaw H. Zak

《Numerical Optimization》 Jorge Nocedal Stephen J. Wright

未经允许不得转载：大数据算法 » 「最优化」共轭方向法