11、DY 共軛梯度法的內(nèi)在性質(zhì)

這篇文章同樣出于戴彧虹 和 袁亞湘 老師之手势誊，我個人感覺證明很巧妙呜达。本文主要進一步分析 DY 共軛梯度法，在不特別給定線搜索和函數(shù)凸性的情況下粟耻，給出了 DY 共軛梯度法的內(nèi)在性質(zhì)查近，即是充分下降性對于大多數(shù)點列都成立。

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,\quad & k=1,\\ -g_k+\beta_k d_k, &k\ge 2,\end{cases}\tag{3}$
其中 $~g_k~$ 是迭代點 $~x_k~$ 處的梯度戈泼， $~\alpha_k~$ 是搜素步長， $~d_k~$ 是搜素方向赏僧， $~\beta_k~$ 為共軛參數(shù)大猛。
?? 不同的參數(shù) $~\beta_k~$ 決定不同的共軛梯度法。在前一篇文章淀零，我們主要介紹了由 戴彧虹 和 袁亞湘 提出的 DY 共軛梯度法胎署，其 $~\beta_k~$ 的參數(shù)形式如下
$\beta_k^{DY}=\frac{\Vert g_k\Vert^2}{d_{k-1}(g_k-g_{k-1})}\tag{4}$
表明了其它標準 Wolfe 線搜索下能夠建立全局收斂性，進一步窑滞，如果在強 Wolfe 線搜索下能夠保證其充分下降性琼牧。我們還討論了如果函數(shù) $~f(x)~$ 為嚴格凸函數(shù)（一致凸函數(shù)），能夠保證下降性（充分下降性）哀卫。
?? 在此巨坊，我想表明的是，通過以上對 DY 算法的認識還遠遠不夠此改，我們應(yīng)該更加深入討論 DY 共軛梯度法的內(nèi)在性質(zhì)趾撵，這些性質(zhì)并不依賴于線搜索的選擇和函數(shù)的凸性。最后我們利用這些性質(zhì)，構(gòu)造出幾種特殊的線搜索來建立全局收斂性占调。

2暂题、DY 共軛梯度法的內(nèi)在性質(zhì)
?? 為了嚴謹，我們都是假定
$g_k\neq 0,~~~\forall ~k\neq 1\tag{5}$
否則究珊，穩(wěn)定點我們已經(jīng)得到薪者，迭代算法就會終止。
?? 其次剿涮，我們定義兩個后面會用到的兩個量
$q_k=\frac{\Vert d_k\Vert^2}{(g_k^Td_k)^2}\tag{6}$
$r_k=-\frac{g_k^T d_k}{\Vert g_k\Vert^2}\tag{7}$
其中 $~q_k~$ 可看成一個反映方向 $~d_k~$ 長度的量言津， $~r_k~$ 則反映 $~d_k~$ 的下降程度。實際上取试，若 $~r_k>0~$ 悬槽，則 $~d_k~$ 是下降方向，若 $~r_k\ge c~$ 對某常數(shù) $~c~$ 成立瞬浓，則式 $~(7)~$ 表明 $~d_k~$ 是下降方向初婆。
?? 下面的這些東西，其實在上一篇文章的證明過程中也出現(xiàn)過猿棉，在此我們還是敘述一下
當 $~k\ge 2~$ 時烟逊， $~d_k=-g_k+\beta_k^{DY}d_{k-1}~$ ，兩端與 $~g_k~$ 做內(nèi)積铺根。
$g_k^T d_k=-\Vert g_k\Vert^2+\beta_k^{DY}g_k^T d_{k-1}=\Vert g_k\Vert^2\frac{g_{k-1}^T d_{k-1}}{d_{k-1}^T(g_k-g_{k-1})}=\beta_k^{DY}g_{k-1}^T d_{k-1}\tag{8}$
當 $~k\ge 2~$ 時宪躯， $~d_k+g_k=\beta_k d_{k-1}~$ ，兩端取模平方并移項位迂，可得
$\Vert d_k\Vert^2=\beta_k^2\Vert d_{k-1}\Vert^2-2g_k^Td_k-\Vert g_k\Vert^2$
將上式除以 $~(g_k^T d_k)^2~$ 访雪，并利用 $~(8)~$ 得
$\frac{\Vert d_k\Vert^2}{(g_k^T d_k)^2}=\frac{\Vert d_{k-1}\Vert^2}{(g_{k-1}^Td_{k-1})}-\frac{2}{g_k^T d_k}-\frac{\Vert g_k\Vert^2}{(g_k^T d_k)^2}\tag{9}$
利用 $~(6)~$ 和 $~(7)~$ 的定義，則有
$q_{k}=g_{k-1}+\frac{1}{\Vert g_k\Vert^2}\frac{2}{r_k}-\frac{1}{\Vert g_k\Vert^2}\frac{1}{r_k^2}\tag{10}$
因此若 $~r_k>0~$ 掂林，則式 $~(10)~$ 式右端的第二項將使 $~q_{k-1}~$ 增加臣缀，第三項將使得 $~q_{k-1}~$ 的值減小，它們關(guān)于 $~\frac{1}{r_k}~$ 的量級分別為一階和二階泻帮。同時考慮這兩項精置，不難看出當且僅當 $~r_k\ge\frac{1}{2}~$ 時， $~q_{k-1}~$ 增加锣杂；而當 $~r_k~$ 趨于零時脂倦， $~q_{k-1}~$ 將顯著減少。由于對所有的 $~k\ge 1~$ 元莫，都有 $~q_k\ge 0~$ 赖阻，我們便可以對 $~r_k~$ 的下界進行估計。
?? 我們先給出如下假定踱蠢，存在正常數(shù) $~\gamma~$ 和 $~\bar{\gamma}~$ 使得
$\gamma\le\Vert g_k\Vert\le\bar{\gamma},~~~\forall~ k\ge 1.\tag{11}$
**
定理1：考慮方法 $~(2)~$ 和 $~(3)~$ 火欧，其中 $~\beta_k~$ 由 $~(4)~$ 計算， $~d_k~$ 滿足 $~g_k^T d_k<0~$ 。若 $~(11)~$ 成立苇侵，則存在常數(shù) $~\delta_1~$ 赶盔， $~\delta_2~$ 和 $~\delta_3~$ ，使得下述關(guān)系式
$-g_k^T d_k\ge\frac{\delta_1}{\sqrt{k}}\tag{12}$
$\Vert d_k\Vert^2\ge\frac{\delta_2}{k}\tag{13}$
$r_k\ge\frac{\delta_3}{\sqrt{k}}\tag{14}$
對所有 $~k\ge 1~$ 都成立.

證明: 利用 $~r_1=1~$ 榆浓，對 $~(10)~$ 式求和于未，得
$q_k=\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}(\frac{2}{r_i}-\frac{1}{r_i^2})\tag{15}$
因為 $~q_k\ge 0~$ ，上式表明
$\frac{1}{\Vert g_k\Vert^2}(-\frac{2}{r_k}+\frac{1}{r_k^2})\le\sum_{i=1}^{k-1}\frac{1}{\Vert g_i\Vert^2}(\frac{2}{r_i}-\frac{1}{r_i^2})\tag{16}$
利用 $~(11)~$ 哀军、 $~(16)~$ 及關(guān)系
$\frac{2}{r_i}-\frac{1}{r_i^2}\le 1\tag{17}$
即得
$\frac{1}{r_k^2}-\frac{2}{r_k}-\frac{\bar{\gamma^2}}{\gamma^2}(k-1)\le 0\tag{18}$
從上式及 $~r_k>0~$ ，不難證得
$\frac{1}{r_k}\le 1+\sqrt{1+\frac{\bar{\gamma}^2}{\gamma^2}(k-1)}\le1+\frac{\bar{\gamma}}{\gamma}\sqrt{k}\le\frac{2\bar{\gamma}}{\gamma}\sqrt{k}\tag{19}$
因此對 $~(14)~$ 對 $~\delta_3=\frac{\gamma}{2\bar{\gamma}}~$ 打却，注意到
$-g_k^T d_k=\Vert g_k\Vert^2r_k\tag{20}$
以及
$\Vert d_k\Vert\ge\Vert g_k\Vert r_k\tag{21}$
即對關(guān)系式 $~(13)~$ 和 $~(14)~$ 中的 $~\delta_1=\delta_3\gamma^2~$ 和 $~\delta_2=\delta_3^2\gamma^2~$ 也成立杉适。

**注1****：在上面的定理中，關(guān)系式 $~(14)~$ 并不表明充分下降在每一步都成立柳击。雖然如此猿推，我們可以證明 DY 共軛梯度法的充分下降性質(zhì)對大部分點列都成立。

定理 2：考慮方法 $~(2)~$ 和 $~(3)~$ 捌肴，其中 $~\beta_k~$ 由 $~(4)~$ 計算蹬叭， $~d_k~$ 滿足 $~g_k^T d_k<0~$ ，若 $~(11)~$ 成立状知，則對任意的 $~p\in(0,1)~$ 秽五，存在正常數(shù) $~\delta_4~$ ， $~\delta_5~$ 乘盼， $~\delta_6~$ 逗鸣，使得對所有的 $~k\ge 1~$ 阅酪，關(guān)系式
$-g_i^T d_i\ge \delta_4\tag{22}$
$\Vert d_i\Vert^2\ge\delta_5\tag{23}$
以及
$r_i\ge\delta_6\tag{24}$
對 $~[1,k]~$ 中至少 $~[pk]~$ 個 $~i~$ 成立

證明： 對任意的 $~p\in (0,1)~$ ，我們選取 $~\delta_6>0~$ 瓣铣，使其滿足
$\delta^{'}\triangleq\frac{1}{\delta_6^2}-\frac{2}{\delta_6\gamma}\ge\frac{\bar{\gamma^2}p}{\gamma^2(1-p)}\tag{25}$
對此 $~\delta_6~$ 和任意的 $~k~$ ，定義集合
$I_k=\left\{i\in[1,k]:r_i\ge\delta_6\right\}\tag{26}$
并記 $~\vert I_k\vert~$ 為 $~I_k~$ 中元素的個數(shù)贷揽，利用 $~(10)~$ 棠笑、 $~(11)~$ 以及 $~q_k\ge 0~$ ，不難看出
$\sum_{i\in [1,k]\backslash I_k}(-\frac{2}{r_i}+\frac{1}{r_i^2})\le\frac{\bar{\gamma}^2}{\gamma^2}\sum_{i\in I_k}(\frac{2}{r_i}-\frac{1}{r_i^2})\tag{27}$
于是禽绪，由 $~(17)~$ 蓖救， $~(27)~$ 以及 $~I_k~$ 的定義可得
$\delta^{'}(k-\vert I_k\vert)\le\frac{\bar{\gamma}^2}{\gamma^2}\vert I_k\vert\tag{28}$
其中 $~\delta^{'}~$ 由 $~(25)~$ 給出，上式和 $~(25)~$ 表明了
$\vert I_k\vert\ge\frac{\delta^{'}\gamma^2}{\delta^{'}\gamma^2+\bar{\gamma}^2}k\ge p k\ge [pk]\tag{29}$
故對任意的 $~p\in (0,1)~$ 印屁，如果選取 $~\delta_6>0~$ 滿足 $~(25)~$ 藻糖、 $~\delta_4=\delta_6\gamma^2~$ ， $~\delta_5=\delta_6^2\gamma^2~$ 库车，則從 $~(11)~$ 巨柒， $~(20)~$ ， $~(21)~$ 和 $~(29)~$ 知，關(guān)系式 $~(22)-(24)~$ 至少對 $~[pk]~$ 個 $~i~$ 都成立洋满。

注2：上述證明證明過程晶乔，本人看了很久，奈何水平有限牺勾，感覺理解不了正罢。比如式 $~(25)~$ 的定義， $~(27)~$ 和 $~(28)~$ 的推導(dǎo)驻民，就不明白翻具，如果有人了解，還望不吝賜教回还。

3裆泳、DY 共軛梯度法在一般線搜索條件下的全局收斂性

現(xiàn)在設(shè)線搜索滿足如下較為一般的條件
$f_k-f_{k+1}\ge c\min\left\{-g_k^T d_k,\Vert d_k\Vert^2,q_k^{-1}\right\}\tag{30}$
其中 $~c>0~$ 為常數(shù)，而 $~q_k~$ 由 $~(6)~$ 式給出柠硕。因為對標準 Wolfe 線搜索可證明
$f_k-f_{k+1}\ge cq_k^{-1}\tag{31}$
對標準 Armijo 線搜索工禾， $~\alpha_k=\max \left\{\lambda^m:m\ge 0,m\in\mathbb{N}\right\}~$ 滿足下式
$f(x_k+\alpha_k d_k)-f(x_k)\le\sigma\alpha_k g_k^Td_k$
則有下式成立
$f_k-f_{k+1}\ge c\left\{-g_k^Td_k,q_k^{-1}\right\}\tag{32}$
對另一種 Armijo 型線搜索， $~\alpha_k=\max \left\{\lambda^m:m\ge 0,m\in\mathbb{N}\right\}~$ 滿足下式
$f(x_k+\alpha_k d_k)-f(x_k)\le-\delta\alpha_k^2 g_k^Td_k$
則有下式成立
$f_k-f_{k+1}\ge c\min\left\{\Vert d_k\Vert^2,q_k^{-1}\right\}\tag{33}$
其上： $~\lambda,\sigma\in(0,1)蝗柔，\delta>0~$

注：上面的 $~(31)~$ 其實是標準 Wolfe 顯然得出的結(jié)論闻葵，或許有對 Armijo 型線搜索不熟悉，可以私信交流 $~(32)~$ 和 $~(33)~$ 癣丧。以上的分析只是想說明槽畔，我們給出的線搜索 $~(30)~$ t條件很好滿足而已。

定理3： 設(shè)目標函數(shù) $~f(x)~$ 有下界胁编，導(dǎo)函數(shù) $~g(x)~$ 是 $~Lipschitz~$ 連續(xù)竟痰，考慮方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 由 $~(4)~$ 計算掏呼， $~d_k~$ 滿足 $~g_k^T d_k<0~$ 坏快，而步長因子 $~\alpha_k~$ 滿足 $~(30)~$ ，如果存在常數(shù) $~\bar{\gamma}>0~$ 憎夷，使得
$\Vert g_k\Vert\le\bar{\gamma},~~\forall ~k\ge 1 \tag{34}$
則方法在下述意義下是全局收斂的：
$\lim_{k\rightarrow\infty}\inf\Vert g_k\Vert=0\tag{35}$

證明： 對 $~(30)~$ 式求和莽鸿，并注意到 $~f(x)~$ 有下界，得
$\sum_{k\ge 1}\min\left\{-g_k^T d_k,\Vert d_k\Vert^2,q_k^{-1}\right\}\le+\infty\tag{36}$
現(xiàn)用反證法拾给，假設(shè) $~(35)~$ 不成立祥得，即存在常數(shù) $~\gamma>0~$ ，使得
$\Vert g_k\Vert\ge\gamma,~~\forall~k\ge1\tag{37}$
由 定理2 可知蒋得，關(guān)系式 $~(12)~$ 和 $~(13)~$ 對某正常數(shù) $~\delta_1~$ 和 $~\delta_2~$ 成立级及，此外，在 $~(15)~$ 中應(yīng)用 $~(17)~$ 和 $~(37)~$ 额衙，得
$q_k\le q_{k-1}+\frac{1}{\gamma^2}$
上式及 $~q_1=1~$ 表明了
$q_k^{-1}\ge\frac{\gamma^2}{k}\tag{38}$
于是利用 $~(12)~$ 饮焦、 $~(13)~$ 和 $~(38)~$ 怕吴，得到
$\sum_{k\ge 1}\min \left\{-g_k^T d_k,\Vert d_k\Vert^2,q_k^{-1}\right\}=+\infty$
上式和 $~(36)~$ 相矛盾，則表明 $~(35)~$ 式成立县踢。

4转绷、結(jié)束語
?? 其實上面的過程我也看了很久，也有一些不懂的地方硼啤，也都用注進行標記议经，之所以還要寫出來，也希望遇見一個研究無約束優(yōu)化特別是共軛梯度法的朋友谴返，能夠相互探討煞肾，相互學(xué)習(xí)吧。

?? 上面的內(nèi)容參考 戴彧虹 的文章
[1] New properties of a nonlinear conjugate gradient method. Numerische Matheematik, 89, 83-98.

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

人面猴
序言：七十年代末嗓袱，一起剝皮案震驚了整個濱河市籍救，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌索抓，老刑警劉巖钧忽，帶你破解...
沈念sama閱讀 218,525評論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件毯炮，死亡現(xiàn)場離奇詭異逼肯，居然都是意外死亡，警方通過查閱死者的電腦和手機桃煎，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,203評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門篮幢，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人为迈，你說我怎么就攤上這事三椿。” “怎么了葫辐？”我有些...
開封第一講書人閱讀 164,862評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵搜锰，是天一觀的道長。經(jīng)常有香客問我耿战，道長蛋叼，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,728評論 1贊 294
?港島之戀（遺憾婚禮）
正文為了忘掉前任剂陡，我火速辦了婚禮狈涮，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘鸭栖。我一直安慰自己歌馍，他們只是感情好，可當我...
茶點故事閱讀 67,743評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布晕鹊。她就那樣靜靜地躺著松却，像睡著了一般暴浦。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上玻褪，一...
開封第一講書人閱讀 51,590評論 1贊 305
城市分裂傳說
那天肉渴，我揣著相機與錄音，去河邊找鬼带射。笑死同规，一個胖子當著我的面吹牛，可吹牛的內(nèi)容都是我干的窟社。我是一名探鬼主播券勺，決...
沈念sama閱讀 40,330評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼灿里！你這毒婦竟也來了关炼？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,244評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤匣吊，失蹤者是張志新（化名）和其女友劉穎儒拂，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體色鸳，經(jīng)...
沈念sama閱讀 45,693評論 1贊 314
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡社痛，尸身上長有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
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留摔癣，地道東北人奴饮。一個月前我還...
沈念sama閱讀 48,191評論 3贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長得像择浊，于是被迫代替她去往敵國和親戴卜。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 44,955評論 2贊 355

11趋急、DY 共軛梯度法的內(nèi)在性質(zhì)

11、DY 共軛梯度法的內(nèi)在性質(zhì)

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