共轭梯度法是一种经典的优化算法。算法求解速度较快,虽然比梯度下降法复杂,但是比二阶方法简单。
一、引入
1. 优化模型建立
假定待优化的问题如下所示:
min x f ( x ) = 1 2 x T A x − b T x \min_{x} f(x)=\frac{1}{2}x^TAx - b^Tx xminf(x)=21xTAx−bTx
其中 x x x为待优化变量, A A A为半正定矩阵(在线性代数中,正定矩阵为对称矩阵), b b b为已知变量。下标k表示优化步数,负梯度为
r k = − ( A x k − b ) r_k =-( Ax_k -b) rk=−(Axk−b)
假设最优变量为 x ∗ x^* x∗,则优化问题可变为求方程 A x ∗ = b Ax^*=b Ax∗=b的解。梯度 r r r也可以称作每一步的残差。误差定义为 x x x与最优变量的差值
e k = x ∗ − x k e_k = x^* - x_k ek=x∗−xk
2. 算法思想简述
虽然梯度下降法的每一步都是朝着局部最优的方向前进的,但是它在不同的迭代轮数中会选择非常近似的方向,说明这个方向的误差并没通过一次更新方向和步长更新完,在这个方向上还存在误差,因此参数更新的轨迹是锯齿状。共轭梯度法的思想是,选择一个优化方向后,本次选择的步长能够将这个方向的误差更新完,在以后的优化更新过程中不再需要朝这个方向更新了。由于每次将一个方向优化到了极小,后面的优化过程将不再影响之前优化方向上的极小值,所以理论上对N维问题求极小只用对N个方向都求出极小就行了。为了不影响之前优化方向上的更新量,需要每次优化方向共轭正交。假定每一步的优化方向用 p k p_k pk表示,可得共轭正交
p i A p j = 0 i ≠ j p_iAp_j = 0 \qquad i\ne j piApj=0i̸=j
由此可得,每一步优化后,当前的误差和刚才的优化方向共轭正交。
p k A e k + 1 = 0 p_kAe_{k+1}=0 pkAek+1=0
若为N维空间优化问题,则每次优化方向可以组成这个空间中的一组基底。 P = { p 1 , p 2 , … , p N } P=\{p_1,p_2,\dots,p_N\} P={
p1,p2,…,pN}
二、算法推导
算法只需要解决两个问题:
- 优化方向
- 优化步长
1.优化方向确定
假定第一次优化方向为初始负梯度方向
p 1 = r 1 = b − A x 1 p_1 = r_1 = b-Ax_1 p1=r1=b−Ax1
每一次优化方向与之前的优化方向正交,采用Gram-Schmidt方法进行向量正交化,每次优化方向根据当前步的梯度得出
p k = r k − ∑ i < k p i T A r k p i T A p i p i p_k = r_k-\sum_{i<k}\frac{p_i^TAr_k}{p_i^TAp_i}p_i pk=rk−i<k∑piTApipiTArkpi
便于后面证明,令 β i = p i T A r k p i T A p i \beta_i=\frac{p_i^TAr_k}{p_i^TAp_i} βi=piTApipiTArk
上式在后面还会进一步优化,省去求和符号。
2.优化步长的选取
假定第k步的优化步长为 α k \alpha_k αk。
方法一:
f ( x k + 1 ) = f ( x k + α k p k ) = g ( α k ) f(x_{k+1})=f(x_k+\alpha_kp_k)=g(\alpha_k) f(xk+1)=f(xk+αkpk)=g(αk),对 α k \alpha_k αk求导令导数为0可得 α k = p k T r k p k T A p k \alpha_k=\frac{p_k^Tr_k}{p_k^TAp_k} αk=pkTApkpkTrk。
方法二:
p k T A e k + 1 = p k T A ( x ∗ − x k + 1 ) = p k T A ( x ∗ − x k + x k − x k + 1 ) = p k T A ( e k − α k p k ) = p k T A e k − α k p k T A p k =