8、CD 共軛梯度法

??前面介紹了 FR 共軛梯度法，給出了其他不同線搜素下的全局收斂性。本節(jié)將講述 CD 共軛梯度法，與 FR 的性質(zhì)相類似，有了前面的基礎(chǔ)，所以收斂性的證明很簡(jiǎn)單。
?? 1987 年，F(xiàn)letcher^{[1]} 提出了 CD 共軛梯度法，也被稱為共軛下降法。這種算法的獨(dú)特優(yōu)點(diǎn)在于使用強(qiáng) Wolfe 條件，CD 共軛梯度法顯然滿足充分下降性，顯然對(duì)于 FR 共軛梯度法這是不能辦到的。

1、簡(jiǎn)介

??共軛梯度法是求解無(wú)約束優(yōu)化問(wèn)題常用的方法
\min_{x\in\mathbb{R}^n}~f(x)\tag{1}
其一般的迭代格式為
x_{k+1}=x_k+\alpha_k d_k\tag{2}
d_k=\begin{cases}-g_k,&k=1,\\-g_k+\beta_k d_{k-1},&k\ge2,\end{cases}\tag{3}
其中~\beta_k~是參數(shù)。不同的~\beta_k~決定不同的共軛梯度法。
??1987 年，F(xiàn)letcher^{[1]}提出了 CD 共軛梯度法，其形式為
\beta_k=\frac{\Vert g_k\Vert^2}{-g_{k-1}^Td_{k-1}}\tag{4}
我們考慮推廣的 Wolfe 線搜素，其條件為
f(x_k)-f(x_k+\alpha_kd_k)\ge -\rho\alpha_kg_k^T d_k\tag{5}
\sigma_1g_k^T d_k\le g(x_k+\alpha_k d_k)^T d_k\le-\sigma_2g_k^T d_k\tag{6}
其中參數(shù)~0<\rho<\sigma_1<1~以及~0\le\sigma_2<1~。顯然，如果~\sigma_1=\sigma_2~，則上述搜素條件就是強(qiáng) Wolfe 條件，由 (3) 和 (4)，知
-g_k^T d_k=\Vert g_k\Vert^2(1+\frac{g_k^Td_{k-1}}{g_{k-1}^T d_{k-1}})
利用上式和 (6) 式，得
1-\sigma_2\le\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\le 1+\sigma_1\tag{7}
從上式中的第一個(gè)不等式及~\sigma_2<1~，則~d_k~必為下降方向，并使得充分下降條件
-g_k^T d_k\ge c\Vert g_k\Vert^2\tag{8}
對(duì)某常數(shù)~c>0~成立
??在充分下降條件 (8) 和 Zoutendijk 條件成立的情況下，如果
\sum_{k\ge 1}\frac{\Vert g_k\Vert^t}{\Vert d_k\Vert^2}=\infty\tag{9}
對(duì)某~t\in [0,4]~成立，不難推知收斂關(guān)系式~\lim\inf\Vert g_k\Vert=0~成立。\color{red}{對(duì)于采取強(qiáng) \rm{Wolfe} 非精確線搜素的共軛梯度法，下節(jié)我們給出一個(gè)一般性的定理。}
\color{red}{該定理表明，只要搜素方向下降，即}
\color{red}{g_k^T d_k<0,~~\forall~k\ge 1}
\color{red}{則 ~(9)~即可保證形如 (2) 和 (3) 方法的收斂性。這一結(jié)果并不需要方向 ~\rm{d_k}~是充分下降條件，而且適用于一般的共軛梯度法。 }
??設(shè)線搜素條件 (5) 和 (6) 中的參數(shù)滿足
\sigma_1<1,~~~\sigma_2=0\tag{10}
根據(jù)~\beta_k^{FR}=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}~和 (4) 式及 (7) 式，不難看出
0\le\beta^{CD}\le\beta_k^{FR}
這時(shí)，類似于 FR 的收斂性，可證明
\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4}\le c\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}
對(duì)某常數(shù)~c>0~成立，故如果方法不收斂，序列~\left\{\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4}\right\}~最多線性增長(zhǎng)，從而 (9) 式成立，則~\lim\inf\Vert g_k\Vert=0~，導(dǎo)致矛盾，因此當(dāng)參數(shù)~\sigma_1~和~\sigma_2~滿足 (10) 式時(shí)，共軛下降法必全局收斂。

2、收斂性分析

定理：設(shè)目標(biāo)函數(shù)~f(x)~下方有界，導(dǎo)數(shù)~\rm{Lipschitz}~連續(xù)，考慮 CD 共軛梯度法~\rm{(2)-(4)}~，其中步長(zhǎng)因子~\alpha_k~滿足推廣的 \rm{Wolfe}線搜素~\rm{(5)-(6)}~。如果~\sigma_1<1~且~\sigma_2=0~，則有~\lim\inf\Vert g_k\Vert=0~。

注：上述定理證明很簡(jiǎn)單，類似于 FR 共軛梯度法，不在此給出。對(duì)于~\sigma_1\ge 1~和~\sigma_2>0~，戴彧虹表明 CD 共軛梯度法會(huì)不收斂，因此 (10) 中的條件對(duì)于 CD 共軛梯度法的收斂性是充分必要的。這些反例的構(gòu)造挺難的，我個(gè)人感覺(jué)不是很重要，也不想給出。

3、參考文獻(xiàn)

[1] Fletcher R. Practical methods of optimization, vol I: unconstrained optimization[M]. New York: John Wiley and Sons, 1987.
[2] 戴彧虹. 非線性共軛梯度法[M]. 科學(xué)出版社, 2000.

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容