8、CD 共軛梯度法

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

1惭聂、簡介

??共軛梯度法是求解無約束優(yōu)化問題常用的方法
$\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}$
從上式中的第一個不等式及 $~\sigma_2<1~$ 狼纬，則 $~d_k~$ 必為下降方向，并使得充分下降條件
$-g_k^T d_k\ge c\Vert g_k\Vert^2\tag{8}$
對某常數(shù) $~c>0~$ 成立
??在充分下降條件 (8) 和 Zoutendijk 條件成立的情況下骂际，如果
$\sum_{k\ge 1}\frac{\Vert g_k\Vert^t}{\Vert d_k\Vert^2}=\infty\tag{9}$
對某 $~t\in [0,4]~$ 成立疗琉，不難推知收斂關(guān)系式 $~\lim\inf\Vert g_k\Vert=0~$ 成立。 $\color{red}{對于采取強(qiáng) \rm{Wolfe} 非精確線搜素的共軛梯度法歉铝，下節(jié)我們給出一個一般性的定理盈简。}$
$\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}$
這時弃衍，類似于 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}$
對某常數(shù) $~c>0~$ 成立坚俗，故如果方法不收斂镜盯，序列 $~\left\{\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4}\right\}~$ 最多線性增長，從而 (9) 式成立猖败，則 $~\lim\inf\Vert g_k\Vert=0~$ 速缆，導(dǎo)致矛盾，因此當(dāng)參數(shù) $~\sigma_1~$ 和 $~\sigma_2~$ 滿足 (10) 式時恩闻，共軛下降法必全局收斂艺糜。

2、收斂性分析

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

注：上述定理證明很簡單理茎，類似于 FR 共軛梯度法黑界，不在此給出。對于 $~\sigma_1\ge 1~$ 和 $~\sigma_2>0~$ 皂林，戴彧虹表明 CD 共軛梯度法會不收斂朗鸠，因此 (10) 中的條件對于 CD 共軛梯度法的收斂性是充分必要的。這些反例的構(gòu)造挺難的式撼，我個人感覺不是很重要童社，也不想給出。

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.

最后編輯于：2022.08.11 18:59:07

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末扰楼，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子美浦，更是在濱河造成了極大的恐慌弦赖，老刑警劉巖，帶你破解...
沈念sama閱讀 218,525評論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件浦辨，死亡現(xiàn)場離奇詭異蹬竖，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,203評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門币厕，熙熙樓的掌柜王于貴愁眉苦臉地迎上來列另，“玉大人，你說我怎么就攤上這事旦装∫逞茫” “怎么了？”我有些...
開封第一講書人閱讀 164,862評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵阴绢，是天一觀的道長店乐。經(jīng)常有香客問我，道長呻袭，這世上最難降的妖魔是什么眨八？我笑而不...
開封第一講書人閱讀 58,728評論 1贊 294
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮左电，結(jié)果婚禮上廉侧，老公的妹妹穿的比我還像新娘。我一直安慰自己券腔，他們只是感情好伏穆，可當(dāng)我...
茶點故事閱讀 67,743評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著纷纫，像睡著了一般。火紅的嫁衣襯著肌膚如雪陪腌。梳的紋絲不亂的頭發(fā)上辱魁，一...
開封第一講書人閱讀 51,590評論 1贊 305
城市分裂傳說
那天，我揣著相機(jī)與錄音诗鸭，去河邊找鬼染簇。笑死，一個胖子當(dāng)著我的面吹牛强岸，可吹牛的內(nèi)容都是我干的锻弓。我是一名探鬼主播，決...
沈念sama閱讀 40,330評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼蝌箍，長吁一口氣：“原來是場噩夢啊……” “哼青灼！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起妓盲，我...
開封第一講書人閱讀 39,244評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤杂拨，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后悯衬，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體弹沽，經(jīng)...
沈念sama閱讀 45,693評論 1贊 314
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,885評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了策橘。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片炸渡。...
茶點故事閱讀 40,001評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖丽已，靈堂內(nèi)的尸體忽然破棺而出偶摔，到底是詐尸還是另有隱情，我是刑警寧澤促脉，帶...
沈念sama閱讀 35,723評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布辰斋，位于F島的核電站，受9級特大地震影響瘸味，放射性物質(zhì)發(fā)生泄漏宫仗。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,343評論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一旁仿、第九天我趴在偏房一處隱蔽的房頂上張望藕夫。院中可真熱鬧，春花似錦枯冈、人聲如沸毅贮。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,919評論 0贊 22
一樁弒父案尘奏，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽滩褥。三九已至，卻和暖如春炫加，著一層夾襖步出監(jiān)牢的瞬間瑰煎，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,042評論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工俗孝，沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留酒甸，地道東北人。一個月前我還...
沈念sama閱讀 48,191評論 3贊 370
代替公主和親
正文我出身青樓赋铝，卻偏偏與公主長得像插勤，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子革骨，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 44,955評論 2贊 355

8迂曲、CD 共軛梯度法

8、CD 共軛梯度法

1惭聂、簡介

2、收斂性分析

3著隆、參考文獻(xiàn)

推薦閱讀更多精彩內(nèi)容