冀祥麟,韦增欣

(广西大学数学与信息科学学院,广西南宁　530004)



一种广义BFGS Levenberg-Marquardt算法*

冀祥麟,韦增欣**

(广西大学数学与信息科学学院,广西南宁530004)

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

摘要:提出一种基于BFGS更新的Levenberg-Marquardt算法,该算法不仅具有全局收敛性和二次收敛速度,而且可以更有效地求解大规模优化问题.数值实验表明，该算法在求解大规模绝对值方程问题方面也是有效的.

关键词:广义Levenberg-Marquardt算法BFGS更新全局收敛性绝对值方程

0 　引言

【研究意义】考虑具有如下形式的非线性方程组:

g(x)=0,

(1)

min f(x),x∈Rn.

传统L-M方法通过求解下述模型获取搜索方向

(2)

搜索方向为

(3)

式中,gk∶=g(xk),sk是g(x)在xk处的下降方向,Jk∶=J(xk)是g(x)在xk处的Jacobian矩阵,μk>0为迭代参数.不难看出,传统L-M方法的每一次迭代都需要计算Jacobian矩阵,这对于大规模问题,会增加算法的计算存储量和时间.【前人研究进展】绝对值方程(AVE)是由Rohn[7]首次提出,是一类不可微的NP-hard问题[8].文献[9]证明该方程解的存在性和唯一性.文献[10]也给出一类绝对值方程与线性互补问题的等价关系.在AVE求解方面,Caccetta 等[11]提出用光滑牛顿方法求解绝对值方程,并且证明其具有全局收敛性质.Mangasarian[12]提出用广义牛顿方法求解此类问题.Ketabchi等[13]提出一种范数方法求解绝对值方程.更多绝对值方程的求解方法见参考文献[14-15].【本研究切入点】为有效求解大规模问题,本文在适当的条件下提出一种在不需要非退化假设[16]即可具备全局收敛性,并且在一定条件下具有二次收敛性的算法.最重要的是,可以不必在每次迭代时都计算Jacobian矩阵,而且对于Jacobian矩阵Jk,通过BFGS推广得到.令yk=g(xk+1)-g(xk),Bk为广义BFGS,有近似关系:

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

(4)

此时,Bk+1满足正割方程Bk+1sk=yk,又有逼近关系:

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为下一次迭代.【拟解决的关键问题】提出一种基于BFGS更新的L-M算法，并分析算法在如下形式的绝对值方程中的应用：

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

(6)

其中,A,b为给定的已知常量矩阵或向量,x,b∈Rn,A∈Rn×n,x=(x1,x2,…,xn)T.文中,‖‖表示欧几里得范数.

1　绝对值方程的基本结论

Mangasarian[8]证明求解AVE是一个不可微的NP-hard的优化问题.又由文献[17-18]可知基于|x|的次梯度的广义Jacobian矩阵∂|x|为一对角矩阵,即

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

(7)

其中,

diag(·) 表示一对角阵,即有∂g(x)∶=J(x)=A-h(x).

根据文献[10]中的性质3和4,给出绝对值方程解的存在性和唯一性基本结论.

引理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选取参数β,σ∈(0,1),μ0>0,初始迭代点x0∈Rn,0≤ε≤1.令k∶=0.

Step 1若f(x)≤ε,算法终止；否则,进入Step 2.

Step 3Armijo线搜索.令λk是满足下面不等式的最小非负整数λ：

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,转Step 1.

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

证明由最优性条件,知sk满足

所以,sk是f(x)在xk处的下降方向,则引理2得证.

定理1(全局收敛性)假设{xk}由算法1迭代产生得到,且步长满足Armijo线搜索准则,如果存在一个子序列xkj→x*,而且满足相应的子序列{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(x*+βλ*s*)

对于子列xkj→x*,当j充分大时,有

f(xkj+βλ*skj)

由Armijo步长准则知λ*≥λ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*.

又根据文[19]中定理7.4和注7.2,可以得到算法的收敛速度是二次的.这里省去二次收敛性质的证明过程,详细证明见文献[19].文献[20]也给出了类似的证明.

定理2(二次收敛性质)假设{xk}是由算法迭代得到的,且收敛到f(x)的一个局部最小值点x*,μk=‖g(xk)‖1+τ,τ∈[0,1],那么,算法的收敛速度是二次收敛的.

3　数值实验

以求解绝对值方程问题为例,验证算法1对于求解大规模优化问题的有效性.实验的所有代码都在Matlab R2010b中运行,其中,电脑的配置：CPU为Intel Pentium(R) Dual-Core E5800 3.20 GHz,SDRAM为2.00 GB的Windows7操作系统.

数值实验结果见表1,其中,Dim表示问题维数；Itertotal表示算法1求解10次问题所需的总迭代次数；Cputimetotal表示算法求解10次问题所需总时间；Optaverage表示算法求解10次问题的平均误差,即

表1数值结果

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)的值随迭代次数Iter的变化

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

4　结论

本文提出一种基于BFGS更新的L-M算法,证明算法具有全局收敛性和二次收敛性质.该算法在每次迭代中,可以避免计算Jacobian矩阵,这在处理大规模问题中可以节约CPU耗费时间.在数值实验中,我们用算法测试了随机生成不同维数绝对值方程问题,结果表明算法是有效的.

参考文献：

[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]马昌凤.最优化方法及其Matlab程序设计[M].北京:科学出版社,2010. MA C F.Optimization Methods and Matlab Programming[M].Beijing:Science Press,2010.

[20]袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,1997. YUAN Y X,SUN W Y.Optimization Theory and Method[M].Beijing:Science Press,1997.

(责任编辑：尹闯)

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-),男,硕士研究生,主要从事最优化理论研究。 **通信作者：韦增欣(1962-),男,教授,博士生导师,主要从事最优化理论研究,E-mail:zxwei@gxu.edu.cn。

中图分类号：O224

文献标识码：A

文章编号：1005-9164(2016)05-0428-04

*国家自然科学基金资助项目(11161003)和广西杰出青年科学基金项目(2015GXNSFGA139001)资助。

广西科学Guangxi Sciences 2016,23(5):428～431

网络优先数字出版时间：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.003

网络优先数字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1520.006.html