共軛梯度法（CG）詳解

這篇文章寫得不錯(cuò)，建議收藏。想要了解 CG，把它認(rèn)認(rèn)真真讀一遍，就很清楚了。

文章目錄

• • 共軛梯度法（CG）詳解
  • • 線性共軛梯度法
    • • 共軛方向
      • 共軛方向法
      • CG 方法
      • 收斂率
      • 預(yù)條件
    • 非線性共軛梯度法
    • • FR 方法
      • 其他非線性 CG
      • PR+ 方法
      • 重啟動(dòng)

之前寫過幾個(gè)關(guān)于共軛梯度法的注記，譬如：

• https://blog.csdn.net/lusongno1/article/details/78550803
• https://blog.csdn.net/lusongno1/article/details/68942821

但事實(shí)上很多人反應(yīng)，看得一頭霧水，基于此，本篇文章旨在對(duì)于共軛梯度方法從優(yōu)化的角度給一個(gè)干凈的描述。

線性共軛梯度法

線性共軛梯度方法是 Hestenes 和 Stiefel 在 20 世紀(jì) 50 年代提出來的的一個(gè)迭代方法，用于求解正定系數(shù)矩陣的線性系統(tǒng)。
假定 $A$ 是對(duì)稱正定的矩陣，求解線性方程組
$$Ax=b$$
等價(jià)于求解如下凸優(yōu)化問題：
$$\min ?(x)\equiv \frac{1}{2}{x}^{T}Ax?b^{T}x$$
該問題的梯度便是原線性系統(tǒng)的殘差，
$$??(x)=Ax?b\equiv r(x)$$
在 $x=x_k$ 點(diǎn)， $r_k=A{x}_k?b$。

共軛方向

定義 對(duì)于非零向量集合 $\left\{p_0,p_1,?,p_t\right\}$ 關(guān)于對(duì)稱正定矩陣 $A$ 是共軛的，若
$$p_i^{T}A{p}_j=0,\text{?for?all?}i\ne j.$$

容易證明，共軛向量之間是線性獨(dú)立的。

假設(shè)已經(jīng)有了一組共軛向量，我們把未知量表示為它們的線性組合 $x={\sum }_{i=1}^n{\alpha }^i{p}_i$，我們希望能夠?qū)ふ乙唤M系數(shù)，去極小化
$$?(x)=\sum _{i=1}^n\left(\frac{{\left({\alpha }^i\right)}^2}{2}{p}_i^{T}A{p}_i?{\alpha }^i{p}_i^{T}b\right)$$
求和中的每一項(xiàng)都是獨(dú)立的，極小化之，那么我們就可以得到
$${\alpha }^i=\frac{p_i^{T}b}{p_i^{T}A{p}_i}$$

通過共軛方向，把一個(gè) n 維問題，拆解成了 n 個(gè)一維問題。

從矩陣的角度來看這個(gè)問題，我們把自變量做一個(gè)變換，
$$\hat{x}=S^{?1}x$$
其中，$S$ 由共軛向量張成，
$$S=\left[p_0,p_1,?,p_{n?1}\right]$$
那么二次問題變?yōu)?#xff0c;
$$\widehat{?}(\hat{x})\equiv ?(S\hat{x})=\frac{1}{2}{\hat{x}}^T\left(S^{T}AS\right)\hat{x}?{\left(S^{T}b\right)}^T\hat{x}$$
由共軛性，我們知道矩陣 $S^{T}AS$ 是個(gè)對(duì)角矩陣，那么久變成了一個(gè)對(duì)角矩陣系數(shù)的極簡(jiǎn)方程。

共軛方向法

所謂的共軛方向法，就是給定初值點(diǎn) $x_0$ 和一組共軛方向，我們通過如下方式迭代更新 $x_k$：
$$x_{k+1}=x_k+{\alpha }_k{p}_k$$
$${\alpha }_k=?\frac{r_k^T{p}_k}{p_k^{T}A{p}_k}$$

1、這里的步長(zhǎng) ${\alpha }_k$ 是二次函數(shù) $?$ 沿著 $x_k+\alpha p_k$ 的一維的極小化，我們一般稱之為精確線搜索步長(zhǎng)。
2、理論上，精確線搜索方法至多 n 步收到到線性系統(tǒng)的解。忽略證明。

對(duì)于共軛方向法來說，有如下定理。

定理： $x_0\in {?}^n$ 是任意起點(diǎn)， $\left\{x_k\right\}$ 通過共軛方向法生成，那么
$$r_k^T{p}_i=0,\text{?for?}i=0,1,?,k?1,$$
且 $x_k$ 在集合
$$\left\{x\mid x=x_0+\mathrm{span}\left\{p_0,p_1,?,p_{k?1}\right\}\right\}.$$
上，關(guān)于 $?(x)=\frac{1}{2}{x}^{T}Ax?b^{T}x$ 的極小化。

CG 方法

共軛方向法的共軛方向如何得到呢？共軛梯度方法（Conjugate Gradient，CG）方法是一個(gè)特別的共軛方向法：它的共軛方向是在 $x_k$ 的迭代中一個(gè)一個(gè)生成出來的，并且 $p_k$ 的計(jì)算只用到 $p_{k?1}$。

它的思想在于，選取當(dāng)前共軛方向?yàn)樨?fù)梯度方向和前一個(gè)共軛方向的線性組合，
$$p_k=?r_k+{\beta }_k{p}_{k?1}$$
將其左乘 $p_{k?1}^{T}A$，由 $p_k$ 與 $p_{k?1}$ 的共軛性，可以得到組合系數(shù)：
$${\beta }_k=\frac{r_k^{T}A{p}_{k?1}}{p_{k?1}^{T}A{p}_{k?1}}$$
在這個(gè)過程中，選擇 $p_0$ 為 $x_0$ 處負(fù)梯度方向，結(jié)合前面的介紹，就可以得到線性共軛梯度方法。

注意到梯度和共軛方向的一些關(guān)系：
$$\begin{array}{rl}{r}_k^T{r}_i& =0,?i=0,?,k?1\\ \mathrm{span}\left\{r_0,r_1,?,r_k\right\}& =\mathrm{span}\left\{r_0,A{r}_0,?,A^k{r}_0\right\}\\ \mathrm{span}\left\{p_0,p_1,?,p_k\right\}& =\mathrm{span}\left\{r_0,A{r}_0,?,A^k{r}_0\right\}\\ p_k^{T}A{p}_i& =0,?i=0,1,?,k?1.\end{array}$$
通過一些簡(jiǎn)單的推導(dǎo)，替換掉 CG 算法中的一些表達(dá)，就得到了如下的 CG 方法的更加經(jīng)濟(jì)的實(shí)用形式，

收斂率

定義條件數(shù)：
$$\kappa (A)=\Vert A{\Vert }_2{\Vert A^{?1}\Vert }_2=\frac{{\lambda }_n}{{\lambda }_1}$$
那么，CG 的收斂率可以表達(dá)為：
$${\Vert x_k?x^{?}\Vert }_A\le 2{\left(\frac{\sqrt{\kappa (A)}?1}{\sqrt{\kappa (A)}+1}\right)}^k{\Vert x_0?x^{?}\Vert }_A$$

由表達(dá)式可以看出，當(dāng) $A$ 條件數(shù)很大的時(shí)候，前面的系數(shù)趨近于 1，收斂速度無法保證。

預(yù)條件

所謂的預(yù)條件，就是希望對(duì)矩陣 $A$ 做一個(gè)改造，改進(jìn)特征值分布，讓它的條件數(shù)小一些。

具體地，引入一個(gè)非奇異矩陣 $C$，做變量替換，
$$\hat{x}=Cx.$$
二次問題就變?yōu)榱?#xff0c;
$$\widehat{?}(\hat{x})=\frac{1}{2}{\hat{x}}^T{\left(C^{?T}A{C}^{?1}\right)}^{?1}\hat{x}?{\left(C^{?T}b\right)}^T\hat{x}$$
其對(duì)應(yīng)的線性系統(tǒng)是，
$$\left(C^{?T}A{C}^{?1}\right)\hat{x}=C^{?T}b$$
我們要做的，就是找一個(gè)逆比較好求的 $C$，使得 $C^{?T}A{C}^{?1}$ 特征值分布更集中。落實(shí)到實(shí)用算法上，得到：

注意到，這里沒有顯式用到 $C$，而是用到了
$$M=C^{T}C$$
性質(zhì)中的殘差的正交性表達(dá)也發(fā)生了改變，
$$r_i^T{M}^{?1}{r}_j=0\text{?for?all?}i\ne j$$

非線性共軛梯度法

求解非線性極小化問題：
$$\min f(x)$$

$f$ 此時(shí)是非線性函數(shù)。

FR 方法

相對(duì)于共軛梯度法，我們做兩點(diǎn)改動(dòng)：

• 對(duì)于步長(zhǎng) ${\alpha }_k$，我們需要采取一種線搜索方法沿著 $p_k$ 去逼近非線性目標(biāo)函數(shù) $f$ 的極小。（滿足所謂的強(qiáng) wolfe 條件的步長(zhǎng)）

• 殘差 $r$ 原來是線性 CG 方法的梯度，現(xiàn)在需要用 $f$ 的梯度來替代它。

那么我們就得到了第一個(gè)非線性共軛梯度法，它是 Fletcher 和 Reeves 在 20 世紀(jì) 60 年代搞的。

對(duì)于 FR 方法，如果某步的方向不太好或者步長(zhǎng)太小，那么下一步的方向和步長(zhǎng)也會(huì)很糟糕。

其他非線性 CG

除了 PR 方法，我們選取不同的組合系數(shù) $\beta$，就能得到不同的非線性 CG 方法。

PR 方法：
$${\beta }_{k+1}^{PR}=\frac{?f_{k+1}^T\left(?f_{k+1}??f_k\right)}{{\Vert ?f_k\Vert }^2}.$$

HS 方法：
$${\beta }_{k+1}^{HS}=\frac{?f_{k+1}^T\left(?f_{k+1}??f_k\right)}{{\left(?f_{k+1}??f_k\right)}^T{p}_k}$$

DY 方法：
$${\beta }_{k+1}^{DY}=\frac{?f_{k+1}^T?f_{k+1}}{{\left(?f_{k+1}??f_k\right)}^T{p}_k}$$

容易觀察到，這四種方法無非是兩個(gè)分子和兩個(gè)分母的四種組合。

我們指出以下幾點(diǎn)：

• DY 方法是我們所的戴彧虹和袁亞湘老師提出的。
• 對(duì)于 $f$ 是強(qiáng)凸的二次問題，若采用精確想搜索，那么 PR-CG 和 HS-CG 是一個(gè)東西。
• 數(shù)值實(shí)驗(yàn)表明，PR 更魯棒更有效。
• PR 方法其實(shí)就是在 FR 的基礎(chǔ)上，當(dāng)遇到前后兩步梯度變化比較小的壞條件的時(shí)候，重新開始梯度下降的 “重啟動(dòng)” 方法。
• PR 方法可能不收斂。

PR+ 方法

若要保證 $p_k$ 是下降方向，我們只需要為 PR 的 $\beta$ 進(jìn)行微調(diào)：
$${\beta }_{k+1}^{+}=\max \left\{{\beta }_{k+1}^{PR},0\right\}$$
稱之為 PR+ 方法。

重啟動(dòng)

一個(gè)重啟動(dòng)的方式是，每迭代 $n$ 步，就設(shè)置 ${\beta }_k=0$，即取迭代方向?yàn)樽钏傧陆捣较颉Ｖ貑?dòng)能抹掉一些舊的信息。但是這種重啟動(dòng)，沒有什么實(shí)際的意義，只能說是一種理論的貢獻(xiàn)。因?yàn)榇蟛糠智闆r下 $n$ 很大，可能不需要迭代多少個(gè) $n$ 步，差不多就達(dá)到了比較好的逼近解。

另外一個(gè)重新啟動(dòng)是基于前后兩步的梯度不正交的考慮，即當(dāng)遇到
$$\frac{\left|?f_k^T?f_{k?1}\right|}{{\Vert ?f_k\Vert }^2}\ge 0.1$$
我們進(jìn)行一個(gè)重啟動(dòng)。

總結(jié)

以上是生活随笔為你收集整理的共轭梯度法（CG）详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。