6、FR 共軛梯度法在廣義線搜索下的收斂性

??在前面，我們介紹了 FR 共軛梯度法在精確線搜索，強(qiáng) Wolfe 線搜索和推廣的 Wolfe 線搜索下的收斂性。本節(jié)，將介紹 FR 共軛梯度法在廣義 Wolfe 線搜索 和 廣義 Armijo 線搜索下的收斂性。廣義線搜索的本質(zhì)是在迭代的過程中搜索方向不一定是下降方向，若是上升方向，我們?nèi)∑浞捶较蛩阉?。與標(biāo)準(zhǔn)線搜索~\alpha_k>0~不同，廣義線搜索是在直線~\left\{x_k+\alpha_k d_k:~\alpha\in\mathbb{R}^1 \right\}~進(jìn)行搜素。

1、簡(jiǎn)介

??共軛梯度法是求解無約束優(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~決定不同的共軛梯度法。
??1964 年，F(xiàn)letcher 和 Reeves^{[1]} 首次提出了解決非線性函數(shù)的共軛梯度法，我們稱為 FR 共軛梯度法，其形式為
\beta_k=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}\tag{4}

2、廣義線搜索

??接下來我們介紹一下廣義線搜索
步 1：計(jì)算~g_k^T d_k~的值
步 2：若~g_k^T d_k=0~，令~\alpha_k=0~，返回；
???否則，令~p_k=\rm{sign}(-g_k^T d_k)d_k~。
步 3：沿方向~\lambda>0~作標(biāo)準(zhǔn)線搜索，得到步長~\lambda>0~
步 4：令~\alpha_k=\rm{sign}(-g_k^T d_k)p_k~，返回。

??對(duì)于上面，若~g_k^T d_k<0~，則廣義線搜索就是標(biāo)準(zhǔn)線搜索；若~g_k^T d_k>0~，即~d_k~是上升方向，則我們沿~d_k~進(jìn)行標(biāo)準(zhǔn)線搜索；若~g_k^T d_k==0~，則~\alpha_k=0~，因g_{k+1}=g_k~及~g_{k}^T d_k=0~，我們有
g_{k+1}^T d_{k+1}=-\Vert g_{k+1}\Vert^2+\beta_k g_{k+1}^T d_k=-\Vert g_{k+1}\Vert^2
可見下一個(gè)搜素方向~d_{k+1}~是下降方向， FR 方法仍可繼續(xù)下去。因此，討論廣義線搜素是有必要的。有了上面的鋪墊，我們現(xiàn)在來具體介紹兩種線搜索，廣義的 Wolfe 線搜索和廣義 Armijo 線搜索。
??廣義 Wolfe 線搜索： 將步 3 改為如下，選擇~\lambda_k>0~，其中~0<\rho<\sigma<1~
f(x_k+\lambda_k p_k)-f(x_k)\le\rho\lambda_k g_k^T p_k
g(x_k+\lambda_k p_k)^Tp_k\ge\sigma g_k^T p_k
??廣義 Armijo 線搜索： 將步 3 改為如下，選擇~\lambda_k>0~，其中~\lambda\in(0,1),~\rho\in(0,1)~且~S=\left\{0,1,2,\dots\right\}~
\lambda_k=\lambda^m
m=\min\left\{m\in S:f(x)\right\}
m=\min\left\{m\in S:f(x_k+\lambda_k p_k)-f(x_k)\le\rho\lambda_k g_k^T p_k\right\}

3、收斂性證明

假定 ：(1) 函數(shù)~f(x)~水平集~\Omega=\left\{x\in\mathbb{R}^n:~f(x)\le f(x_1)\right\}~有下界 (2) 梯度函數(shù)~g(x)~是 Lipchitz 連續(xù)，即存在~L>0~使得
\Vert g(x)-g(y)\Vert\le L\Vert x-y\Vert,~~\forall~x,y\in \Omega
引理 2：假定~x_1~是 假定 的起點(diǎn)，考慮形如 (2) 的任意點(diǎn)列，其中~d_k~是任意方向，步長~\alpha_k~滿足廣義 Wolfe 線搜索，則
\sum_{k\ge 1,\Vert d_k\Vert\neq0}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}<\infty
證明：首先廣義 Wolfe 線搜索可以等價(jià)于
f(x_k)-f(x_k+\alpha_k d_k)\ge -\rho\alpha_k g_k^T d_k\ge 0\tag{1}
g(x_k+\alpha_k d_k)^T d_kg_k^T d_k\le\sigma(g_k^T d_k)^2\tag{2}
由 (1) 可知
\sum_{k\ge 1}\vert \alpha_k g_k^T d_k\vert<\infty\tag{3}
從 (2) 中可以得到
g_k^T d_k[g(x_k+\alpha_k d-k)-g(x_k)]^T d_k\le-(1-\sigma)(g_k^T d_k)^2
利用上式可知
\vert [g(x_k+\alpha_k d_k)-g(x_k)]^Td_k\vert\ge(1-\sigma)\vert g_k^T d_k\vert
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=~g(x)~" alt="~g(x)~" mathimg="1">是~\Omega~上的 Lipschitz 常數(shù)，則有
\vert \alpha_k \vert L \Vert d_k\Vert^2\ge (1-\sigma)\vert g_k^T d_k\vert\tag{4}
利用 (3) 和 (4)，則命題得證。

引理 3：假定~x_1~是 假定 的起點(diǎn)，考慮形如 (2) 的任意點(diǎn)列，其中~d_k~是任意方向，步長~\alpha_k~滿足廣義 Armijo 線搜索，定義~N_1(k)=\left\{k\in Z^+:\vert a_k\vert=1\right\}~和~Z_2(k)=\left\{k\in Z^+:\vert a_k\vert\in(0,1)\right\}~，其中~Z_k~是所有正整數(shù)集合。則有
\lim\sum_{i\in N_1(k)}\vert g_i^T d_i\vert<\infty
\lim\sum_{i\in N_2(k)}\frac{(g_i^T d_i)^2}{\Vert d_i\Vert^2}<\infty
注：我們假定對(duì)于任意的~k~都有~g_k\neq 0~，故~d_k\neq 0~。因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=~d_k%3D0~" alt="~d_k=0~" mathimg="1">，則~d_{k+1}~為最速下降方向。

引理 4：我們首先假定
t_k=\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4},~~~r_k=-\frac{g_k^T d_k}{\Vert g_k\Vert^2}
對(duì)于 FR 共軛梯度法 (2)-(4)，對(duì)于任意的~k~都有
t_k=-\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}+\sum_{i=1}^k\frac{2r_i}{\Vert g_i\Vert^2}
證明：因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=~d_1%3D-g_1~" alt="~d_1=-g_1~" mathimg="1">，結(jié)論對(duì)~k=1~顯然成立。當(dāng)~k\ge 2~時(shí)，有
\Vert d_i\Vert^2=\beta_i^2\Vert d_{i-1}\Vert^2-\Vert g_i\Vert^2-2g_i^T d_i
將上式除以~\Vert g_i\Vert^4~，并利用定義。
t_i=t_{i-1}-\frac{1}{\Vert g_i\Vert^2}+\frac{2r_i}{\Vert g_i\Vert^2}
歸納遞推
t_k=t_1-\sum_{i=2}^k\frac{1}{\Vert g_i\Vert^2}+\sum_{i=2}^k\frac{2r_i}{\Vert g_i\Vert^2}
利用~t_1=\frac{1}{\Vert g_1\Vert^2}~和~r_1=1~，利用上式，很顯然可證得結(jié)論。

引理 5：設(shè)~l>0~，c~為常數(shù)。如果正項(xiàng)級(jí)數(shù)~\left\{a_i\right\}~對(duì)所有的~k~都成立
\sum_{i=1}^ka_i\ge lk+c
則有
\sum_{i\ge 1}\frac{a_i^2}{i}=\infty
\sum_{k\ge 1}\frac{a_k^2}{\sum_{i=1}^ka_i}=\infty
注：這個(gè) 引理 的證明可以參考文獻(xiàn) [1]

定理 1：假定~x_1~是 假定 的起點(diǎn)，考慮形如 (2) 的任意點(diǎn)列，其中步長~\alpha_k~滿足廣義 Wolfe 線搜索或者廣義 Armijo 線搜索，若
\sum_{k\ge 1}r_k^2=\infty
則有~\lim\inf\Vert g_k\Vert=0~

注 1：由前面的文章可知，如果線搜索是強(qiáng) Wolfe 線搜索，且~\sigma<\frac{1}{2}~，則存在常數(shù)~c>0~，使得
r_k\ge c,~~\forall~k\ge 1
注 2：由前面的文章可知，如果線搜索是推廣的 Wolfe 線搜索，若~\sigma_1+\sigma_2\le 1~，則有
r_k+r_{k+1}\ge c
因此充分下降對(duì)于相鄰的兩次迭代至少一次成立

注 3：如果 假定 成立且 水平集有界，若~\lim\inf \Vert g_k\Vert\neq 0~，則有
\sum_{i=1}^kr_i\ge ck
以上的式子表明充分下降對(duì)任意~k~次的平均成立，我們依然可以通過構(gòu)造矛盾，得出收斂性

\color{red}{顯然定理~1~ 中的條件要比注 1，2，3中的條件要弱，至于定理 ~6~的證明可參考后面文獻(xiàn)。}

推論 1：假定~x_1~是假定的起點(diǎn)，考慮 FR 共軛梯度法 (2)、(3)、和 (4)，若~\alpha_k~是由廣義強(qiáng) Wolfe 線搜索，其中~0<\rho<\sigma<1~，我們有~\lim\inf\Vert g_k\Vert=0~。

定理 2：假定~x_1~是假定的起點(diǎn)，考慮 FR 共軛梯度法 (2)、(3)、和 (4)，若~\alpha_k~是由廣義 Wolfe 線搜索或者是廣義 Armijo 線搜索，若
\sum_{k\ge1}\frac{1}{\Vert g_k\Vert^2}=\infty
則
~\lim\inf\Vert g_k\Vert=0~
注：這個(gè)定理我們也不加以證明，具體過程參考后面的文獻(xiàn)

推論 2：假定~x_1~是假定的起點(diǎn)，考慮 FR 共軛梯度法 (2)、(3)、和 (4)，若~\alpha_k~是由廣義 Wolfe 線搜索或者是廣義 Armijo 線搜索，若~f(x)~水平集有界，我們就有~\lim\inf\Vert g_k\Vert=0~

推論 3：假定~x_1~是假定的起點(diǎn)，考慮 FR 共軛梯度法 (2)、(3)、和 (4)，若~\alpha_k~是由廣義 Wolfe 線搜索或者是廣義 Armijo 線搜索，若
~\sum_{k\ge 1}\Vert x_{k+1}-x_k\Vert<\infty~
則
~\lim\inf\Vert g_k\Vert=0~
證明：利用 柯西不等式 和條件，我們有
\sum_{i=1}^k\Vert x_{k+1}-x_k\Vert\le c\sqrt{k}
其中~c=(\sum_{i=1}^{\infty}\Vert x_{k+1}-x_k\Vert^2)^{\frac{1}{2}}~
由于
\Vert g_{k+1}\Vert-\Vert g_k\Vert\le\Vert g_{k+1}-g_k\Vert\le L\Vert x_{k+1}-x_k\Vert
利用上遞推和前面關(guān)系，我們可知
\sum_{k\ge 1}\frac{1}{\Vert g_k\Vert^2}=\infty

4、結(jié)束語

??以上便是 FR 共軛梯度法在廣義 線搜索下的收斂性，包括廣義 Wolfe 和廣義 Armijo 線搜索。其中具體的定理的證明并未給出，可以參考如下文獻(xiàn)。

[1] Pu D, Yu W. On the convergence properties of the DFP algorithms, Annals of Operations Research, 1990, 24: 175.
[2] 戴彧虹, 袁亞湘. 廣義 Wolfe 線搜索下 Fletcher-Reeves 方法的收斂性. 高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào)，1996，142-148.
[3] Dai Y H. Further insight into the convergence of the Fletcher-Reeves method. 1999, Science in China, 905-916.

最后編輯于 ：
?著作權(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)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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

  • ??今天，應(yīng)該是正式研究共軛梯度法的開始。如果只是運(yùn)用共軛梯度法，而不去了解其算法的內(nèi)在含義，這也不是我在《簡(jiǎn)書》...
    多情劍客無情劍yu閱讀 3,456評(píng)論 0贊 3
  • 1 共軛方向的定義 對(duì)于正定二次函數(shù)，其中是對(duì)角陣，對(duì)角元均為正數(shù)，這種情況下函數(shù)關(guān)于原點(diǎn)中心對(duì)稱，每列由一...
    HarmoniaLeo閱讀 4,264評(píng)論 0贊 2
  • ??上節(jié)我們研究了線性共軛梯度法，線性共軛梯度法的研究對(duì)象是二次函數(shù)，且采取的線搜索為精確線搜索。為此可以產(chǎn)生共軛...
    多情劍客無情劍yu閱讀 2,099評(píng)論 0贊 3
  • 摘抄：https://www.cnblogs.com/shixiangwan/p/7532830.html[htt...
    taobao閱讀 1,155評(píng)論 0贊 4
  • 共軛梯度法及其淺顯分析 更多內(nèi)容請(qǐng)關(guān)注我的個(gè)人博客浩源小站 背景 無處不在的線性方程組,昭示著一個(gè)優(yōu)秀的算法能帶來...
    HaoYuan_He閱讀 9,728評(píng)論 1贊 9

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