一種修正下降的非線性共軛梯度法

張小讓,朱志斌,邢明燕

一種修正下降的非線性共軛梯度法

張小讓,朱志斌,邢明燕

(桂林電子科技大學數學與計算科學學院,廣西桂林 541004)

為求解無約束優化問題,基于MMHS方法和DY方法,提出了一種修正下降的非線性共軛梯度法。在Armijo線搜索下,該算法是全局收斂的。數值實驗證明了該算法的有效性和可行性。

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

令f:Rn→R連續可微,并考慮如下無約束優化問題:

用共軛梯度法[1]求解問題(1),迭代步為:

其中:αk(αk≥0)為步長,由一定的線搜索決定;dk為搜索方向,滿足(g(x))Tdk＜0。并定義:

其中βk為參數。MHS[2]方法和DY[3]方法是2個熟悉的共軛梯度法,其參數βk定義為:

其中:gk=g(xk);g(x)=▽f(x);yk-1=gk-gk-1;sk=xk+1-xk;‖?‖為歐幾里得范數。另外,Armijo線搜索[4]是普遍采用的精確線搜索,給定δ∈(0, 1),ρ∈(0,1),并令

滿足線搜索條件:

易知,若采用Armijo精確線搜索,可得到一個下降方向。為此,構建一個新的共軛梯度法,證明在Armijo線搜索下算法的全局收斂性。

1 修正的非線性共軛梯度法

文獻[5]對MFR方法[6-8]和MPRP方法[6-10]進行處理,給出了一種由DY和MMHS[2]所構造的共軛梯度法,稱為修正的非線性共軛梯度法(簡稱DYMMHS方法)。用此共軛梯度法解決問題(1),在DY方法和MMHS方法中,搜索方向dk分別為:

其中:

基于式(11),給出一種共軛梯度法,并稱為DYMMHS方法。

算法1(DY-MMHS方法) 給定常數δ,λ∈(0,1),ρ∈(0,1),ε＞0,選擇一個初始點x0∈Rn,并令k∶=0。

1)通過式(11)計算dk,當‖gk‖＜ε時,中止。

2)用Armijo精確線搜索計算步長αk。

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

4)令k∶=k+1,并返回步驟1)。

DY-MMHS方法可產生目標函數的充分下降方向,此性質獨立于線搜索,且算法具有二次終止性。

2 收斂性分析

通過分析算法的全局收斂性,做出如下基本假設[]。

假設1 1)水平集W={x∈Rnf(x)≤f(x0)}有界。

2)存在W的某個鄰域N,使得f在該鄰域上連續可微,且導數滿足Lipschitz條件,即存在常數L＞0,使得

由假設1易得該算法收斂性定理。

定理1 設假設1成立,{xk}由DY-MMHS方法產生,則有

證明(反證法) 假設結論不成立,則存在常數ε＞0,使得‖gk‖≥ε,?k。

由Armijo線搜索及假設1可得

另由Armijo線搜索,對充分大的k∈K,有

結合微積分中值定理及Lipschitz條件(12),存在tk∈(0,1),使得

其中,L＞0為梯度g的Lipschitz常數。因此,對于充分大的k∈K,有

這與式(14)矛盾,因此假設不成立,故結論成立。證畢。

以上結果表明,DY-MMHS方法在Armijo線搜索下是全局收斂的。

3 數值實驗

通過Matlab編程進行數值實驗以驗證MMHSDY算法的有效性和穩定性。運行環境為Windows 7,Intel Pentium,內存2 GB,CPU 2.50 GHz,測試環境為Matlab v8.1(R2013a)。x0為初始點,xk為末點。數值實驗的算例為:

例1 f(x)=(x1-2)2+0.04/(-x21/4-x22+ 1)+(x1-2x2+1)2/0.2+(x2-1)2,x0=(1,1), xk=(1.795 4,1.377 9)。

例2 f(x)=4(x1-5)2+(x2-6)2,x0=(1, 1),xk=(5.000 0,6.000 0)。

例3 f(x)=(1.5-x1(1-x2))2+(2.25-x1(1-x22))2+(2.625-x1(1-x32))2,x0=(1,1), xk=(3.000 0,0.500 0)。

例4 f(x)=(x2-x21)2+(1-x1)2,x0= (-1.2,1),xk=(1,1)。

例5 f(x)=(x21+x2-11)2+(x1+x22-7)2, x0=(1,1),xk=(3.000 0,2.000 0)。

例6 f(x)=(x2-x21)2+100(1-x1)2,x0= (-1.2,1),xk=(1,1)。

令參數δ=0.001,ρ=0.5,λ=0.1。對于測試問題,‖gk‖為DY-MMHS算法的梯度范數,k為迭代步。終止條件為‖gk‖≤10-6。表1為DYMMHS算法實驗結果,從表1可看出,對于所有算例,算法效果很好,其結果也很精確,同時消耗的時間也很少。

表1 DY-MMHS算法實驗結果Tab.1 The numerical results of DY-MMHS method

4 結束語

在傳統共軛梯度法基礎上,將DY方法和MMHS方法結合在一起,尋求一種新的共軛梯度法,從而達到預想的結果。該算法的靈感來源于文獻[5],采用的是Armijo線搜索。實驗結果表明,算法在一定的條件下是收斂的。

[1] 袁亞湘,孫文瑜.最優化理論與方法[M].北京:科學出版社,2007:183-199.

[2] 張麗.求解最優化問題的非線性共軛梯度法[D].長沙:湖南大學,2006:34-39.

[3] 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.

[4] 李董輝,童小嬌,萬中.數值最優化算法與理論[M].北京:科技出版社,2010:1-91.

[5] Tao Y.A class of descent nonlinear conjugate gradient methods[C]//2013 Fourth International Conference on Digital Manufacturing&Automation(ICDMA).IEEE Computer Society,2013:14-16.

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

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

[8] Polak E,Ribière G.Note sur la convergence de méthodes de directions conjuguées[J].Rev franaise Information recherche Opérationnelle,1969,(16):35-43.

[9] 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(4):561-572.

[10] Zhang Li,Zhou Weijun,Li Donghui.A descent modified Polak-Ribiere-Polyak conjugate gradient method and its global convergence[J].Ima Journal of Numerical Analysis,2006,26(4):629-640.

編輯:梁王歡

A modified descent nonlinear conjugate gradient method

Zhang Xiaorang,Zhu Zhibin,Xing Mingyan
(School of Mathematics and Computational Science,Guilin University of Electronic Technology,Guilin 541004,China)

To solve unconstrained optimization problem,based on DY method and MMHS method,a modified descent conjugate gradient method is presented.When Armijo line searching is used,the method is globally convergent.Numerical experiments show that the proposed method is effective and feasible.

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

O224

A

1673-808X(2015)05-0424-03

2015-03-26

國家自然科學基金(11361018);廣西自然科學基金(2014GXNSFFA118001);桂林市科學研究與技術開發計劃(20140127-2)

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

張小讓,朱志斌,邢明燕.一種修正下降的非線性共軛梯度法[J].桂林電子科技大學學報,2015,35(5):424-426.