一種新的求解無約束規(guī)劃的共軛梯度法

關(guān)　哲，于憲偉

(渤海大學(xué) 數(shù)理學(xué)院，遼寧 錦州 121000)

?

一種新的求解無約束規(guī)劃的共軛梯度法

關(guān)哲，于憲偉*

(渤海大學(xué) 數(shù)理學(xué)院，遼寧 錦州 121000)

摘要：研究無約束優(yōu)化問題的共軛梯度法，推導(dǎo)出一種新的共軛梯度法，算法在新Wolfe線搜索條件下具有充分下降性與全局收斂性.

關(guān)鍵詞：共軛梯度法；無約束優(yōu)化；全局收斂性；Wolfe線搜索

共軛梯度法是求解無約束優(yōu)化問題的重要方法之一，基于其算法簡單，存儲量小的特點，常用于求解大規(guī)模優(yōu)化問題.

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

(1)

其中f:Rn→R連續(xù)可微，對于為問題(1)的共軛梯度法，一般采用如下的迭代格式：

(2)

(3)

其中：gk=f(xk)是f在xk處的梯度，αk是由線性搜索產(chǎn)生的步長，βk是標(biāo)量，由αk和βk的選取不同，可以產(chǎn)生不同的共軛梯度法.常用的共軛梯度法有：FR算法[1]、PRP算法[2-3]、HS算法[4]、DY算法[5]、LS算法[6]、CD算法[7]，參數(shù)公式分別為：

此外還有許多學(xué)者對共軛梯度法進行深入研究，并取得豐碩成果[8-13].步長αk步長通常用非精確線性搜索求得，常用的線搜索有Armijio型線搜索和Wolfe型線搜索[14-18]：

標(biāo)準(zhǔn)的Armijio型線搜索：

αk=max{ρj,j=0,1,2,…},

(4)

其中:ρ∈(0,1),δ∈(0,0.5).

標(biāo)準(zhǔn)的Wolfe線搜索：

(5)

(6)

其中參數(shù)0<δ<σ<1.

(7)

(8)

(9)

當(dāng)線性搜索精確時，式(9)等價于FR公式.

文獻[19]對廣義Wolfe線搜索進行改進，得到如下線搜索：

筆者對標(biāo)準(zhǔn)Wolfe線搜索做出如下改進.將搜索條件(6)改為：

(10)

1算法及性質(zhì)

算法1

步1給定初始值x1∈Rn，ε>0，d1=-g1，令k：=1；

步2如果‖gk‖≤ε，則停止，否則轉(zhuǎn)步3；

步3由線搜索式(5)和式(10)求出步長αk，由式(2)得出xk+1；

(11)

由式(3)有dk=-gk+βkdk-1，等式兩端分別與gk做內(nèi)積，并結(jié)合式(9)可得：

由數(shù)學(xué)歸納法知命題1成立.

2算法的全局收斂性

本文做如下假設(shè)Η：

(i)水平集Ω={x∈Rn|f(x)≤f(x1)}有界，f(x)在Ω下方有界.

(ii)在Ω鄰域N內(nèi)，f(x)連續(xù)可微且梯度函數(shù)g(x)是Lipschitz連續(xù)的，即存在常數(shù)L>0,使得‖g(x)-g(y)‖≤L‖x-y‖，?x,y∈N恒成立.

命題2[20]設(shè)目標(biāo)函數(shù)滿足假設(shè)Η，xk由迭代式(2)和式(3)產(chǎn)生，其中dk滿足dkgk<0，步長由搜索式(5)和式(10)求得，則有：

(13)

(14)

由假設(shè)(ii)得：

(15)

由式(14)和式(15)得：

(16)

由式(16),{fk}為單調(diào)減的收斂數(shù)列得：

(17)

對上式兩端分別求和得:

(18)

得證.

證明若命題3不成立，則存在r>0，使得對任意k≥1有：

(19)

由式(3)可得：dk+gk=βkdk-1，兩端取模平方，移項得：

(20)

由式(9)和式(12)易知：

(21)

利用d1=-g1，并遞推得 ：

(22)

結(jié)合式(22)可以得出：

(23)

3數(shù)值實驗

為了測試算法的數(shù)值表現(xiàn)，用Matlab編程，對如下函數(shù)進行數(shù)值實驗，并與經(jīng)典算法進行比較：

問題1f(x)=[-13+x1+((5-x2)x2-2)x2]2+[-29+x1((x2+1)x2-14)x2]2,x0=[3,5]Τ.

問題2f(x)=100(x2-x12)2+(1-x1)2,x0=[-1.2,2]Τ.

問題3f(x)=(x12+x22)/(1-x1)2,x0=[-1.5,0.5]Τ.

問題4f(x)=x12+2x22+2x32+x42-5(x1+x2)-21x3+7x4,x0=[1,1,1,1]Τ.

表1　數(shù)值測試結(jié)果

對以上的4個函數(shù)進行數(shù)值實驗，結(jié)果見表1，其中參數(shù)取δ=0.4，σ=0.6，終止條件為‖gk‖<10-4或迭代次數(shù)超過1 000.

4結(jié)語

通過對經(jīng)典共軛梯度法與線性搜索的研究，推導(dǎo)出一種新的共軛梯度法，并且在新的搜索條件下證明了算法的充分下降性與全局收斂性，該方法可以類似DY方法，使用簡短的證明過程即可證明算法的全局收斂性.數(shù)值實驗表明算法可行.該算法的其他性質(zhì)還有待進一步研究.

參考文獻:

[1]FLETCHER R,REEVES C.Function minimization by conjugate gradient[J].Computer Journal，1964,7:149-154.

[2]POLAK E，RIBIERE G.Note sur la convergence de dirctions conjugees[J].Rev Francaise Informat Recherche Opertionelle，1969，16:35-43.

[3]POLAK B T.The Conjugate Graidnt Method in Extremem Problems[J].USSR Comp Math and Math,Phys,1969,9:94-112.

[4]HESTENES M R,Stiefel E.Methods of Conjugate Gradients for Solving Linear Systems[J].Res Nat Bur Standards Sect，1952,49:409-436.

[5]DAI Y H，YUAN Y.A nonlinear conjugate gradient with a strong global convergence property[J].SIAM Journal on Optimization，1999，10:177-182.

[6]LIU Y，STOREY C. Efficient Generalized Conjugate Gradient Algorithms.Part1 Theory[J].Journal of Optimization Theory and Applications，1991,69:129-137.

[7]FLETHER R.Practical method of optimization,Unconstrained Optimization[M].New York:John Wiley and Sons,1987.

[8]CHENG W Y，LIU X J. A hybrid nonlinear conjugate gradient method with sufficient descent property[J].Applied Mechanics and Materials，2011，943:58-60.

[9]ANDREI N. Another hybrid conjugate gradient algorithm for unconstrained optimization[J].Numerical Algorithms，2008，47:143-156.

[10]DAI Z F，CHEN L P. A mixed conjugate gradient method by HS and DY[J].Journal of Computational Mathematics，2005，27:429-436.

[11]喬峰.Wolfe線性搜索下一類帶誤差的共軛梯度法[J].云南民族大學(xué)學(xué)報(自然科學(xué)版),2013,22(4):266-269.

[12]吳雙江,杜學(xué)武.一個帶有擾動因子的修正DL共軛梯度法[J].湖北民族學(xué)院學(xué)報(自然科學(xué)版),2015,33(4):375-378.

[13]周雪琴.一個新的PRP共軛梯度法的全局收斂性[J].重慶工商大學(xué)學(xué)報(自然科學(xué)版),2015,32(11):31-33.

[14]陳忠.一個具有全局收斂性質(zhì)的共軛梯度法[J].長江大學(xué)學(xué)報(自然科學(xué)版),2014,11(7):1-4.

[15]戴彧虹，袁亞湘.非線性共軛梯度法[M].上海：上?？茖W(xué)出版社，2000.

[16]GRIPPO L,LUCIDI S.A globally convergent version of the Polak-Ribiere conjugate gradient method[J].Math Prog,1997,78:375-391.

[17]WOLFE P.Convergence Conditions for Ascent Methods[M].SIAM Rev,1969,11:226-235.

[18]GILBERT J C,NOCEDAL J.Global convergence propertiea of conjugate gradient methods for optimization[J].SIAM Journal on Optimization,1992,1:21-42

[19] 崔少勇，李廷鋒，孫惠娟.一種改進的非線性共軛梯度法[J].河北理工大學(xué)學(xué)報(自然科學(xué)版)，2008,30(4):78-80.

[20] ZOUTENDIJK G.Nonlinear Programming,Computational Methods[M].Amsterdam:North-Holland Publishing Company,1970.

責(zé)任編輯：時凌

A New Conjugate Gradient Method for Solving Unconstrained Optimization Problems

GUAN Zhe,YU Xianwei*

(School of Mathematics and Physcis,Bohai University,Jinzhou 121000,China)

Abstract：A new conjugate gradient method for unconstrained optimization problems is studied in this paper，The algorithm in the new Wolfe line search satisfies the sufficient descent condition，and the global convergence.

Key words：conjugate gradient method;unconstrained optimization;global convergence;Wolfe line search

收稿日期：2015-11-18.

基金項目：遼寧省教育廳科學(xué)研究項目(2010009).

作者簡介：關(guān)哲(1990- )男，碩士生，主要從事最優(yōu)化理論與算法研究；*通信作者：于憲偉(1963- )，男，副教授，主要從事可積系統(tǒng)、最優(yōu)化理論的研究.

文章編號：1008-8423(2016)01-0016-04

DOI:10.13501/j.cnki.42-1569/n.2016.03.004

中圖分類號：O224

文獻標(biāo)志碼：A