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

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

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

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

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

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

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

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

考慮無約束優化問題

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

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

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

共軛梯度法的關鍵是更新迭代參數βk的選取,不同的βk對應不同的共軛梯度法。著名的βk計算公式有:

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

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

文獻[5]中,修正的佩里共軛梯度法更新參數為:

受文獻[5]更新參數βk的啟發,提出新的參數βk為:

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

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

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

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

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

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

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

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

2 全局收斂性分析

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

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

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

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

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

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

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

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

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

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

證畢。

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

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

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

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

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

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

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

結合式(20),有

證畢。

3 數值實驗

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

其中x*為算例的最優解。

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

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

1)‖gk‖＜ε;

2)I＞1000。

當終止準則2)出現時認為該方法對此數值例子失效。第1組數值實驗結果見表1。

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

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

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

由表2可知,MHSCG算法對不同維度的算例能成功求得最優解,且迭代次數較少,算法穩定。

4 結束語

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

[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線搜索技術及全局收斂性[J].桂林電子科技大學學報,2008,28(1):62-65.

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

編輯:翁史振

見習編輯:陳汝偉

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

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

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

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