冀祥麟,韋增欣

(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,廣西南寧　530004)

?

一種廣義BFGS Levenberg-Marquardt算法*

冀祥麟,韋增欣**

(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,廣西南寧530004)

(College of Mathematics and Information Science,Guangxi University,Nanning,Guangxi,530004,China)

摘要:提出一種基于BFGS更新的Levenberg-Marquardt算法,該算法不僅具有全局收斂性和二次收斂速度,而且可以更有效地求解大規(guī)模優(yōu)化問題.數(shù)值實驗表明，該算法在求解大規(guī)模絕對值方程問題方面也是有效的.

關(guān)鍵詞:廣義Levenberg-Marquardt算法BFGS更新全局收斂性絕對值方程

0 　引言

【研究意義】考慮具有如下形式的非線性方程組:

g(x)=0,

(1)

min f(x),x∈Rn.

傳統(tǒng)L-M方法通過求解下述模型獲取搜索方向

(2)

搜索方向為

(3)

式中,gk∶=g(xk),sk是g(x)在xk處的下降方向,Jk∶=J(xk)是g(x)在xk處的Jacobian矩陣,μk>0為迭代參數(shù).不難看出,傳統(tǒng)L-M方法的每一次迭代都需要計算Jacobian矩陣,這對于大規(guī)模問題,會增加算法的計算存儲量和時間.【前人研究進(jìn)展】絕對值方程(AVE)是由Rohn[7]首次提出,是一類不可微的NP-hard問題[8].文獻(xiàn)[9]證明該方程解的存在性和唯一性.文獻(xiàn)[10]也給出一類絕對值方程與線性互補(bǔ)問題的等價關(guān)系.在AVE求解方面,Caccetta 等[11]提出用光滑牛頓方法求解絕對值方程,并且證明其具有全局收斂性質(zhì).Mangasarian[12]提出用廣義牛頓方法求解此類問題.Ketabchi等[13]提出一種范數(shù)方法求解絕對值方程.更多絕對值方程的求解方法見參考文獻(xiàn)[14-15].【本研究切入點(diǎn)】為有效求解大規(guī)模問題,本文在適當(dāng)?shù)臈l件下提出一種在不需要非退化假設(shè)[16]即可具備全局收斂性,并且在一定條件下具有二次收斂性的算法.最重要的是,可以不必在每次迭代時都計算Jacobian矩陣,而且對于Jacobian矩陣Jk,通過BFGS推廣得到.令yk=g(xk+1)-g(xk),Bk為廣義BFGS,有近似關(guān)系:

yk=g(xk+1)-g(xk)≈g(xk+1)sk.

(4)

此時,Bk+1滿足正割方程Bk+1sk=yk,又有逼近關(guān)系:

Bk+1sk≈g(xk+1)sk.

這意味著Bk+1沿方向sk逼近g(xk+1),即

(5)

其中,sk=xk+1-xk,yk=g(xk+1)-g(xk),xk+1為下一次迭代.【擬解決的關(guān)鍵問題】提出一種基于BFGS更新的L-M算法，并分析算法在如下形式的絕對值方程中的應(yīng)用：

g(x)∶=Ax-|x|-b=0,

(6)

其中,A,b為給定的已知常量矩陣或向量,x,b∈Rn,A∈Rn×n,x=(x1,x2,…,xn)T.文中,‖‖表示歐幾里得范數(shù).

1　絕對值方程的基本結(jié)論

Mangasarian[8]證明求解AVE是一個不可微的NP-hard的優(yōu)化問題.又由文獻(xiàn)[17-18]可知基于|x|的次梯度的廣義Jacobian矩陣?|x|為一對角矩陣,即

h(x)=diag(sign(x)),

(7)

其中,

diag(·) 表示一對角陣,即有?g(x)∶=J(x)=A-h(x).

根據(jù)文獻(xiàn)[10]中的性質(zhì)3和4,給出絕對值方程解的存在性和唯一性基本結(jié)論.

引理1i) 若A∈Rn×Rn,且A的所有奇異值都大于1,則對任意的b∈Rn,絕對值方程存在唯一解；

ii)若A∈Rn×Rn,且‖A-1‖<1,則對任意的b∈Rn,絕對值方程存在唯一解.

2　算法及其收斂性分析

基于BFGS更新,提出一種BFGS Levenberg-Marquardt算法.

算法1

Step 0選取參數(shù)β,σ∈(0,1),μ0>0,初始迭代點(diǎn)x0∈Rn,0≤ε≤1.令k∶=0.

Step 1若f(x)≤ε,算法終止；否則,進(jìn)入Step 2.

Step 3Armijo線搜索.令λk是滿足下面不等式的最小非負(fù)整數(shù)λ：

f(xk+βλsk)≤fk+σβλ，

(8)

令αk∶=βλk,xk+1∶=xk+αksk.

Step 4μk=‖g(xk)‖1+τ,τ∈[0,1],令yk=gk+1-gk,如果yksk>0,按照(5)式更新Jk+1；否則,令Jk+1=Jk.

Step 5令k∶=k+1,轉(zhuǎn)Step 1.

引理2式(2)中,sk是f(x)在xk處的下降方向.

證明由最優(yōu)性條件,知sk滿足

所以,sk是f(x)在xk處的下降方向,則引理2得證.

定理1(全局收斂性)假設(shè){xk}由算法1迭代產(chǎn)生得到,且步長滿足Armijo線搜索準(zhǔn)則,如果存在一個子序列xkj→x*,而且滿足相應(yīng)的子序列{J(xki)TJ(xki)+μkiI}收斂于正定矩陣J(x*)TJ(x*)+μ*I,那么,f(x*)=0.

證明若f(xk)≠0,則sk≠0.由引理2,μk>0及xkj→x*得到

由于skj=-[J(xkj)TJ(xkj)+μkjI]-1J(xkj)Tg(xkj),則skj→s*=

-[J(x*)TJ(x*)+μ*I]-1J(x*)Tg(x*).

因此對于β∈(0,1),存在非負(fù)整數(shù)λ*使得

f(x*+βλ*s*)

對于子列xkj→x*,當(dāng)j充分大時,有

f(xkj+βλ*skj)

由Armijo步長準(zhǔn)則知λ*≥λkj,所以

f(xkj+1)=f(xkj+βλkjskj)≤f(xkj)+

σβλkj,

即對充分大的j,有

f(xkj+1)≤f(xkj)+σ βλ*f(xkj)Tskj.

(9)

又

從而對(9)式兩邊求極限,得

f(x*)≤f(x*)+σ βλ*f(x*)Ts*.

又根據(jù)文[19]中定理7.4和注7.2,可以得到算法的收斂速度是二次的.這里省去二次收斂性質(zhì)的證明過程,詳細(xì)證明見文獻(xiàn)[19].文獻(xiàn)[20]也給出了類似的證明.

定理2(二次收斂性質(zhì))假設(shè){xk}是由算法迭代得到的,且收斂到f(x)的一個局部最小值點(diǎn)x*,μk=‖g(xk)‖1+τ,τ∈[0,1],那么,算法的收斂速度是二次收斂的.

3　數(shù)值實驗

以求解絕對值方程問題為例,驗證算法1對于求解大規(guī)模優(yōu)化問題的有效性.實驗的所有代碼都在Matlab R2010b中運(yùn)行,其中,電腦的配置：CPU為Intel Pentium(R) Dual-Core E5800 3.20 GHz,SDRAM為2.00 GB的Windows7操作系統(tǒng).

數(shù)值實驗結(jié)果見表1,其中,Dim表示問題維數(shù)；Itertotal表示算法1求解10次問題所需的總迭代次數(shù)；Cputimetotal表示算法求解10次問題所需總時間；Optaverage表示算法求解10次問題的平均誤差,即

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

Table 1Numerical results

DimItertotalCputimetotalOptaverage500591.456425e+022.573539e-101000596.337541e+023.963551e-101500631.556172e+031.288582e-092000552.260922e+031.869581e-092500644.888463e+032.653575e-093000647.682067e+031.955933e-09

圖1Opt(Iter)的值隨迭代次數(shù)Iter的變化

Fig.1The values of Opt(Iter) with the number of iterations Iter

4　結(jié)論

本文提出一種基于BFGS更新的L-M算法,證明算法具有全局收斂性和二次收斂性質(zhì).該算法在每次迭代中,可以避免計算Jacobian矩陣,這在處理大規(guī)模問題中可以節(jié)約CPU耗費(fèi)時間.在數(shù)值實驗中,我們用算法測試了隨機(jī)生成不同維數(shù)絕對值方程問題,結(jié)果表明算法是有效的.

參考文獻(xiàn)：

[1]MARQUARDT D W.An algorithm for least-squares estimation of nonlinear parameters[J].Journal of the Society for Industrial and Applied Mathematics,1963,11(2):431-441.

[2]NOCEDAL J,WRIGHT S J.Numerical Optimization [M].New York:Springer-Verlag,2006.

[3]BERTSEKAS D P.Nonlinear Programming[M].2nd edition.Belmount,Mass,USA:Athena Scientific,1999.

[4]LEVENBERG K.A method for the solution of certain non-linear problems in least squares[J].Quarterly of Applied Mathematics,1944,2(2):164-168.

[5]YUAN Y X.Trust Region Algorithms for Nonlinear Equations[M].Hong Kong:Department of Mathematics,Hong Kong Baptist University,1994.

[6]ZHU D T.Nonmonotone backtracking inexact quasi Ne- wton algorithms for solving smooth nonlinear equations[J].Applied Mathematics and Computation,2005,161(3):875-895.

[7]ROHN J.Systems of linear interval equations[J].Linear Algebra and its Applications,1989,126:39-78.

[8]MANGASARIAN O L.Absolute value programming [J].Computational Optimization and Applications,2007,36(1):43-53.

[9]ROHN J.A theorem of the alternatives for the equation[J].Linear and Multilinear Algebra,2004,52(6):421-426.

[10]MANGASARIAN O L,MEYER R R.Absolute value equations[J].Linear Algebra and Its Applications,2006,419(2/3):359-367.

[11]CACCETTA L,QU B,ZHOU G L.A globally and qu- adratically convergent method for absolute value equations[J].Computational Optimization and Applications,2011,48(1):45-58.

[12]MANGASARIAN O L.A generalized newton method for absolute value equations[J].Optimization Letters,2009,3(1):101-108.

[13]KETABCHI S,MOOSAEI H.An efficient method for optimal correcting of absolute value equations by minimal changes in the right hand side[J].Computers & Mathematics with Applications,2012,64(6):1882-1885.

[14]YONG Q L.An iterative method for absolute value equations problem[J].Information,2013,16(1):7-12.

[15]HU S L,HUANG Z H.A note on absolute value equations[J].Optimization Letters,2010,4(3):417-424.

[16]YUAN G L,WEI Z X,LU X W.A BFGS trust-region method for nonlinear equations[J].Computing,2011,92(4):317-333.

[17]POLYAK B T.Introduction to Optimization[M].New York:Optimization Software Inc,1987.

[18]ROCKAFELLAR R T.New Applications of Duality in Convex Programming[C]//Proceedings of the Fourth Conference on Probability.Brasov,1971.

[19]馬昌鳳.最優(yōu)化方法及其Matlab程序設(shè)計[M].北京:科學(xué)出版社,2010. MA C F.Optimization Methods and Matlab Programming[M].Beijing:Science Press,2010.

[20]袁亞湘,孫文瑜.最優(yōu)化理論與方法[M].北京:科學(xué)出版社,1997. YUAN Y X,SUN W Y.Optimization Theory and Method[M].Beijing:Science Press,1997.

(責(zé)任編輯：尹闖)

A Generalized BFGS Levenberg-Marquardt Algorithm

JI Xianglin,WEI Zengxin

Key words：generalized Levenberg-Marquardt algorithm,BFGS update,global convergence,absolute value equations

Abstract：This paper proposes a modified Levenberg-Marquardt algorithm with BFGS update formula.Our algorithm converges globally to an optimal solution and the convergence rate is quadratic.Moreover,it has better efficiency for solving large-scale problems.Numerical results show that this algorithm is promising for solving large-scale absolute value equations problems.

收稿日期：2016-07-25

作者簡介：冀祥麟(1993-),男,碩士研究生,主要從事最優(yōu)化理論研究。 **通信作者：韋增欣(1962-),男,教授,博士生導(dǎo)師,主要從事最優(yōu)化理論研究,E-mail:zxwei@gxu.edu.cn。

中圖分類號：O224

文獻(xiàn)標(biāo)識碼：A

文章編號：1005-9164(2016)05-0428-04

*國家自然科學(xué)基金資助項目(11161003)和廣西杰出青年科學(xué)基金項目(2015GXNSFGA139001)資助。

廣西科學(xué)Guangxi Sciences 2016,23(5):428～431

網(wǎng)絡(luò)優(yōu)先數(shù)字出版時間：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.003

網(wǎng)絡(luò)優(yōu)先數(shù)字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1520.006.html