數值計算之 共軛梯度法（1）線性共軛梯度法

• 前言
• 共軛梯度法的引出
• 線性共軛梯度法
• • 共軛向量組構造
  • 線性共軛梯度流程
• 補充：線性共軛梯度法的簡化

前言

本篇繼續無約束優化算法學習，線性共軛梯度法。

共軛梯度法的引出

回顧之前的牛頓法、擬牛頓法，目的都是尋找迭代方向。牛頓法中的$H\Delta x=J$，高斯牛頓的$J{J}^{T}p=?Jf$，都涉及到一個解方程組的問題。如果方程組是線性的，則解線性方程組$Ax=b$的問題可以轉化為一個優化問題：
$$\begin{gathered} Ax=b \\ \to \underset{x}{\mathrm{argmin}}f(x)=\frac{1}{2}{x}^{T}Ax?b^{T}x \\ because?f(x)=Ax?b=0 \\ whenf(x)=\min f(x) \end{gathered}$$

在梯度下降法中，迭代過程可能出現下圖的折線。這是因為梯度下降法只考慮了一階梯度，當前迭代的方向可能與上次迭代的方向線性相關，使得迭代過程來回抖動。

即使通過線搜索方法得到最優步長時，相鄰兩次迭代的梯度正交，如下圖所示，將增量進行分解，不朝向極值點的分量仍然會導致抖動。

這里證明一下精確線搜索的梯度下降法，兩次梯度正交：
$$\begin{gathered} 最優步長處，f關于\alpha 的導數為0 \\ {f}^{\prime }(x_{k+1})=f^{\prime }(x_k+\alpha (??f(x_k)))=0 \\ \to f^{\prime }(x_k+\alpha (??f(x_k))=??f(x_k{)}^T?f(x_{k+1})=0 \end{gathered}$$

共軛梯度法要解決的就是生成下面這條綠線的迭代過程。

線性共軛梯度法

對于對稱正定矩陣$A$，如果存在一個向量組$\{{\delta }_n\},{\delta }_i^{T}A{\delta }_j=0$對于任意兩個不同的向量都成立，稱向量組是$A$的共軛向量組。共軛向量組是線性無關的，可以用反證法證明：
$$\begin{gathered} if{d}_1={\lambda }_2{d}_2+?+{\lambda }_n{d}_n \\ then{d}_i^{T}A{d}_j=({\lambda }_2{d}_2+?+{\lambda }_n{d}_n{)}^{T}A{d}_j \\ =\lambda d_j^{T}A{d}_j=0 \\ then?j,d_j=0 \end{gathered}$$

共軛梯度法證明了對于二次型的優化問題，可以通過構造共軛向量組$\{{\delta }_n\}$，依次沿著每個共軛向量（梯度）上優化后，就能得到極小值。也就是說，迭代$n$次后就能得到結果。

共軛向量組構造

第一個共軛向量可以通過梯度下降法獲得$p_0$，梯度下降法得到的相鄰梯度是正交的（線性無關），因此可以用來構造共軛向量：
$$\begin{gathered} {\alpha }_0通過精確線搜索獲得 \\ {p}_0=??f(x_0) \\ {\hat{p}}_1=??f(x_0+{\alpha }_0{p}_0) \\ {p}_1={\hat{p}}_1+{\beta }_1{p}_0=?f(x_0+{\alpha }_0{p}_0)?{\beta }_1{p}_0 \\ {p}_0^{T}A{p}_1=0 \\ {\beta }_1{p}_0^{T}A{p}_0?p_0^{T}A?f(x_0+{\alpha }_0{p}_0)=0 \\ {\beta }_1=\frac{p_0^{T}A?f(x_0+{\alpha }_0{p}_0)}{p_0^{T}A{p}_0} \end{gathered}$$
然后迭代構造每一步的共軛向量：
$$\begin{gathered} {\alpha }_k通過精確線搜索獲得 \\ {p}_{k+1}={\beta }_{k+1}{p}_k+{\hat{p}}_{k+1} \\ {\beta }_{k+1}=\frac{p_k^{T}A?f(x_k+{\alpha }_k{p}_k)}{p_k^{T}A{p}_k} \end{gathered}$$
可以證明，上面的迭代出的共軛向量可以構成共軛向量組。

然后通過精確線搜索獲得${\alpha }_{k+1}$：
$${\alpha }_{k+1}=\frac{p_{k+1}^T{\hat{p}}_{k+1}}{p_{k+1}^{T}A{p}_{k+1}}$$

線性共軛梯度流程

給定$x_0$，通過梯度下降法獲得初始$p_0,{\alpha }_0$

迭代到第k次，判斷收斂條件，若不滿足，進入3；否則跳出循環

通過共軛梯度構造公式依次計算$x_{k+1},{\beta }_{k+1},p_{k+1},{\alpha }_{k+1}$，判斷收斂條件，若不滿足則回到2

補充：線性共軛梯度法的簡化

前面推導的時候，沒有用到線性條件$?f(x)=Ax?b$，這里可以進行簡化。首先給出簡化后的精確線搜索步長：
$$\begin{gathered} f^{\prime }(x_k+{\alpha }_k{p}_k)=p_k^T?f(x_k+{\alpha }_k{p}_k)=0 \\ \to p_k^T(A(x_k+{\alpha }_k{p}_k)?b)=0 \\ \to p_k^{T}A{x}_k+{\alpha }_k{p}_k^{T}A{p}_k=p_k^{T}b \\ \to {\alpha }_k=\frac{p_k^T(b?A{x}_k)}{p_k^{T}A{p}_k} \\ setb?A{x}_k=r_k,{\alpha }_k=\frac{r_k^T{p}_k}{p_k^{T}A{p}_k} \end{gathered}$$
然后構造共軛梯度向量：
$$\begin{gathered} p_{k+1}=?f(x_k+{\alpha }_k{p}_k)+{\beta }_{k+1}{p}_k \\ and{p}_k^{T}A{p}_{k+1}=0 \\ \to p_k^{T}A?f(x_k+{\alpha }_k{p}_k)+{\beta }_{k+1}{p}_k^{T}A{p}_k=0 \\ \to {\beta }_{k+1}{p}_k^{T}A{p}_k=?p_k^{T}A?f(x_k+{\alpha }_k{p}_k) \\ {\beta }_{k+1}=?\frac{p_k^{T}A?f(x_k+{\alpha }_k{p}_k)}{p_k^{T}A{p}_k} \\ =?\frac{p_k^{T}A(A{x}_{k+1}?b)}{p_k^{T}A{p}_k} \\ =\frac{r_{k+1}^{T}A{p}_k}{p_k^{T}A{p}_k} \end{gathered}$$

最后梳理一下：

初始化$k=0$，計算$x_0,p_0$

迭代第$k+1$輪，判斷收斂條件，不滿足時繼續循環

${\alpha }_k=\frac{r_k^T{p}_k}{p_k^{T}A{p}_k}$

$x_{k+1}=x_k+{\alpha }_k{p}_k$

$r_{k+1}=b?A{x}_{k+1}$

${\beta }_{k+1}=\frac{r_{k+1}^{T}A{p}_k}{p_k^{T}A{p}_k}$

$p_{k+1}=?r_{k+1}+{\beta }_{k+1}{p}_k$

$k=k+1$

總結

以上是生活随笔為你收集整理的数值计算之 共轭梯度法（1）线性共轭梯度法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。