求解非線性對(duì)稱方程組的范數(shù)下降算法

王曉亮,袁功林,段俠彬,崔曾如,盛　洲

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

?

求解非線性對(duì)稱方程組的范數(shù)下降算法

王曉亮,袁功林,段俠彬,崔曾如,盛洲

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

摘要：針對(duì)非線性對(duì)稱方程組求解問題，提出了一種具有回溯線搜索技術(shù)的修正方法，該方法不僅具有下降性質(zhì)而且在適當(dāng)?shù)臈l件下具有全局收斂性。數(shù)值結(jié)果表明該算法對(duì)非線性方程組問題是有效的。

關(guān)鍵詞：回溯線搜索技術(shù);非線性方程組;下降性;全局收斂性

0引言

考慮下面的非線性方程組：

F(x)=0,x∈Rn,

(1)

其中F: Rn→Rn是連續(xù)可微的，且它的雅克比矩陣F(x)在x∈Rn是對(duì)稱的。令‖F(xiàn)(x)‖2為一范數(shù)函數(shù)，則非線性方程組問題(1)等價(jià)于下面的優(yōu)化問題:

minθ(x),x∈Rn。

(2)

求解非線性方程組問題的方法有多種，一種常見的方法是迭代法，在本文，筆者利用迭代線搜索技術(shù)來求解問題(1)，其一般迭代公式為：

xk+1=xk+αkdk,

(3)

其中dk是線搜索方向，αk是沿著dk的步長(zhǎng)。求解步長(zhǎng)αk和方向dk的方法有很多種(見文獻(xiàn)[1]~文獻(xiàn)[14]),在給出新算法之前，筆者先介紹一種常見的求步長(zhǎng)αk和方向dk的方法。

魯習(xí)文等[4]提出了一種修正的單調(diào)下降線搜索技術(shù)：

(4)

其中δ∈(0，1),αk=max{1,r,r2,…}且使式(4)成立。該方法在適當(dāng)?shù)臈l件下具有全局收斂性和超線性收斂等性質(zhì)，數(shù)值結(jié)果也表明該方法比其他的一般線搜索技術(shù)更具有競(jìng)爭(zhēng)力。

袁功林[14]提出了一種新的搜索方向：

(5)

其對(duì)范數(shù)函數(shù)θ(x)具有獨(dú)立于線搜索的下降性；在適當(dāng)?shù)臈l件下，該方法比BFGS方法有更好的數(shù)據(jù)表現(xiàn)。

筆者基于文獻(xiàn)[14]的思想，提出了一個(gè)改進(jìn)的搜索方向技術(shù)，并且在適當(dāng)?shù)臈l件下證明了其全局收斂性等性質(zhì)。貫穿本文，‖‖表示歐式范數(shù)，F(xiàn)k和Fk+1分別是F(xk)和F(xk+1)的簡(jiǎn)寫，序列{xk}是由算法產(chǎn)生的迭代點(diǎn)列。

1算法

在計(jì)算步長(zhǎng)αk時(shí)，雅可比矩陣F(x)的計(jì)算會(huì)明顯的增加計(jì)算量和消耗更多的時(shí)間。為了避免該缺陷，在本文，筆者將利用線搜索式(4)來求解步長(zhǎng)αk。

文獻(xiàn)[14]提出了一個(gè)新的搜索方向如式(5)，它對(duì)范數(shù)函數(shù)θ(x)具有獨(dú)立于線搜索的下降性。受此啟發(fā)，筆者給出一個(gè)修改的線搜索方向：

(6)

其中μ，η≥1。

算法MYL步驟如下：

Step 0： 給定x0∈Rn，常數(shù)η，μ；r,δ∈(0,1)，τ,ε∈(0,1)。令k:=1。

Step 1： 如果‖F(xiàn)k‖<ε，則停止；否則進(jìn)行step 2。

Step 2： 通過式(6)計(jì)算搜索方向dk。

Step 3： 若 ‖F(xiàn)(xk+dk)‖≤τ‖F(xiàn)(xk)‖，則αk=1，轉(zhuǎn)入step5；否則轉(zhuǎn)入step4。

Step 4： 令ik是使式(4)成立的最小的非負(fù)整數(shù)，則αk=rik；

Step 5： 利用迭代公式xk+1=xk+αkdk，計(jì)算新的迭代點(diǎn)xk+1。

Step 6： 如果‖F(xiàn)k+1‖<ε，則停止，否則令k=k+1，返回step2。

2全局收斂性

令Ω為一水平集，它的定義為：

Ω={x|‖F(xiàn)(x)‖≤‖F(xiàn)(x0)‖}，

為了得到算法MYL的全局收斂性，本文做如下假設(shè)：

假設(shè)1：F在包含于Ω的一個(gè)開凸集Ω1上是連續(xù)可微的。

假設(shè)2：F的雅可比矩陣在集合Ω1上是對(duì)稱的、有界的、正定的，即存在正的常數(shù)M≥m>0使的對(duì)任意的x∈Ω1，d∈Rn都有:

‖F(xiàn)(x)‖≤M和m‖d‖2≤dTF(x)d≤M‖d‖2,

(7)

成立。

②由假設(shè)1和假設(shè)2對(duì)任意的d∈Rn，x,y∈Ω1，有如下結(jié)論：

(8)

M‖d‖≥‖F(xiàn)(x)d‖≥m‖d‖和M‖x-y‖≥‖F(xiàn)(x)-F(y)‖≥m‖x-y‖。

(9)

下面的引理表明了由式(6)定義新的搜索方向?qū)Ψ稊?shù)函數(shù)θ(x)具有獨(dú)立于線搜索的下降性。

引理1若假設(shè)1和假設(shè)2滿足， 則存在正常數(shù)n1,n2使得對(duì)任意k≥0，都有：

和

成立。

其中不等式可以從注①中得到。

(10)

其中最后一個(gè)不等式由式(8)得到。綜上所述，取n1∈(0,1)和n2∈(0,1/M)，則引理得證。

通過上面的引理，可以得出范數(shù)函數(shù)θ(x)沿著搜索方向dk是下降的，這意味著對(duì)所有k≥0，都有‖F(xiàn)k+1‖≤‖F(xiàn)k‖成立。與文獻(xiàn)[4]中引理3.2相似，可以得到下面的引理，這里省略其證明。

引理2 若假設(shè)1和假設(shè)2成立，{αk,dk,xk,Fk}由算法MYL產(chǎn)生，則序列{xk}?Ω，并且序列{‖F(xiàn)k‖}收斂。

引理3若假設(shè)1和假設(shè)2成立，{αk,dk,xk,Fk}由算法MYL產(chǎn)生，則有：

(11)

證明：由式(4)， 則：

由序列{θ(xk)}是嚴(yán)格下降的，故引理得證。

下面將證明在滿足假設(shè)1和假設(shè)2的情況下，算法MYL的全局收斂性，即存在序列{xk}的一個(gè)聚點(diǎn)，其是方程公式(2)的一個(gè)穩(wěn)定點(diǎn)，即滿足：

(12)

定理1若假設(shè)1和假設(shè)2滿足，{αk,dk,xk,Fk}由算法MYL產(chǎn)生，則式(12)成立。

(13)

(14)

。

(15)

另一方面，在不等式(10)兩邊同時(shí)對(duì)k取極限，則得到：

。

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

將對(duì)算法MYL和BFGS算法的數(shù)值表現(xiàn)進(jìn)行測(cè)試、比較。為了避免計(jì)算范數(shù)函數(shù)θ(x)的雅可比矩陣θ(x)，在數(shù)值試驗(yàn)中用‖F(xiàn)k+1‖-‖F(xiàn)k‖來代替θ(xk+1)。具有固定初始點(diǎn)的測(cè)試函數(shù)(見文獻(xiàn)[11],文獻(xiàn)[14]~文獻(xiàn)[16])如表1，其中：

F(x)=(f1(x),f2(x),…,fn(x))T。

表1　測(cè)試函數(shù)

試驗(yàn)時(shí)，所有的代碼都在MatlabR2010b 上進(jìn)行編寫，程序在CPU為Intel Pentium(R)Dual-Core E5800 3.20 GHz， SDRAM為2.00G bytes的Windows 7操作系統(tǒng)下運(yùn)行。在試驗(yàn)中，算法中的參數(shù)的選擇為μ=1，η=1，r=δ=0.1，τ=0.5，ε=10-5。試驗(yàn)終止的條件為‖F(xiàn)(x)‖≤10-5或者NI≥1 000。試驗(yàn)結(jié)果見表2，其中的元素有下列的定義：

Dim：?jiǎn)栴}的維數(shù)； NI: 試驗(yàn)中迭代次數(shù)；NF：試驗(yàn)中函數(shù)值計(jì)算次數(shù)；GN：當(dāng)試驗(yàn)終止時(shí)，F(xiàn)(x)的范數(shù)‖F(xiàn)(x)‖；Cputime：試驗(yàn)所需時(shí)間,s；fail：試驗(yàn)失敗。

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

從表2不難發(fā)現(xiàn)算法MYL在解決非線性方程組問題方面比一般的BFGS方法更有效:對(duì)于問題1，3，6，一般的BFGS方法不能求解，而的算法MYL可以十分有效的快速解決。對(duì)于問題7在Dim=1 000時(shí)，算法MYL 因迭代次數(shù)超過1 000而失效；同時(shí)還可以看到，一般的BFGS方法對(duì)上述8個(gè)問題進(jìn)行求解時(shí)，其消耗的時(shí)間都不少于算法MYL求解時(shí)所需時(shí)間。因此，算法MYL是合適的。

4結(jié)語

對(duì)于求解非線性對(duì)稱方程組問題，本文基于文獻(xiàn)[14]的思想，提出了一個(gè)改進(jìn)的搜索方向技術(shù)。在適當(dāng)?shù)臈l件下，建立了算法MYL的下降性、全局收斂性和局部收斂性等性質(zhì)。在數(shù)值試驗(yàn)中，可以發(fā)現(xiàn)算法MYL比一般的BFGS方法在求解非線性對(duì)稱方程組問題中耗費(fèi)的時(shí)間更短，而且可以求解的問題更多。因此，算法MYL是有效的。

參考文獻(xiàn):

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

[2]LI D, FUKUSHIMA M.A global and superlinear convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations[J]. SIAM J.Numer.Anal.1999,37:152-172.

[3]GU G Z, LI D H, QI L, et al.Descent directions of quasi-Newton methods for symmetric nonlinear equations[J]. SIAM Journal on Numerical Analysis, 2002, 40(5): 1763-1774.

[4]YUAN G, LU X.A new backtracking inexact BFGS method for symmetric nonlinear equations[J]. Computers & Mathematics with Applications, 2008, 55(1): 116-129.

[5]NASH S G.A survey of truncated-Newton methods[J]. Journal of Computational and Applied Mathematics, 2000,124(1): 45-59.

[6]BROWN P N, SAAD Y.Convergence theory of nonlinear Newton-Krylov algorithms[J]. SIAM Journal on Optimization, 1994, 4(2): 297-330.

[7]吳鋒,李秀梅,朱旭輝,等.最速下降法的若干重要改進(jìn)[J]. 廣西大學(xué)學(xué)報(bào): 自然科學(xué)版, 2010,35(4):596-600.

[8]韋增欣, 謝品杰.修改 Broyden 族在一類非精確線搜索下的全局收斂性[J]. 廣西科學(xué), 2006, 13(1): 12-16.

[9]LI Q, LI D H.A class of derivative-free methods for large-scale nonlinear monotone equations[J]. IMA journal of numerical analysis, 2011, 31(4): 1625-1635.

[10]YU Z, LIN J, SUN J, et al.Spectral gradient projection method for monotone nonlinear equations with convex constraints[J]. Applied numerical mathematics, 2009, 59(10): 2416-2423.

[11]LI X, WANG X, DUAN X.A Limited memory bfgs method for solving large-scale symmetric nonlinear equations[C]//Abstract and Applied Analysis. London: Hindawi Publishing Corporation, 2014.

[12]YUAN G. A new method with descent property for symmetric nonlinear equations[J]. Numerical functional analysis and optimization, 2010, 31(8): 974-987.

[13]SHI Z J.Convergence of line search methods for unconstrained optimization[J]. Applied Mathematics and Computation, 2004, 157(2): 393-405.

[14]RAYDAN M.The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem[J]. SIAM Journal on Optimization, 1997, 7(1): 26-33.

[15]BING Y, LIN G.An efficient implementation of Merrill’s method for sparse or partially separable systems of nonlinear equations[J]. SIAM Journal on Optimization, 1991, 1(2): 206-221.

[16]ROBERTS S M, SHIPMAN J S.On the closed form solution of Troesch’s problem[J]. Journal of Computational Physics, 1976, 21(3): 291-304.

(責(zé)任編輯梁碧芬)

A norm descent method for symmetric nonlinear equations

WANG Xiao-liang, YUAN Gong-lin, DUAN Xia-bin, CUI Zeng-ru, SHENG Zhou

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

Abstract:In this paper, a modified search direction with backtracking line search method for symmetric nonlinear equations is presented .Furthermore, the proposed method not only possesses descent property but also owns global convergence in mild conditions.The numerical results indicate that the presented method is effective for the given problems.

Key words:backtracking line search; nonlinear equations; descent property; global convergence

中圖分類號(hào):O224

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào)：1001-7445(2015)06-1597-06

doi:10.13624/j.cnki.issn.1001-7445.2015.1597

通訊作者：袁功林(1976—)，河南商丘人，廣西大學(xué)教授，博士生導(dǎo)師; E-mail：yuangl0417@126.com。

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(11261006)；廣西杰出青年科學(xué)基金資助項(xiàng)目(2015GXNSFGA139001)

收稿日期：2015-09-20；

修訂日期：2015-10-11