共轭方向法 | 彩潭有鲤的札记

type

status

date

slug

summary

基本的共轭方向法

针对维二次型函数的最小化问题其中，。由于，因此函数有一个全局极小点，可通过求解方程得到。

基本的共轭方向法：给定初始点和一组关于共轭的方向，迭代公式为：

对于任意初始点，基本共轭方向法都能在次迭代之内收敛到唯一全局极小点，即

在共轭方向算法中, 对于所有，都有

即

例：利用基本的共辄方向算法求函数的极小点，初始点为，初始点为，给定共轭方向为。

首先计算：

因此：

再计算：

因此：

由于函数是一个二维的二次型函数，故

目标函数为维二次型函数时，共轭方向法能够在步迭代之后得到极小点

共辄方向法的计算效率很高但是前提是必须能够给定一组共轭方向

共轭梯度法

共轭梯度法不需要预先给定共轭方向，而是随着迭代的进行不断产生共轭方向。在每次迭代中，利用上一个搜索方向和目标函数在当前迭代点的梯度向量之间的线性组合构造一个新方向，使其与前面已经产生的搜索方向组成共轭方向。

考虑二次型目标函数:

其中，初始点为，搜索方向采用最速下降法的方向，即函数在处梯度的负方向，即

产生下一个迭代点：

其中，步长为：

再开展下一次迭代，搜索方向应该和是关于共轭的，可将写为和之间的线性组合。推广开来，在第次迭代中，捜索方向写为和之间的线性组合，可写为：

按照如下方式选择系数 , 可以使得组成共轭方向：

共轭梯度法算法归纳：

令；选择初始值。

计算，如果，停止迭代；否则，令。

计算。

计算。

计算，如果，停止迭代。

计算。

计算。

令，返回第3步。

共轭梯度法中的搜索方向 是 共轭方向

例：目标函数为二次型函数利用共轭梯度法求其极小点，初始点为

函数可以写为

其中，

函数的梯度为

因此，

新的迭代点为

可得

对应的搜索方向为

步长为

得到新的迭代点为

开展第3次迭代，可得

步长为

非二次型问题中的共轭梯度法

共轭梯度法是共轭方向法的一种具体实现，能够在步之内迭代求得维正定二次型函数的极小点。如果将函数视为某个目标函数泰勒展开式的二阶近似，就可以将共轭梯度法推广应用到一般的非线性函数。由泰勒展开式可知，如果展开点离函数极小点比较近，那么函数可以利用二次型函数进行较好的近似。二次型函数中的矩阵，即黑塞矩阵是常数矩阵。但是，对于一般的非线性函数而言，每次迭代都必须重新计算黑塞矩阵，这需要非常大的运算量。因此，有必要对共轭梯度法进行修改，消除每次迭代中求黑塞矩阵的环节，使得算法更加高效。

矩阵只出现在和的计算公式中，由于

说明的计算公式可以替换为一维搜索过程。因此，只需要考虑从的计算公式中去掉就可以了，使得的计算只需要用到当前达代点的函数值和梯度值。为此，假设二次型目标函数的黑塞矩阵末知，但目标函数和梯度是可求的。利用数学上的处理，可以将从的计算公式中消除，从而实现对共轭梯度法的修正。

Hestenes-Stiefel公式

共轭梯度法中, 的计算公式为

利用替代，可得到 Hestenes-Stiefel 公式

对于二次型目标函数，，等号两侧同时左乘矩阵，并减去向量，由于，因此，简单整理后有

Polak-Ribiere公式

Hestenes-Stiefel公式中分母展开，可得

，等式的两侧同时左乘，可得

Polak-Ribiere公式

将 Polak-Ribière公式的分子部分展开，可得

由

可得

将以上这3个公式应用到共辄梯度法中，在迭代过程中就不需要求解黑塞矩阵，每次迭代只需要计算目标函数值和梯度就可以了。对于二次型问题，这3个公式是等价的；但是，当目标函数为一般的非线性函敖时，这3个公式并不一致。

对于非二次型问题，共轭梯度法通常不会在忧步之内收敛到极小点，随着迭代的进行，搜索方向将不再是共轭方向。常用的解决办法是每经过几次迭代之后（如或次），重新将搜索方向初始化为目标函数梯度的负方向，然后继续搜索直到满足停止规则。