求解非線性方程組的一類非單調(diào)修正Levenberg-Marquardt算法

郭　楠,黃華鷹

(1.南京工程學(xué)院 數(shù)理部,江蘇 南京　211167; 2.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,安徽 合肥　230601)

?

求解非線性方程組的一類非單調(diào)修正Levenberg-Marquardt算法

郭楠1,黃華鷹2

(1.南京工程學(xué)院 數(shù)理部,江蘇 南京211167; 2.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,安徽 合肥230601)

通過將非單調(diào)搜索準(zhǔn)則與修正Levenberg-Marquardt(L-M)算法結(jié)合,提出了求解非線性方程組的一個(gè)新的非單調(diào)修正L-M方法.新算法在每次迭代步都引入校正步,使新的試探步更靠近Moore-Penrose步.利用信賴域技巧修正L-M參數(shù),在一定的條件下,證明了該算法的全局收斂性.數(shù)值試驗(yàn)表明了算法的有效性.關(guān)鍵詞:非線性方程組；Levenberg-Marquardt方法；非單調(diào)；信賴域方法；收斂性

考慮下述約束非線性方程組

(1)

其中:F:Rn→Rm二次連續(xù)可微的函數(shù).在論文中,總假設(shè)(1)的解集非空,記作X*.

與非線性方程組(1)相關(guān)的最優(yōu)化問題為

minf(x),

求解非線性方程組目前有許多有效的方法[1-3],其中,Levenberg-Marquardt方法是解決(1)的經(jīng)典方法之一,利用如下線性方程組的解dk作為點(diǎn)xk處的一個(gè)搜索方向

文[4]中提出的修正L-M算法是單調(diào)下降的.但是對(duì)于一些函數(shù)單調(diào)算法并不理想,收斂速度較慢.而非單調(diào)算法不需要每一步都單調(diào)下降,1993年,鄧乃揚(yáng)[5]首次提出了一類具有強(qiáng)收斂性質(zhì)的非單調(diào)信賴域算法,試驗(yàn)結(jié)果表明適當(dāng)?shù)姆菃握{(diào)算法比單調(diào)算法有更好的收斂結(jié)果.由于非單調(diào)技術(shù)具有很好的計(jì)算效果,很多學(xué)者對(duì)它進(jìn)行了進(jìn)一步的研究,并被成功地應(yīng)用到很多優(yōu)化算法中[5-8].Mo和Gu在文[6]中提出了一種非單調(diào)搜索技術(shù)獲得了較好的數(shù)值效果,即

其中

(2)

1　算　法

首先給出利用信賴域技巧的非單調(diào)修正L-M算法.

定義(1)的價(jià)值函數(shù)為

則在第k步迭代的實(shí)際下降量和預(yù)估下降量分別為

算法1(非單調(diào)修正L-M算法)

得到dk,求解

得到sk;

步4:置xk+1=xk+sk,若rk≥p0,并轉(zhuǎn)步5;否則,令ik是滿足下面不等式的最小非負(fù)整數(shù)i,

(3)

令tk=λik,xk+1=xk+tksk;

步5:計(jì)算

k:=k+1,轉(zhuǎn)步2.

在算法1中,m為一給定常數(shù),它是參數(shù)因子αk的下界.當(dāng)?shù)c(diǎn)靠近方程組的解時(shí),它防止試探步過大而引起的數(shù)值困難.

顯然,L-M步dk是下面最值問題的解

若定義

則dk也是下面信賴域問題的一個(gè)解

由Powell在文[10]中給出的結(jié)果

(4)

(5)

注意到

從而,預(yù)估下降量滿足

(6)

及

(7)

因此,有

(8)

此外,結(jié)合(4)～(8)式,可以得到如下引理：

引理1設(shè)sk由算法1的步2產(chǎn)生,則?k≥1,下式成立

(9)

且

(10)

2　算法的收斂性

為分析算法的收斂性,作如下假設(shè):

(AS1) 水平集L={x|f(x)≤f(x0)}?Ω,其中Ω是空間中的Rn有界閉集.

(AS3)F(x),J(x)在水平集L上是Lipschitz連續(xù),即存在正數(shù)L1和L2,使得

由于J(x)的Lipschitz連續(xù)性,有

(11)

為了證明算法的適定性,首先給出如下引理:

引理2設(shè){xk}是由算法1產(chǎn)生的序列,則對(duì)任意的k≥0,都有

fk+1≤Dk+1.

證明設(shè)I={k:rk≥p0},J={0,1,2,…}I.當(dāng)k∈I時(shí),有

結(jié)合引理1,有

得Dk≥fk+1.

當(dāng)k∈J時(shí),由(3),(10)式,有

得Dk≥fk+1.

從而,?k≥0,都有Dk≥fk+1.又由Dk的定義,對(duì)?k≥0,有

下面證明算法1的步4是適定的,從而算法是適定的.

引理3對(duì)任意的k∈J,算法1的步4的線搜索是有限終止的.即存在正整數(shù)ik使得(3)式成立.

證明假設(shè)步4不能有限終止,則存在k∈J,滿足

由于Dk≥fk,可得

又有f的可微性,不等式兩邊令i→∞并取極限,有

引理4設(shè)假設(shè)(AS1)、(AS2)成立,{xk}是由算法1產(chǎn)生的序列,則存在正數(shù)M,使得步長(zhǎng)tk滿足

證明由算法1的步4,有

通過泰勒展式得到,?ξk∈(xk,xk+λ-1tksk),使得

又由F的二階連續(xù)可微性知,?M>0,使得

結(jié)合引理2及上面的式子,有

由引理1可得

整理得

綜合上面兩式及(AS2),有

引理5設(shè)假設(shè)(AS1)成立,算法1產(chǎn)生的序列{xk}和{Dk},滿足{xk}?L且{Dk}非增且收斂.

證明先用歸納法證算法產(chǎn)生的序列{xk}?L.

當(dāng)k=1,顯然成立.現(xiàn)假設(shè)xk∈L,即f(xk)≤f(x1).由Dk+1的定義知Dk+1≤f(x1),結(jié)合引理2知f(xk+1)≤f(x1).

下證{Dk}是單調(diào)下降的.

當(dāng)k∈I時(shí),由算法1及(9)式，有

所以,有

當(dāng)k∈J時(shí),由算法1、引理4及(10)式,有

(12)

由Dk的定義及(12)式,有

所以,序列{Dk}是單調(diào)下降的.又Dk≥0,則序列{Dk}是收斂的.

接下來,證明算法1的全局收斂性.

定理1設(shè)假設(shè)(AS1)及(AS3)成立,{xk}是由算法1產(chǎn)生的序列,則有

證明若定理不成立,則存在ε>0,使得

(13)

由F的二階連續(xù)可微性知,?β>0,使得

又根據(jù)引理5的證明可知,?k≥0,有

因?yàn)閧Dk}是收斂的,所以，有

可推得

由sk的定義和算法1,推得

(14)

另一方面,結(jié)合引理1、(11)和(13)式,有

根據(jù)引理2,有

3　數(shù)值結(jié)果

為了驗(yàn)證算法1的有效性,對(duì)一些奇異問題進(jìn)行了數(shù)值試驗(yàn),并與文[11]的傳統(tǒng)L-M算法進(jìn)行了比較,結(jié)果列于表1、2.測(cè)試問題來自文[12].表1是對(duì)文[5]的標(biāo)準(zhǔn)問題修改得到的(見文[11]的算例說明)，表2是文[12]的Powell奇異問題.

表1　其余測(cè)試問題的數(shù)值結(jié)果

表2　 Powell奇異問題的數(shù)值結(jié)果

4　結(jié)束語

[1]FANJY,PANJY.Animprovedtrustregionalgorithmfornonlinearequations[J].ComputOptimAppl, 2011, 48 (1): 199-210.

[2]HAGERW,ZHANGH.Self-adaptiveinexactproximalpointmethod[J].ComputOptimAppl, 2008, 39: 161-181.

[3]蔣利華,馬昌鳳.光滑阻尼Gauss-Newton法解非線性不等式組[J].安徽大學(xué)學(xué)報(bào)(自然科學(xué)版), 2009, 33 (1): 18-21.

[4]FANJY,ZENGJL.ALevenberg-Marquardtalgorithmwithcorrectionforsingularsystemofnonlinearequations[J].AppliedMathematicsandComputation, 2013, 219 (17) : 9438-9446.

[5]DENGNY,XIAOY,ZHOUFZ.NonmonotonictrustregionaIgorithm[J].OptimiTheoryAppl, 1993, 76 (2): 259-285.

[6]GUNZ,MOJT.Incorporatingnonmonotonestrategiesintothetrustregionmethodforunconstrainedoptimization[J].ComputersandMathematicswithApplications, 2008, 55 (9): 2158-2172.

[7]GRIPPOL,LAMPAXIELLOANDF,LUCIDIS.AtruncatedNewtonmethodwithnonmonotonelinesearchforunconstrainedoptimization[J].JournalofOptimizationTheoryandApplications, 1989, 60: 401-419.

[8]SHIZJ,WANGSQ,XUZW.Theconvergencegradientmethodwithnonmontonelinesearch[J].AppliedMathematicsandComputation, 2010, 217 (5): 1921-1932.

[9]楊柳,陳艷萍.求解非線性方程組的一種新的全局收斂的Levenberg-Marquardt算法[J].計(jì)算數(shù)學(xué), 2008, 30 (4): 388-396.

[10]POWELLMJ.Aniterativemethodforfindingstationaryvaluesofafunctionofseveralvariables[J].ComputJ, 1962, 5: 147-151.

[11]楊柳,陳艷萍.一種新的Levenberg-Marquardt算法的收斂性[J].計(jì)算數(shù)學(xué), 2005, 27 (1): 55-62.

(責(zé)任編輯朱夜明)

A nonmonotonic L-M method with correction for solving nonlinear equations

GUO Nan1, HUANG Huaying2

(1.Department of Mathematics and Science,Nanjing Institute of Technology,Nanjing 211167,China;2.School of Mathematical Sciences,Anhui University,Hefei 230601,China)

In this paper,by using the nonmonotonic techniques and modified L-M method,we proposed a new nonmonotone L-M algorithm with correction for solving nonlinear equations.At every iteration, not only a L-M step but also a modified step was computed which makes the trial step closer to the Moore-Penrose step.On the other hand,the L-M parameter was updated by the trust region technique.Under certain conditions,we proved global convergence of this new method.Numerical results show that this new method performs very well.

nonlinear equations;Levenberg-Marquardt method;nonmonotone;trust region method;convergence

10.3969/j.issn.1000-2162.2016.02.003

2015-01-06

國(guó)家自然科學(xué)基金資助項(xiàng)目(61305072);江蘇省高校自然科學(xué)研究基金資助項(xiàng)目(13KJB110011);南京工程學(xué)院校級(jí)科研基金資助項(xiàng)目(QKJB201310)

郭楠(1983-),女,江蘇靖江人,南京工程學(xué)院講師.

O221.2

A

1000-2162(2016)02-0014-07