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

張小讓,朱志斌,邢明燕

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

張小讓,朱志斌,邢明燕

(桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,廣西桂林 541004)

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

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

令f:Rn→R連續(xù)可微,并考慮如下無(wú)約束優(yōu)化問(wèn)題:

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

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

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

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

滿足線搜索條件:

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

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

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

其中:

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

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

1)通過(guò)式(11)計(jì)算dk,當(dāng)‖gk‖＜ε時(shí),中止。

2)用Armijo精確線搜索計(jì)算步長(zhǎng)αk。

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

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

DY-MMHS方法可產(chǎn)生目標(biāo)函數(shù)的充分下降方向,此性質(zhì)獨(dú)立于線搜索,且算法具有二次終止性。

2 收斂性分析

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

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

2)存在W的某個(gè)鄰域N,使得f在該鄰域上連續(xù)可微,且導(dǎo)數(shù)滿足Lipschitz條件,即存在常數(shù)L＞0,使得

由假設(shè)1易得該算法收斂性定理。

定理1 設(shè)假設(shè)1成立,{xk}由DY-MMHS方法產(chǎn)生,則有

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

由Armijo線搜索及假設(shè)1可得

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

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

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

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

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

3 數(shù)值實(shí)驗(yàn)

通過(guò)Matlab編程進(jìn)行數(shù)值實(shí)驗(yàn)以驗(yàn)證MMHSDY算法的有效性和穩(wěn)定性。運(yùn)行環(huán)境為Windows 7,Intel Pentium,內(nèi)存2 GB,CPU 2.50 GHz,測(cè)試環(huán)境為Matlab v8.1(R2013a)。x0為初始點(diǎn),xk為末點(diǎn)。數(shù)值實(shí)驗(yàn)的算例為:

例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)。

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

表1 DY-MMHS算法實(shí)驗(yàn)結(jié)果Tab.1 The numerical results of DY-MMHS method

4 結(jié)束語(yǔ)

在傳統(tǒng)共軛梯度法基礎(chǔ)上,將DY方法和MMHS方法結(jié)合在一起,尋求一種新的共軛梯度法,從而達(dá)到預(yù)想的結(jié)果。該算法的靈感來(lái)源于文獻(xiàn)[5],采用的是Armijo線搜索。實(shí)驗(yàn)結(jié)果表明,算法在一定的條件下是收斂的。

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

[2] 張麗.求解最優(yōu)化問(wèn)題的非線性共軛梯度法[D].長(zhǎng)沙:湖南大學(xué),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] 李董輝,童小嬌,萬(wàn)中.數(shù)值最優(yōu)化算法與理論[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

國(guó)家自然科學(xué)基金(11361018);廣西自然科學(xué)基金(2014GXNSFFA118001);桂林市科學(xué)研究與技術(shù)開發(fā)計(jì)劃(20140127-2)

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

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