焦佳佳

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

其中R n是n維歐幾里得空間,f:Rn→R是一個連續(xù)可微的函數(shù).

眾所周知,共軛梯度法是求解該類問題的一種重要方法,它具有如下的迭代格式

其中αk是某種線搜索下的步長,dk滿足

其中βk是共軛參數(shù).不同的βk的取法會產(chǎn)生不同的共軛梯度法,常見的βk有如下定義:

對應的方法分別叫做FR(Fletcher-Revees),PRP(Polak-Ribiere-Polyak),HS(Hestenes-Stiefel),LS(Liu-Storey),CD(Conjugate Descent)和DY(Dai-Yuan)共軛梯度法.常用的線搜索有:Wolfe線搜索,強Wolfe線搜索,Armijo-type線搜索等,其中強Wolfe線搜索要求αk滿足

與其他共軛梯度法相比,PRP方法的數(shù)值表現(xiàn)是目前認為最好的方法之一,但該方法的收斂性不理想.研究發(fā)現(xiàn),PRP方法收斂性不好的原因在于它不具有充分下降性.充分下降性是指,對所有的k,不等式

成立,其中c為常數(shù).此性質(zhì)在收斂性分析中起著非常重要的作用.因此,許多學者都希望找到數(shù)值表現(xiàn)可與PRP相媲美同時性質(zhì)又比其好的方法.文獻[1]將標準的共軛梯度法迭代格式(3)推廣為如下譜共軛梯度形式

文獻[2]取βk=βkFR,在式(7)下滿足gkTdk=-‖gk‖2.本文受這些思想的啟發(fā),基于譜共軛梯度法迭代式(7),考慮如下參數(shù)

結(jié)合強Wolfe線搜索建立新的譜共軛梯度算法,并分析了算法的全局收斂.

NLS算法:

初始步:給定x0∈Rn,ε≥0.令d0=-g0,k=0.

第一步:若 ‖g0‖ ≤ε,則停止;

第二步:求出滿足強Wolfe線搜索的步長αk;

第三步:計算xk+1=xk+αkdk,若 ‖gk+1‖ ≤ε,則停止;

第四步:通過式(5),(6),求得dk+1;令k=k+1,轉(zhuǎn)第二步.

為了討論新算法的全局收斂性,假定目標函數(shù)滿足如下基本假設:

(A)水平集Ω={x∈Rnf( x)≤f( x0)}有下界,即存在常數(shù)a＞0,使得 x≤a.

(B)f在水平集Ω的一個鄰域Ν內(nèi)連續(xù)可微,且其梯度g滿足Lipschitz連續(xù),即存在正的常數(shù)L,使得

顯然,在上述假設下,存在某個正的常數(shù)Γ,使得

引理1 若假設(A)和(B)成立,考慮方法(2)和(3),其中dk滿足強Wolfe線搜索(4)和(5),則有

引理2 在假設(A)和(B)成立的條件下,序列 xk{}由算法NLS產(chǎn)生,αk滿足強Wolfe線搜索(4)和(5).如果存在一個常數(shù)ε＞0使得對所有的k＞0有‖gk‖≥ε,則存在正的常數(shù)C和M使得

和

成立.

引理3 若假設(A)和(B)成立,序列 xk{}由算法NLS產(chǎn)生,αk滿足強Wolfe線搜索(4)和(5).如果存在一個常數(shù)ε＞0使得對所有的k＞0有‖gk‖≥ε,則有

該引理的證明類似于文獻[3]中引理3.2的證明,所以在此處省略該引理的證明.

定理1 若假設(A)和(B)成立,序列 xk{}由算法NLS產(chǎn)生,αk滿足強Wolfe線搜索(4)和(5),則有

該定理的證明類似于文獻[3]中定理3.1的證明,所以在此處省略該算法的全局收斂性證明.

對于求解大規(guī)模的無約束優(yōu)化問題,給出了一種修正的譜LS共軛梯度法,該方法不依賴任何線搜索具有充分下降性,并且在強Wolfe線搜索下證明了該方法的全局收斂性.

參考文獻:

[1]Birgin E G,Martimez J M.A spectral conjugate gradient method for unconstrained optimization[J].Appl Math Optim,2001,43:117128.

[2]Zhang Li,Zhou Weijun,Li Donghui.Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search[J].Numerische Mathematik,2006(104):561-572.

[3]Dai Zhifeng.Global convergence of some modified PRP nonlinear conjugate gradient methods[J].Optim Lett,2011(5):615-630.

[4]Zhang Li,Zhou Weijun,Li Donghui.A descent modified Polar-Ribiere and Polyak conjugate gradient method with armijo-type line search[J].IMA Journal of Numerical Analysis,2006(26):629-640.

[5]孟繼東,杜學武.Armijo型線搜索一個修正LS共軛梯度法的全局收斂性[J].重慶師范大學學報,2012,11:6-8.

[6]Zhang Li,Zhou W,Li D.Some descent three-term conjugate gradient methods and their global convergence[J].Optim.Methods Softw,2007(22):697-711.

[7]張霞.一個新的光滑低階精確罰函數(shù)[J].重慶工商大學學報:自然科學版,2013,30(8):36-38.

[8]李曉峰.修正的LS共軛梯度法在Armijo型線搜索下的全局收斂性[J].太原科技大學學報,2010,31(4):317-319.