共轭梯度法

1. 为什么要用共轭梯度

• 梯度下降法受限制于搜索步长的学习率问题，可能需要多次搜索才能达到极值点；
• 最速下降法每次的下降方向都和上次的正交，因此会产生锯齿现象，在靠近极值点的时候会多次缓慢搜索。那么在同一个方向上可能多次下降，这不如一次在这个方向上一次搜索到底。

2. 共轭向量法

对于无约束的二次型目标函数：

其中 $A$ 是对称正定的，问题在于求取其最小值点 $x^{*}$。也可以说是求以下方程的解，这两个问题等效。

定理：若矩阵A为对称正定阵，并且一组向量 $\{d_{0},d_{1}, ...,d_{m}\}$ 是关于A共轭的，那么这组向量是线性无关的。 说明：向量组$\{d_{0},d_{1}, ...,d_{m}\}$关于矩阵A共轭，即

$$ d_{i}^{T}Ad_{j} = 0, \qquad \{i \neq j\} $$

可以选取一组共轭向量作为每次变量迭代的方向，即 $\{d_{0},d_{1},d_{2}, ... , d_{n-1} \}$，假设目标函数极值点为 $x^{*}$，则

从 $x_{i}$ 迭代到 $x_{i+1}$ 的表达式为：

那么 $d_{i}$ 作为已知的方向，现在只需要求在这个方向上的步长 $\alpha_{i}$ 。

对于第 $i$ 步时，我们有

所以，迭代公式就为：

这叫做共轭向量法。前提是知道二次项系数 $A$ 的一组完备的共轭向量组。这里加入了一些限制，比如 $A$ 是对称矩阵，则其共轭向量组是正交的，也是共轭的。那么共轭向量组就是其特征向量组。

共轭方向定理：记向量 $\{ d_{0},d_{1},…,d_{n−1}\}$ 是 A 共轭的， $x_{0} \in R^{n}$ 是任意的一个 n 维向量，则按照 $x_{i+1} = x_{i} + \alpha_{i} d_{i},g_{i} =Ax_{i}-b,\alpha_{i} = \frac{d_{i}^{T}g_{i}}{ d_{i}^{T} Ad_{i} ^{T}}$ 的迭代格式进行 n 步迭代，我们就能得到 $x_{n} = x^{*}$。

3. 共轭梯度法

在共轭向量法中，每次搜索的方向就是一个共轭向量的方向，共轭向量组需要事先获得。但要是可以在迭代过程中逐步获得当前的搜索方向，也就是共轭梯度，那就更好了。 在第一次迭代给定初值 $x_{0}$ 后，此时的搜索方向设定为梯度方向，即

对于 $x_{i+1}$ 时的搜索方向，我们可认为是上一位置的搜索方向 $d_{i}$ 和当前位置的梯度方向 $g_{i+1}$ 的线性组合：

那么，要求解得到这个 $\beta_{i}$：

于是对于共轭梯度法，迭代步骤便如下：

1. 令 $k := 0$； 选择初始值 $x_{0}$。
2. 计算 $g_{0} = \nabla f(x_{0})$ ，若 $g_{0} = 0$ ，停止迭代，否则令 $d_{0} = g_{0}$；
3. 计算 $\alpha_{0} =-\frac{d_{0}^{T}g_{0}}{d_{0}^{T} Ad_{0} ^{T}}$；
4. 完成第一次迭代： $x_{1} = x_{0} + \alpha_{0} d_{0}$；
5. 计算 ${i+1}$ 时刻梯度 $g_{i+1} = \nabla f(x_{i+1})$ ；
6. 计算 $i+1$ 时刻搜索方向 $d_{i+1} = -g_{i+1} + \beta_{i} d_{i}$， 其中$\beta_{i} = \frac{d_{i}^{T}Ag_{i+1}}{d_{i}^{T}Ad_{i}}$。
7. 计算 $i+1$ 时刻步长 $\alpha_{i+1} = -\frac{d_{i+1}^{T}g_{i+1}}{ d_{i+1}^{T} Ad_{i+1} ^{T}}$；
8. 搜索得到 $i+2$ 时刻 $x_{i+2} = x_{i+1}+\alpha_{i+1}d_{i+1}$

4. 补充

• 共轭法的每一个方向的步长是确定的，不然没有办法最终 $n$ 步到达极值点（极值点是共轭向量的线性组合）。当然也可以设置为固定步长的学习率，这就不能保证 $n$ 步之后到达极值点了。
• 共轭向量组的求解有很多方法，这里是假定当前搜索方向是当前梯度和上一位置搜索方向的线性组合。还有一些其他方法：
  1. Fletcher-Reeves （FR）法： $\beta_{i} = \frac{g_{i+1}^{T}g_{i+1}}{g_{i}^{T}g_{i}}$
  2. Polak-Ribière （PR）法：$\beta_{i} =\frac{g_{i+1}^{T}(g_{i+1} - g_{i})}{g_{i}^{T}g_{i}}$