4、非線性共軛梯度法的研究

??上節(jié)我們研究了線性共軛梯度法，線性共軛梯度法的研究對(duì)象是二次函數(shù)，且采取的線搜索為精確線搜索。為此可以產(chǎn)生共軛向量組，具有二次終止性。所謂的二次終止性，并不是迭代兩次就終止，而是對(duì)于二次函數(shù)且采取精確線搜索能夠有限步終止?；诙魏瘮?shù)的良好性質(zhì)，我們將推廣到一般函數(shù)，采用一般線搜索。實(shí)際計(jì)算中，發(fā)現(xiàn)方法是有效的。便有了非線性共軛梯度法，在不引起混淆的情況下，非線性共軛梯度法也被稱為線性共軛梯度法。
??對(duì)共軛梯度法的研究主要集中在參數(shù)~\beta_k~的選擇，混合共軛梯度法，多項(xiàng)共軛梯度法和譜共軛梯度法等方面。

1、前言

??共軛梯度法是無約束優(yōu)化方法，主要解決如下問題
\min_{x\mathbb{R}^n}~f(x)\tag{1}
解決問題 (1)，我們采用是線搜索的迭代方法，即
x_{k+1}=x_k+\alpha_k d_k\tag{2}
其中~d_k~是搜索方向，~\alpha_k~是搜索步長，無論是混合共軛梯度法，譜共軛梯度法或者是多項(xiàng)共軛梯度法，只是方向~d_k~不同。

2、經(jīng)典共軛參數(shù)~\beta_k~的選擇

??一般地，共軛梯度法的搜索方向?yàn)?br> d_k=\begin{cases}-g_k,&k=1,\\ -g_k+\beta_k d_{k-1},&k\ge2. \end{cases}
1952 年，Hestenes 和 stiefel^{[1]}在線性共軛梯度法中提出
\beta_k^{HS}=\frac{g_k^T(g_k-g_{k-1})}{d_{k-1}^T(g_k-g_{k-1})}
1964 年，F(xiàn)letcher 和 Reeves^{[2]}首次提出了非線性共軛梯度法
\beta_k^{FR}=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}
1969 年，Polak , Ribiere^{[3]} 和 Polyak^{[4]} 提出
\beta_k^{PRP}=\frac{g_k^T(g_k-g_{k-1})}{\Vert g_{k-1}\Vert^2}
1987 年，F(xiàn)letcher^{[5]} 提出
\beta_k^{CD}=\frac{\Vert g_k\Vert^2}{-g_{k-1}^Td_{k-1}}
1991 年，Liu 和 Storey^{[6]} 提出
\beta_k^{LS}=\frac{g_k^T(g_k-g_{k-1})}{-g_{k-1}^Td_{k-1}}
1998 年，戴彧虹 和 袁亞湘^{[7]} 提出
\beta_k^{DY}=\frac{\Vert g_k\Vert^2}{d_{k-1}^T(g_k-g_{k-1})}
2001年，戴彧虹 和 Liao^{[8]} 提出
\beta_k^{DL}=\frac{g_k^T(g_k-g_{k-1}-ts_{k-1})}{d_{k-1}^T(g_k-g_{k-1})}
其中~t> 0~，s_{k-1}=x_k-x_{k-1}.
2005 年，Hager 和 Zhang^{[9]} 提出
\beta_k^{HZ}=\frac{g_k^T(y_{k-1}-2d_{k-1}\frac{\Vert y_{k-1}\Vert^2}{d_{k-1}^Ty_{k-1}})}{d_{k-1}^Ty_{k-1}}
其中~y_{k-1}=g_k-g_{k-1}~

??以上是八種經(jīng)典的共軛梯度法，其收斂性會(huì)在后面詳細(xì)介紹。

3、混合共軛梯度法

??為了利用各種基本共軛梯度法的不同優(yōu)點(diǎn)，許多學(xué)者采用了不同共軛梯度法的巧妙組合。

Gilbert 和 Nocedal^{[10]}為保證算法的收斂性和具有較好的數(shù)值表現(xiàn)，取
\beta_k=\begin{cases} &-\beta_k^{FR},&~若~\beta_k^{PRP}<-\beta_k^{FR}\\ &\beta_k^{PRP},&~若~\vert \beta_k^{PRP}\vert\le\beta_k^{FR}\\ &\beta_k^{FR},&~若~\beta_k^{PRP}>\beta_k^{FR} \end{cases}
戴雨虹 和 袁亞湘^{[11]} 提出了混合 DY 和 CD 共軛梯度法
\beta_k=\frac{\Vert g_k\Vert^2}{\max \left\{d_{k-1}^T(g_k-g_{k-1}),-g_{k-1}^Td_{k-1} \right\}}
焦寶聰，陳蘭平 和 潘翠英^{[12]} 提出混合 DY 和 FR 共軛梯度法
\beta_k=\begin{cases} &\beta_k^{DY},~&若~g_k^T d_{k-1}\ge \Vert g_{k-1}\Vert^2\\ &\beta_k^{FR},~&否則 \end{cases}
??以上只是列出幾種混合梯度法而已，具體他們有什么性質(zhì)，收斂性的證明，后面會(huì)有更加全面的介紹。

4、多項(xiàng)項(xiàng)共軛梯度法

?? 基本的共軛梯度法是負(fù)梯度方向與前一搜索方向的組合，許多學(xué)者在此基礎(chǔ)上，研究了負(fù)梯度、前一搜索方向或位移、梯度差的各種形式，得到了多項(xiàng)共軛梯度法。多項(xiàng)共軛梯度法中最主要的形式還是三項(xiàng)共軛梯度法。

2006 年，張麗，周偉軍，李董輝^{[13]}提出了改進(jìn)的 PRP 共軛梯度法，得到了如下的三項(xiàng)共軛梯度法
d_k=\begin{cases} &-g_k,&~k=1,\\ &-g_k+\beta_k^{PRP}d_{k-1}-\frac{g_k^T d_{k-1}}{\Vert g_{k-1}\Vert^2}y_{k-1},&~k\ge 2. \end{cases}
2011 年，Narushima，Yabe 和 Ford^{[14]}得到了一般的三項(xiàng)共軛梯度法
d_k=\begin{cases} &-g_k,&k=1,或~g_k^Tp_k=0,\\ &-g_k+\beta_k d_{k-1}-\beta_k\frac{g_k^T d_{k-1}}{g_k^Tp_k}p_k,&其他情形， \end{cases}
其中~p_k~為任意向量
同年，Andrei^{[15]} 將 PRP 公式改進(jìn)為
d_k=-\frac{y_{k-1}^Ts_{k-1}}{\Vert g_{k-1}\Vert^2}+\frac{y_{k-1}^Tg_k}{\Vert g_{k-1}\Vert^2}s_{k-1}-\frac{g_k^Ts_{k-1}}{\Vert g_{k-1}\Vert^2}y_{k-1}
其中~s_{k-1}=x_k-x_{k-1},~y_{k-1}=g_k-g_{k-1}~.

5、譜共軛梯度法

??譜共軛梯度法是由譜梯度法和共軛梯度法發(fā)展而來。譜梯度法又稱 BB 算法，最早是由 Barzilai 和 Borwein^{[16]} 于 1988 年為求解無約束優(yōu)化問題 (1) 提出來的。BB 方法的主要思想是在最小二乘意義下，生成能夠逼近目標(biāo)函數(shù) Hesse 矩陣的逆矩陣，其迭代具有以下形式
x_{k+1}=x_k-\alpha_k d_k
其中
\alpha_k=\frac{(x_k-x_{k-1})^T(x_k-x_{k-1})}{(x_k-x_{k-1})^T(g_k-g_{k-1})}
BB 方法可以看成是最速下降法的改進(jìn)，優(yōu)點(diǎn)是它的數(shù)值表現(xiàn)遠(yuǎn)遠(yuǎn)好于最速下降法。
??2001 年，Birgin 和 Martinez^{[17]} 將譜梯度和共軛梯度相結(jié)合，提出了譜共軛梯度法，其搜索方向如下
d_k=\begin{cases} &-g_k,&~k=1,\\ &-\theta_kg_k+\beta_k d_{k-1},&~k\ge 2,\tag{1} \end{cases}
其中
\theta_k=\frac{s_{k-1}^Ts_{k-1}}{s_{k-1}^Ty_{k-1}}
\beta_k=\frac{g_k^T(\theta_ky_{k-1}-s_{k-1})}{d_{k-1}^Ty_{k-1}}
y_{k-1}=g_k-g_{k-1},~~s_{k-1}=x_k-x_{k-1}
我們把 (1) 的方法稱為譜共軛梯度法，但是上式的譜共軛梯度法不能保證是下降算法。
??張麗, 周偉軍^{[18]}提出一種譜共軛梯度法
d_k=\begin{cases} &-g_k,&k=1,\\ &-(1+\beta_k\frac{g_k^T d_k}{\Vert g_k\Vert^2})g_k+\beta_k d_{k-1},&k\ge 2, \end{cases}

6、結(jié)束語

\color{red}{以上的內(nèi)容只是簡單的介紹共軛梯度法，后面將會(huì)對(duì)共軛梯度法作進(jìn)一步學(xué)習(xí)}，

7、參考文獻(xiàn)

[1] Hestenes M R, Stiefel E. Method of conjugate geadient for linear equations[J]. Research of the National Bureau of Standards, 1952, 49(6): 409-436
[2] Flecher R, Reeves C. Fuction minimization by conjugate gradient gradients[J]. Computer Journal, 1964 7(2): 149-154.
[3] Polak E, Ribiere G. Note surla convergence de directions conjugate[J]. Rev Fr Inform Rech Oper, 1969, 16(3): 35-43.
[4] Polyak B T. The conjugate gradient method in extreme problems. USSR Comput Math Phys, 1969, 9(1): 94-112.
[5] Fletcher R. Practical methods of optimization, vol I: unconstrained optimization[M]. New York: John Wiley and Sons, 1987.
[6] Liu Y, Storey C. Efficient generalized conjugate gradient algorithms, I. Theory[J]. J Optim Theorey Appl, 1991, 69(1): 129-137.
[7] Dai Y H, Yuan Y X. A nonlinear conjugate gradient method with a strong global convergence property. SIAM J Optim, 1999, 10(1): 177-182.
[8] Dai Y H, Liao L Z. New conjugacy conditions and related nonlinear conjugate gradient methods[J]. Applied Mathematics and Optimization, 2001, 43 : 87-101.
[9] Hager W W, Zhang H C. A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 2005, 1(16) : 170-192.
[10] Gilbert J C, Nocedal J. Global convergence proerties of conjugate gradient methods for optimization[J]. SIAM Journal on Optimization, 1992, 2, 21-42.
[11] Dai Y H, Yuan Y X. Some properties of a new conjugate gradient methods[J]. Advances in Nonlinear Programming. 1998, 12, 251-262.
[12] 焦寶聰，陳蘭平，潘翠英. Goldstein 線搜索下混合共軛梯度法的全局收斂性[J]. 計(jì)算數(shù)學(xué), 2007,2(29): 137-146.
[13] Zhang L, Zhou W J, LI D H. A descent modified Polak_Ribiere-Polak gradient method and its global convergence[J]. IMA Journal of Numerical Analysis, 2006, 26: 629-640.
[14] Yasushi N, Hiroshi Y, John A F. A three-term conjugate gradient method with sufficient descent property for unconstrined optimization[J]. 2011,
[15] Andrei N. Amodified Polak-Ribiere-Polyak conjugate gradient algorithm for unconstrained optimization. Optimization, 60(12), 1457-1471.
[16] Barzilai J, Borwein M J. Two-point step size gradient methods[J]. IMA Journal of Numerical Analysis. 1988, 1(8): 141-148.
[17] Birgin E G, Martinez J M. A spectural conjugate gradeint method for unconstrained optimization[J]. 2001, 2(42): 117-128.
[18] Zhang L, Zhou W J. Two descent hybrid conjugate gradient methods for optimization[J]. Journal of Computation and Applied Mathematics, 2008, 251-264.

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

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

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