数值计算之 共轭梯度法（2）非线性共轭梯度法

前言

上篇写了线性共轭梯度法，本篇继续非线性共轭梯度法

非线性共轭梯度法

非线性共轭梯度法：

1. k = 0 k=0 k=0，通过梯度下降法初始化 x 0 , r 0 = ∇ f ( x 0 ) , p 0 = − r 0 x_0,r_0=\nabla f(x_0),p_0=-r_0 x0​,r0​=∇f(x0​),p0​=−r0​
2. 迭代到 k k k轮，判断收敛条件，如果不满足则进入第3步
3. 通过非精确线搜索计算 α k \alpha_{k} αk​
4. x k + 1 = x k + α k p k x_{k+1}=x_k+\alpha_{k}p_k xk+1​=xk​+αk​pk​
5. r k + 1 = ∇ f ( x k + 1 ) r_{k+1}=\nabla f(x_{k+1}) rk+1​=∇f(xk+1​)
6. β k + 1 = r k + 1 T r k + 1 r k T r k \beta_{k+1}=\frac{r_{k+1}^Tr_{k+1}}{r_{k}^Tr_{k}} βk+1​=rkT​rk​rk+1T​rk+1​​
7. 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+1​pk​
8. k = k + 1 k=k+1 k=k+1

以上就是FR-CG法的流程。

为了确保全局收敛性，使用FR-CG法时，要结合Strong Wolfe Condition，并且收敛速度比较慢。

将 β \beta β的更新方式进行更换，可以获得收敛速度更快的PR-CG法： β ^ k + 1 = r k + 1 T ( r k + 1 − r k ) ∣ ∣ r k ∣ ∣ 2 β k + 1 = max ⁡ { β ^ k + 1 , 0 } \hat \beta_{k+1}=\frac {r_{k+1}^T(r_{k+1}-r_{k})}{||r_k||^2} \\ \quad \beta_{k+1}=\max \{\hat\beta_{k+1},0 \} β^​k+1​=∣∣rk​∣∣2rk+1T​(rk+1​−rk​)​βk+1​=max{β^​k+1​,0}