- 前言
- 共轭梯度法的引出
- 线性共轭梯度法
- 共轭向量组构造
- 线性共轭梯度流程
- 补充：线性共轭梯度法的简化
本篇继续无约束优化算法学习，线性共轭梯度法。
共轭梯度法的引出回顾之前的牛顿法、拟牛顿法，目的都是寻找迭代方向。牛顿法中的 H Δ x = J H\Delta x=J HΔx=J，高斯牛顿的 J J T p = − J f JJ^Tp=-Jf JJTp=−Jf，都涉及到一个解方程组的问题。如果方程组是线性的，则解线性方程组 A x = b Ax=b Ax=b的问题可以转化为一个优化问题： A x = b → arg min x f ( x ) = 1 2 x T A x − b T x b e c a u s e ∇ f ( x ) = A x − b = 0 w h e n f ( x ) = min f ( x ) Ax=b \\ \to \argmin_{x} f(x) = \frac{1}{2}x^TAx-b^Tx \\ \quad \\ because \quad \nabla f(x)=Ax-b=0 \\ when \quad f(x)=\min f(x) Ax=b→xargminf(x)=21xTAx−bTxbecause∇f(x)=Ax−b=0whenf(x)=minf(x)
在梯度下降法中，迭代过程可能出现下图的折线。这是因为梯度下降法只考虑了一阶梯度，当前迭代的方向可能与上次迭代的方向线性相关，使得迭代过程来回抖动。 
即使通过线搜索方法得到最优步长时，相邻两次迭代的梯度正交，如下图所示，将增量进行分解，不朝向极值点的分量仍然会导致抖动。
这里证明一下精确线搜索的梯度下降法，两次梯度正交：
最
优
步
长
处
，
f
关
于
α
的
导
数
为
0
f
′
(
x
k
+
1
)
=
f
′
(
x
k
+
α
(
−
∇
f
(
x
k
)
)
)
=
0
→
f
′
(
x
k
+
α
(
−
∇
f
(
x
k
)
)
=
−
∇
f
(
x
k
)
T
∇
f
(
x
k
+
1
)
=
0
最优步长处，f关于\alpha的导数为0 \\ f' (x_{k+1})=f'(x_k+\alpha (-\nabla f(x_k)))=0 \\ \to f'(x_k+\alpha (-\nabla f(x_k))= -\nabla f(x_k)^T\nabla f(x_{k+1}) =0
最优步长处，f关于α的导数为0f′(xk+1)=f′(xk+α(−∇f(xk)))=0→f′(xk+α(−∇f(xk))=−∇f(xk)T∇f(xk+1)=0 
共轭梯度法要解决的就是生成下面这条绿线的迭代过程。 
对于对称正定矩阵 A A A，如果存在一个向量组 { δ n } , δ i T A δ j = 0 \{ \delta _n\},\delta_i^TA\delta_j=0 {δn},δiTAδj=0对于任意两个不同的向量都成立，称向量组是 A A A的共轭向量组。共轭向量组是线性无关的，可以用反证法证明： i f d 1 = λ 2 d 2 + ⋯ + λ n d n t h e n d i T A d j = ( λ 2 d 2 + ⋯ + λ n d n ) T A d j = λ d j T A d j = 0 t h e n ∀ j , d j = 0 ⃗ if \quad d_1=\lambda_2d_2+\dots+\lambda_nd_n \\ then \quad d_i^TAd_j=(\lambda_2d_2+\dots+\lambda_nd_n)^TAd_j \\ = \lambda d_j^TAd_j=0 \\ then \quad \forall j, \quad d_j=\vec 0 ifd1=λ2d2+⋯+λndnthendiTAdj=(λ2d2+⋯+λndn)TAdj=λdjTAdj=0then∀j,dj=0
共轭梯度法证明了对于二次型的优化问题，可以通过构造共轭向量组 { δ n } \{ \delta _n\} {δn}，依次沿着每个共轭向量（梯度）上优化后，就能得到极小值。也就是说，迭代 n n n次后就能得到结果。
共轭向量组构造第一个共轭向量可以通过梯度下降法获得 p 0 p_0 p0，梯度下降法得到的相邻梯度是正交的（线性无关），因此可以用来构造共轭向量： α 0 通 过 精 确 线 搜 索 获 得 p 0 = − ∇ f ( x 0 ) p ^ 1 = − ∇ f ( x 0 + α 0 p 0 ) p 1 = p ^ 1 + β 1 p 0 = ∇ f ( x 0 + α 0 p 0 ) − β 1 p 0 p 0 T A p 1 = 0 β 1 p 0 T A p 0 − p 0 T A ∇ f ( x 0 + α 0 p 0 ) = 0 β 1 = p 0 T A ∇ f ( x 0 + α 0 p 0 ) p 0 T A p 0 \alpha_0通过精确线搜索获得 \\ p_0 = -\nabla f(x_0) \\ \hat p_1=-\nabla f(x_0+\alpha_0 p_0) \\ p_1 =\hat p_1 + \beta_1p_0=\nabla f(x_0+\alpha_0 p_0)-\beta_1p_0 \\ \quad \\ p_0^TAp_1=0 \\ \beta_1p_0^TAp_0 - p_0^TA\nabla f(x_0+\alpha_0 p_0)=0 \\ \quad \\ \beta_1 = \frac{p_0^TA\nabla f(x_0+\alpha_0 p_0)}{p_0^TAp_0} \\ \quad \\ α0通过精确线搜索获得p0=−∇f(x0)p^1=−∇f(x0+α0p0)p1=p^1+β1p0=∇f(x0+α0p0)−β1p0p0TAp1=0β1p0TAp0−p0TA∇f(x0+α0p0)=0β1=p0TAp0p0TA∇f(x0+α0p0) 然后迭代构造每一步的共轭向量： α k 通 过 精 确 线 搜 索 获 得 p k + 1 = β k + 1 p k + p ^ k + 1 β k + 1 = p k T A ∇ f ( x k + α k p k ) p k T A p k \alpha_k通过精确线搜索获得 \\ p_{k+1} = \beta_{k+1} p_{k}+\hat p_{k+1} \\ \beta_{k+1}=\frac{p_k^T A \nabla f(x_k+\alpha_kp_k)}{p_k^TAp_k} αk通过精确线搜索获得pk+1=βk+1pk+p^k+1βk+1=pkTApkpkTA∇f(xk+αkpk) 可以证明，上面的迭代出的共轭向量可以构成共轭向量组。
然后通过精确线搜索获得 α k + 1 \alpha_{k+1} αk+1： α k + 1 = p k + 1 T p ^ k + 1 p k + 1 T A p k + 1 \alpha_{k+1}=\frac{p_{k+1}^T\hat p_{k+1}}{p_{k+1}^TAp_{k+1}} αk+1=pk+1TApk+1pk+1Tp^k+1
线性共轭梯度流程- 给定 x 0 x_0 x0，通过梯度下降法获得初始 p 0 , α 0 p_0,\alpha_0 p0,α0
- 迭代到第k次，判断收敛条件，若不满足，进入3；否则跳出循环
- 通过共轭梯度构造公式依次计算 x k + 1 , β k + 1 , p k + 1 , α k + 1 x_{k+1},\beta_{k+1},p_{k+1},\alpha_{k+1} xk+1,βk+1,pk+1,αk+1，判断收敛条件，若不满足则回到2
前面推导的时候，没有用到线性条件 ∇ f ( x ) = A x − b \nabla f(x)=Ax-b ∇f(x)=Ax−b，这里可以进行简化。首先给出简化后的精确线搜索步长： f ′ ( x k + α k p k ) = p k T ∇ f ( x k + α k p k ) = 0 → p k T ( A ( x k + α k p k ) − b ) = 0 → p k T A x k + α k p k T A p k = p k T b → α k = p k T ( b − A x k ) p k T A p k s e t b − A x k = r k , α k = r k T p k p k T A p k f'(x_k+\alpha_k p_k)=p_k^T\nabla f(x_k+\alpha_k p_k)=0 \\ \to p_k^T(A(x_k+\alpha_k p_k)-b)=0 \\ \to p_k^TAx_k+\alpha_k p_k^TAp_k=p_k^Tb \\ \quad \\ \to \alpha_k=\frac {p_k^T(b-Ax_k)}{p^T_kAp_k} \\ set \quad b-Ax_k=r_k, \quad \alpha_k = \frac {r^T_kp_k}{p^T_kAp_k} f′(xk+αkpk)=pkT∇f(xk+αkpk)=0→pkT(A(xk+αkpk)−b)=0→pkTAxk+αkpkTApk=pkTb→αk=pkTApkpkT(b−Axk)setb−Axk=rk,αk=pkTApkrkTpk 然后构造共轭梯度向量： p k + 1 = ∇ f ( x k + α k p k ) + β k + 1 p k a n d p k T A p k + 1 = 0 → p k T A ∇ f ( x k + α k p k ) + β k + 1 p k T A p k = 0 → β k + 1 p k T A p k = − p k T A ∇ f ( x k + α k p k ) β k + 1 = − p k T A ∇ f ( x k + α k p k ) p k T A p k = − p k T A ( A x k + 1 − b ) p k T A p k = r k + 1 T A p k p k T A p k p_{k+1}=\nabla f(x_{k}+\alpha_kp_k)+\beta_{k+1} p_k \\ and \quad p_{k}^TAp_{k+1}=0 \\ \to p_k^TA\nabla f(x_{k}+\alpha_kp_k)+\beta_{k+1} p_k^TAp_k=0 \\ \to \beta_{k+1} p_k^TAp_k= -p_k^TA\nabla f(x_{k}+\alpha_kp_k) \\ \quad \\ \beta_{k+1} = -\frac{p_k^TA\nabla f(x_{k}+\alpha_kp_k)}{p_k^TAp_k} \\ \quad \\ = -\frac {p_k^TA(Ax_{k+1}-b)}{p_k^TAp_k} \\ = \frac {r_{k+1}^TAp_{k}}{p_k^TAp_k} \\ pk+1=∇f(xk+αkpk)+βk+1pkandpkTApk+1=0→pkTA∇f(xk+αkpk)+βk+1pkTApk=0→βk+1pkTApk=−pkTA∇f(xk+αkpk)βk+1=−pkTApkpkTA∇f(xk+αkpk)=−pkTApkpkTA(Axk+1−b)=pkTApkrk+1TApk
最后梳理一下：
- 初始化 k = 0 k=0 k=0，计算 x 0 , p 0 x_0,p_0 x0,p0
- 迭代第 k + 1 k+1 k+1轮，判断收敛条件，不满足时继续循环
- α k = r k T p k p k T A p k \alpha_k=\frac {r^T_kp_k}{p^T_kAp_k} αk=pkTApkrkTpk
- x k + 1 = x k + α k p k x_{k+1}=x_k+\alpha_k p_k xk+1=xk+αkpk
- r k + 1 = b − A x k + 1 r_{k+1}=b-Ax_{k+1} rk+1=b−Axk+1
- β k + 1 = r k + 1 T A p k p k T A p k \beta_{k+1}=\frac {r_{k+1}^TAp_{k}}{p_k^TAp_k} βk+1=pkTApkrk+1TApk
- p k + 1 = − r k + 1 + β k + 1 p k p_{k+1}=-r_{k+1}+\beta_{k+1}p_k pk+1=−rk+1+βk+1pk
- k = k + 1 k=k+1 k=k+1
