Wolfe線搜索下的全局收斂修正HS共軛梯度法

李雙安,朱志斌,楊柳笑,陳鳳華

(1.桂林電子科技大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院,廣西桂林 541004; 2.河南理工大學(xué)萬方科技學(xué)院,鄭州 451400)

Wolfe線搜索下的全局收斂修正HS共軛梯度法

李雙安1,朱志斌1,楊柳笑1,陳鳳華2

(1.桂林電子科技大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院,廣西桂林 541004; 2.河南理工大學(xué)萬方科技學(xué)院,鄭州 451400)

為解決大規(guī)模無約束優(yōu)化問題,基于Wolfe線搜索技術(shù),提出新的修正HS共軛梯度法。在水平集有界和梯度Lipschitz連續(xù)的條件下,證明新算法具有全局收斂性。數(shù)值實驗證實此算法有效可行。

無約束優(yōu)化;共軛梯度法;Wolfe線搜索;全局收斂性

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

其中f:Rn→R是一光滑非線性函數(shù),其梯度記為g(x)=?f(x)。

用共軛梯度法可有效解決大規(guī)模無約束優(yōu)化問題(1)。此方法具有運算簡便和占用存儲空間少的特點,相關(guān)研究可參考文獻(xiàn)[1-4]。求解問題(1)的共軛梯度法迭代公式為:

其中:αk＞0為搜索步長;dk為搜索方向;gk= g(xk);βk為更新參數(shù)。

共軛梯度法的關(guān)鍵是更新迭代參數(shù)βk的選取,不同的βk對應(yīng)不同的共軛梯度法。著名的βk計算公式有:

其中‖·‖為歐式范數(shù),yk-1=gk-gk-1。式(4)、(5)、(6)、(7)分別為FR、PRP、HS、DY共軛梯度法的迭代更新參數(shù),在某些線搜索下的全局收斂性已被廣泛研究,它們的收斂性和數(shù)值表現(xiàn)不盡相同。其中FR方法和DY方法具有良好的收斂性,而HS方法和PRP方法則數(shù)值性能優(yōu)良。采用精確線搜索的HS方法與PRP方法對一般的非凸函數(shù)不一定收斂。為此,建立一種新的修正HS算法,證明在Wolf線搜索下該算法的全局收斂性結(jié)果。改變HS共軛梯度法的更新參數(shù)βk,同時在保證算法的搜索方向始終是下降方向前提下,提出新搜索方向dk,得到一種新的修正HS共軛梯度法。在水平集有界和梯度Lipschitz連續(xù)的條件下,可證明此算法具有全局收斂性。通過Matlab編程測試,證實新算法具有良好的數(shù)值結(jié)果。

1 修正的HS共軛梯度法(MHSCG)

文獻(xiàn)[5]中,修正的佩里共軛梯度法更新參數(shù)為:

受文獻(xiàn)[5]更新參數(shù)βk的啟發(fā),提出新的參數(shù)βk為:

式(11)成立可保證式(10)的搜索方向在每一步迭代是下降方向,對確保算法的全局收斂性很重要。

修正的HS共軛梯度法(MHSCG)的算法步驟為:

1)初始點x0∈Rn,且0＜σ1＜σ2＜1,令k=0。

2)若‖gk‖=0,則終止,否則進(jìn)入下一步。

3)計算式(10)定義的搜索方向dk。

4)由Wolfe線搜索計算步長αk,

5)令xk+1=xk+αkdk。

6)置k∶=k+1,返回步驟2)。

2 全局收斂性分析

為保證全局收斂性,對問題(1)作如下基本假設(shè):

H1 水平集Ω={x∈Rnf(x)≤f(x0)}有界,即存在一常數(shù)A＞0滿足

H2 在Ω的某一鄰域N內(nèi),f可微且其梯度g是Lipschitz連續(xù),即存在一常數(shù)L＞0,滿足

由H1、H2可推得存在一常數(shù)m＞0,滿足

引理1 若H1、H2成立,則Wolfe線搜索是良定的。

證明 設(shè)φk(α)=f(xk+αdk)是關(guān)于α的函數(shù),由于φk(α)=f(xk+αdk)在α＞0時有下界且0＜σ1＜1,故射線φ(α)=f(xk)+σ1αdk與曲線φk(α)在α的正半軸上有交點。

記最小的交點為α′k,則

結(jié)合式(17),并利用0＜σ1＜σ2＜1及dk＜0,得

由式(9)、(16)及H2,有如下引理。

引理2 若H1、H2成立,序列{xk}由修正的HS共軛梯度法產(chǎn)生,則有

證畢。

一般而言,共軛梯度法只要執(zhí)行的線搜索滿足Wolfe條件(12)和(13),都具有下面引理3所述性質(zhì)[6],該性質(zhì)通常用來證明共軛梯度法全局收斂性。

引理3 若H1、H2成立,考慮任一共軛梯度法的迭代形式(2),其中dk滿足gTkdk＜0,且αk滿足Wolfe條件(12)和(13),則

顯然,將式(11)代入式(19),如下不等式成立:

下面對一致凸函數(shù)證明修正的HS共軛梯度法的全局收斂性。

定理1 若H1、H2成立,且f是一致凸函數(shù),即存在一常數(shù)η＞0滿足

{xk}由修正的HS共軛梯度法產(chǎn)生,則存在k,使得gk=0或‖gk‖=0。

由式(14)、(15)、(18)、(22),有

結(jié)合式(20),有

證畢。

3 數(shù)值實驗

為驗證MHSCG算法的有效性和穩(wěn)定性,通過Matlab編程對算法進(jìn)行數(shù)值實驗。運行環(huán)境為Windows 7,Intel(R)Pentium(R),內(nèi)存2 GB,CPU為2.13 GHz,測試環(huán)境為Matlab v7.8(R2009a)。數(shù)值實驗所用算例為:

其中x*為算例的最優(yōu)解。

數(shù)值實驗分為2組:第1組數(shù)值實驗針對算例1)用MHSCG算法與傳統(tǒng)的FR方法、PR方法以及文獻(xiàn)[7-8]提出的方法做對比;第2組數(shù)值實驗針對算例2)～6)測試MHSCG算法對不同維度算例的可行性和穩(wěn)定性。

實驗參數(shù)設(shè)置為:σ1=0.2,σ2=0.8,精確度ε＜10-8。算法終止準(zhǔn)則為以下二者之一:

1)‖gk‖＜ε;

2)I＞1000。

當(dāng)終止準(zhǔn)則2)出現(xiàn)時認(rèn)為該方法對此數(shù)值例子失效。第1組數(shù)值實驗結(jié)果見表1。

表1 算例1的對比測試結(jié)果Tab.1 Comparison of testing results for example 1

由表1的數(shù)值結(jié)果可知:MHSCG算法尋找算例1)的最優(yōu)解所需迭代步數(shù)顯著減少,優(yōu)勢明顯。第2組數(shù)值實驗結(jié)果見表2。

表2 算例2)～6)的測試結(jié)果Tab.2 Testing results for example 2)-6)

由表2可知,MHSCG算法對不同維度的算例能成功求得最優(yōu)解,且迭代次數(shù)較少,算法穩(wěn)定。

4 結(jié)束語

在傳統(tǒng)Hestenes-Stiefel(HS)共軛梯度法基礎(chǔ)上,提出一個新的參數(shù)βk計算公式,相應(yīng)提出新的搜索方向dk。在Wolfe線搜索下,證明此方法具有全局收斂性。通過Matlab編程測試,證實MHSCG算法在相同精度下,迭代步數(shù)顯著減少,適合解決不同維度問題。

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

[2] Yuan Yaxiang.Numerical Methods for Nonlinear Programming[M].Shanghai:Shanghai Scientific Technical Publishers,1993:152-209.

[3] Shi Zhenjun.Restricted PR conjugate gradient method and its global convergence[J].Advances in Mathematics,2002,31(1):47-55.

[4] Shi Zhenjun.Convergence of PRP method with new nonmonotone line search[J].Applied Mathematics and Computation,2006,181(1):423-431.

[5] Livieris I E,Pintelas P.Globally convergent modied Perry’s conjugate gradient method[J].Applied Mathematics and Computation,2012,218(18):9197-9207.

[6] Zoutendijk G.Nonlinear Programming[M]//Abadie J. Integer and Nonlinear Programming.Amsterdam:North Holland Press,1970:37-86.

[7] 房明磊,張聰,陳鳳華.一種新的Wolfe線搜索技術(shù)及全局收斂性[J].桂林電子科技大學(xué)學(xué)報,2008,28(1):62-65.

[8] 陳鳳華,張聰,房明磊.曲線搜索下的新的記憶擬牛頓法[J].廣西科學(xué),2008,15(3):254-256.

編輯:翁史振

見習(xí)編輯:陳汝偉

Globally convergent modified HSconjugate gradient method with Wolfe line searching

Li Shuang’an1,Zhu Zhibin1,Yang Liuxiao1,Chen Fenghua2
(1.School of Mathematics and Computational Science,Guilin University of Electronic Technology,Guilin 541004,China; 2.Wanfang Institute of Science and Technology,Henan Polytechnic University,Zhengzhou 451400,China)

Based on Wolfe line searching technology,a modified HS conjugate gradient method for large-scale unconstrained optimization problem is presented.When level set is bounded and gradient is Lipschitz continuous,the global convergence of the new method is proved.Numerical experiments show that the proposed algorithm is feasible and effective.

unconstrained optimization;conjugate gradient method;Wolfe line searching;global convergence

O224

A

1673-808X(2015)02-0162-04

2014-05-26

國家自然科學(xué)基金(11361018);廣西自然科學(xué)基金(2012GXSFFA060003);河南省教育廳科學(xué)技術(shù)研究重點項目(12B110011)

朱志斌(1974-),男,湖南雙峰人,教授,博士,研究方向為最優(yōu)化理論與算法。E-mail:zhuzb@guet.edu.cn

李雙安,朱志斌,楊柳笑,等.Wolfe線搜索下的全局收斂修正HS共軛梯度法[J].桂林電子科技大學(xué)學(xué)報,2015,35(2):162-165.