張 鵬

考慮無約束優(yōu)化問題

其中f:Rn→R是連續(xù)可微的函數(shù).共軛梯度法因為迭代簡單存儲量小,因此常被用來求解具有問題(1)形式的大規(guī)模優(yōu)化問題.共軛梯度法的一般迭代格式為

其中αk是由線搜索確定的步長,搜索方向dk滿足

βk是共軛參數(shù),βk的不同取法對應于不同的非線性共軛梯度法.著名的共軛梯度法有1964年Fletcher和Reeves提出的FR方法[1],1969年Polar-Ribiere和Polyak分別獨立提出的PRP方法[2,3],1952年Hestenes和Stiefel提出的HS方法[4],1999年Dai和Yuan提出的DY方法[5],βk分別由下式給出

其中,‖·‖為歐幾里得范數(shù),yk-1=gk-gk-1.

在共軛梯度法的許多理論分析和數(shù)值實現(xiàn)中,常常采用非精確線搜索如強Wolfe線搜索.強Wolfe線搜索要求步長αk滿足

其中0＜δ≤σ＜1.

Al-Baali[6]證明了當強Wolfe線搜索參數(shù)σ被限制在時FR方法是全局收斂的.Liu等[7]將Al-Baali的結果推廣到σ=.Zhang[8]提出一種修正的PRP方法,其中βk被定義為

并證明了NPRP在強_Wolfe線搜索下的充分下降性和全局收斂性.最近,Dai等[9]提出一種修正的NPRP方法 (記為:DPRP方法),βk被定義為

證明了DPRP方法不依賴線搜索而具有充分下降性,且對Armijo線搜索和Wolfe線搜索具有全局收斂性.受Zhang[8]和Dai[9]的啟發(fā),這里構造一類如下的修正FR方法,共軛梯度參數(shù)βk具有如下形式

其中μ＞1.當目標函數(shù)是嚴格凸二次函數(shù)并采用精確線搜索時,MFR退化為經典的FR方法.可以證明新方法不依賴線搜索,具有充分下降性且在強Wolfe線搜索下具有全局收斂性.

1 MFR算法

Step 0 給定常數(shù)σ∈(0,1),δ∈(0,σ),ε≥0,選取初始點x0∈Rn,計算d0=-g(x0),置k=0.

Step 1 如果‖gk‖∞≤ε,則算法終止.

Step 2 計算αk＞0滿足強Wolfe線搜索 (4)-(5).

Step 3 令xk+1=xk+αkdk,gk+1=g(xk+1).如果‖gk+1‖∞≤ε,則算法終止.

Step 4 由式 (3),(6)計算dk+1,置k=k+1,轉Step 2.

2 MFR算法的收斂性

假設

(A)目標函數(shù)f(x)在水平集L={x∈Rn∣f(x)≤f(x0)}上有下界,其中x0∈Rn為算法初始點.

(B)目標函數(shù)f(x)在水平集L的一個領域N內連續(xù)可微,且其梯度函數(shù)g滿足Lipschitz條件,即存在常數(shù)l＞0,使 ‖g(x)-g(y)‖ ≤l‖x-y‖,?x,y∈L.

引理1 βkMFR滿足0≤βkMFR≤βkFR.

證 由βkMFR的表達式(6)知

引理2 考慮具有式(2)和 (3)的迭代方法,其中βk=βkMFR,則對任意的線搜索有

證 由βkMFR的表達式(6),有

因此

由引理1和文獻[10]中的定理3.2可以直接得到下面的定理.

定理 若假設(A)(B)成立,MFR算法中步長αk滿足強Wolfe條件(4)和(5),參數(shù)0＜δ＜σ＜=0.

參考文獻:

[1]Fletcher R,Reeves C M.Function minimization by conjugate gradients[J].The Computer Journal,1964,7(2):149-154.

[2]Polak E,Ribiere G.Note sur la convergence de methodes de directions conjuguees[J].ESAIM:Mathematical Modelling and Numerical Analysis-Modélisation Mathematique et Analyse Numerique,1969,3(R1):35-43.

[3]Polyak B T.The conjugate gradient method in extremal problems[J].USSR Computational Mathematics and Mathematical Physics,1969,9(4):94-112.

[4]Hestenes M R,Stiefel E.Methods of conjugate gradients for solving linear systems[M].Washington,DC:National Bureau of Standards,1952:409-436.

[5]Dai Y H,Yuan Y.A nonlinear conjugate gradient method with a strong global convergence property[J].SIAM Journal on Optimization,1999,10(1):177-182.

[6]Al-Baali M.Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J].IMA Journal of Numerical Analysis,1985,5(1):121-124.

[7]Liu G H,Han J Y,Yin H X.Global convergence of the Fletcher-Reeves algorithm with inexact linesearch[J].Applied Mathematics-A Journal of Chinese Universities,1995,10(1):75-82.

[8]Zhang L.An improved Wei-Yao-Liu nonlinear conjugate gradient method for optimization computation[J].Applied Mathematics and Computation,2009,215(6):2269-2274.

[9]Dai Z,Wen F.Another improved Wei-Yao-Liu nonlinear conjugate gradient method with sufficient descent property[J].Applied Mathematics and Computation,2012,218(14):7421-7430.

[10]Gilbert J C,Nocedal J.Global convergence properties of conjugate gradient methods for optimization[J].SIAM Journal on optimization,1992,2(1):21-42.