G.Jerry的共轭梯度法笔记_baolan2020的博客

该笔记初衷为期末复习所用，引用出处均已注明，涉及个人理解部分如果有不对之处，还请批评指正，俺会虚心接受滴！

1.应用范围

目标函数 $min f(x)=1/2*x^TQx+b^Tx+c, x=(x_1,x_2,...,x_n)^T$ 的无约束绩效问题。

2.相关定义

定义1 设Q为n阶实对称正定矩阵，若n维方向x和y满足 $x^TQy=0$ ，则称方向x和y是Q-共轭的。

3.原理

将函数改写成如下形式：

如果每个子函数 ${f_i}\left( {{x_i}} \right)$ 都能取得最小值，那么f(x)也能取得最小值。假设梯度下降一共需要n阶(也就是迭代次数啦)，每个 ${f_i}\left( {{x_i}} \right)$ 对应一个阶梯，每阶的方向和步长都使 ${f_i}\left( {{x_i}} \right)$ 取得最小值。

我们当然希望阶梯数n越少越好，那么如何找到所需最少的阶梯数呢？当阶梯数最少时，每阶的方向和步长都不同，且每阶都无法由其他的阶梯组合而成。也就是说，每次梯度下降的方向必须是线性无关的，梯度下降的次数才会最少，迭代次数才会最少。

我们是有办法找到一组线性无关的方向向量（即Rn中的一组基{p1,p2,…,pn}）的哦！首先在初始点(记为x1)选取负梯度方向为p1(就是x1点的方向啦)，然后寻找与p1共轭的方向为p2，再寻找与p1和p2共轭的方向为p3，…，由此经过n次寻找到f(x)的最小值。

也就是说，我们需要找到合适的基{p1,p2,…,pn}，从而确定方向、步长的迭代式，满足 $\frac{{d(f({x_i} + \alpha {p_i})}}{{d\alpha }} = {p_i}^T\triangledown f\left( {{x_{i + 1}}} \right) = 0$ ，i∈{1,2,…,n}。

好巧不巧，当 ${\left[ {{p_1}{\text{ }}{p_2}{\text{ }} \ldots {\text{ }}{p_n}} \right]^T}Q\left[ {{p_1}{\text{ }}{p_2}{\text{ }} \ldots {\text{ }}{p_n}} \right] = diag\{ {\vartriangle _1},{\vartriangle _2}, \ldots ,{\vartriangle _n}\}$ 时，选择方向 ${p_{i + 1}} = - \triangledown f\left( {{x_{i + 1}}} \right) + {\lambda _i}{p_i}$ ，其中 ${\lambda _i} = \frac{{{p_i}^TQ\triangledown f\left( {{x_{i + 1}}} \right)}}{{{p_i}^TQ{p_i}}}$ (常数)，步长为 ${\alpha _{\text{i}}} = \frac{{ - {p_i}^T\triangledown f\left( {{x_i}} \right)}}{{{p_i}^TQ{p_i}}}$ (常数)，可以满足上述条件。

当 ${\left[ {{p_1}{\text{ }}{p_2}{\text{ }} \ldots {\text{ }}{p_n}} \right]^T}Q\left[ {{p_1}{\text{ }}{p_2}{\text{ }} \ldots {\text{ }}{p_n}} \right] = diag\{ {\vartriangle _1},{\vartriangle _2}, \ldots ,{\vartriangle _n}\}$ 时，就可以使 $\frac{{d(f({x_i} + \alpha {p_i})}}{{d\alpha }} = {p_i}^T\triangledown f\left( {{x_{i + 1}}} \right) = 0$ ，i∈{1,2,…,n}成立了。

已知 $df\left( x \right) = \triangledown f\left( x \right) = Qx + b$ ，那么 $\triangledown f\left( {{x_{i + 1}}} \right) - \triangledown f\left( {{x_{j + 1}}} \right) = Q\left[ {{x_{i + 1}} - {x_{j + 1}}} \right]$ 总是成立，i∈{1,2,…,n}，j∈{1,2,…,i}（简单来说，i表示当前迭代次数，j表示i次之前的每个迭代次数，显然i≠j）。(正是这个独特的导数和梯度条件，使得共轭梯度法的使用范围有限制！)整理一下就是 $\triangledown f\left( {{x_{i + 1}}} \right) = \triangledown f\left( {{x_{j + 1}}} \right) + Q\left[ {{x_{i + 1}} - {x_{j + 1}}} \right]$ 。这非常容易凑成共轭关系：

这里仅仅得到了基需要满足的条件(即它们必须具有关于Q共轭的性质)。然而，在迭代过程中，程序需要的是pi+1与pi的关系式，以及λi+1与λi的关系式。所以要根据基的共轭特性，找出方向和步长的迭代式。

根据恒成立等式 ${p_i}^TQ{p_{i + 1}} = 0$ ，尝试构造出一类方向迭代式： ${p_{i + 1}} = - \triangledown f\left( {{x_{i + 1}}} \right) + {\lambda _i}{p_i}$ 。显然当 ${\lambda _i} = \frac{{{p_i}^TQ\triangledown f\left( {{x_{i + 1}}} \right)}}{{{p_i}^TQ{p_i}}}$ 时，

${p_i}^TQ{p_{i + 1}} = - {p_i}^TQ\triangledown f\left( {{x_{i + 1}}} \right) + {\lambda _i}{p_i}^TQ{p_i} = - {p_i}^TQ\triangledown f\left( {{x_{i + 1}}} \right) + \frac{{{p_i}^TQ\triangledown f\left( {{x_{i + 1}}} \right)}}{{{p_i}^TQ{p_i}}}{p_i}^TQ{p_i}$ =0总是成立。这样就确定下方向迭代式了。

通过恒成立等式 ${p_j}^TQ{p_{i + 1}} = 0$ 可以确定步长迭代式。显然当 ${\alpha _{\text{i}}} = \frac{{ - {p_i}^T\triangledown f\left( {{x_i}} \right)}}{{{p_i}^TQ{p_i}}}$ 时，下式成立：

其中 $\triangledown f{\left( {{x_j}} \right)^T}\triangledown f\left( {{x_{i + 1}}} \right) = 0$ 可由 ${p_j}^T\triangledown f\left( {{x_{i + 1}}} \right) = - \triangledown f{\left( {{x_j}} \right)^T}\triangledown f\left( {{x_{i + 1}}} \right) + {\lambda _{j - 1}}{p_{j - 1}}^T\triangledown f\left( {{x_{i + 1}}} \right) = 0 + 0$ 推出。

本来这里就结束了，但是大聪明们发现方向 ${p_{i + 1}} = - \triangledown f\left( {{x_{i + 1}}} \right) + {\lambda _i}{p_i}$ 中的 ${\lambda _i} = \frac{{{p_i}^TQ\triangledown f\left( {{x_{i + 1}}} \right)}}{{{p_i}^TQ{p_i}}}$ 是可以简化的，于是将其简化为