黎 勇， 鄧娌莉

(百色學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 廣西 百色 533000)

一種求解大規(guī)模方程組的修正Dai-Yuan共軛梯度法

黎 勇*， 鄧娌莉

(百色學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 廣西 百色 533000)

設(shè)計(jì)一種針對(duì)大規(guī)模非線性方程組的修正DY共軛梯度算法.該算法的搜索方向不僅自動(dòng)滿足充分下降條件，而且屬于信賴域.在適當(dāng)條件下，可以證明新算法是全局收斂的.初步的數(shù)值實(shí)驗(yàn)表明新算法可以有效求解大規(guī)模非線性方程組．

非線性方程組； 共軛梯度法； 大規(guī)模； 信賴域； 全局收斂

考慮非線性方程組：

f(x)=0，x∈Rn，

(1)

其中f:Rn→Rn連續(xù)可微.求解此類問(wèn)題的方法很多，將方程組問(wèn)題轉(zhuǎn)化為最優(yōu)化問(wèn)題是其中的一種思想.令

minφ(x)，x∈Rn，

(2)

共軛梯度法的一般迭代格式如下：

xk+1=xk+αkdk，

(3)

(4)

其中,αk是步長(zhǎng)，dk是搜索方向，不同的βk對(duì)應(yīng)著不同的共軛梯度法，最經(jīng)典的有HS方法、FR方法、PRP方法、DY方法等[1]．

不少研究人員在應(yīng)用共軛梯度思想求解非線性方程組方面進(jìn)行了討論，也取得了較好的研究結(jié)果.本文受文獻(xiàn)[2]和[3]的思想方法的啟發(fā)，將在經(jīng)典DY共軛梯度法的基礎(chǔ)上，利用投影技術(shù)，提出一種修正的DY投影共軛梯度法．

1 算法

新算法的搜索方向設(shè)計(jì)如下：

dk+1=

(5)

其中,f(xk+1)=fk+1，f(xk)=fk，yk=fk+1-fk，而λ1>0，λ2>0是常數(shù).在此基礎(chǔ)上，下面將給出新算法.新算法采用以下線搜索[4]：

-f(xk+αkdk)Tdk≥

(6)

這里αk=max{s，λs，λ2s，…}，σ>0，s>0，λ∈(0，1)．

算法1(MDY算法)：

步0. 選取初始點(diǎn)x0∈Rn.常數(shù)ε∈(0，1)，參數(shù)λ1>0，λ2>0，σ>0.令k:=0．

步2. 利用(5)式計(jì)算搜索方向dk+1．

步3. 由線搜索技術(shù)(6)式計(jì)算步長(zhǎng)αk．

步4. 利用以下公式計(jì)算下一個(gè)迭代點(diǎn)zk=xk+αkdk．

(7)

步6. 令k:=k+1.轉(zhuǎn)步1．

注：(7)式表示算法的下一個(gè)迭代點(diǎn)xk+1應(yīng)當(dāng)通過(guò)將當(dāng)前迭代點(diǎn)xk投射到超平面Hk={x∈Rnf(zk)T(x-zk)=0}上獲得，這一思想由Solodov和Svaiter在文獻(xiàn)[5]提出．

2 全局收斂性分析

引理1設(shè)dk滿足(5)式，則有：

(8)

和

(9)

證明當(dāng)k=0時(shí)，結(jié)論顯然成立．

當(dāng)k≥1時(shí)，根據(jù)(5)式可得

即(8)式成立．

依據(jù)(8)式，利用Cauchy-schwartz不等式得

故

綜上所述，(9)式得證. 證畢.

上述引理說(shuō)明新算法不僅自動(dòng)具有獨(dú)立于線搜索的充分下降性質(zhì)，而且搜索方向具有信賴域性質(zhì)，這兩個(gè)重要性質(zhì)對(duì)算法全局收斂性的證明非常重要.下面利用文獻(xiàn)[2]和[3]的思想方法討論新算法的全局收斂性.以下兩個(gè)假設(shè)是后文討論的依據(jù)：

假設(shè)(i)：非線性方程組(1)有解．

假設(shè)(ii)：f(x) Lipschitz 連續(xù)，即存在一個(gè)正的常數(shù)L，使得

(10)

由假設(shè)(ii)容易推出存在一個(gè)正的常數(shù)γ，使得

(11)

引理2若假設(shè)(i)、(ii)成立，則算法1是可行的．

(12)

下面證明滿足線搜索(6)式的步長(zhǎng)有下界．

反證法.假設(shè)存在k′使(6)式不成立，則對(duì)?m∈∪{0}，令有

由(8)式和假設(shè)(ii)有

(13)

而由(9)、(11)式可以推出

(14)

聯(lián)立(9)、(13)、(14)式可得

引理3設(shè)序列{xk}由算法1產(chǎn)生，假設(shè)(i)、(ii)成立，且f(x*)=0，則

和

成立．

引理3及其證明詳見(jiàn)文獻(xiàn)[5]．

定理1若假設(shè)(i)、(ii)成立，αk，dk，xk，fk都由算法1產(chǎn)生，則

(15)

證明假設(shè)(15)式不成立，則存在一個(gè)正的常數(shù)η，使

由(9)式有

(16)

而由(9)、(11)式容易得到

根據(jù)引理2、引理3以及(3)式容易知道

因此

(17)

(18)

當(dāng)k→∞時(shí)，對(duì)?k∈N2，上式兩邊同取極限得

而(8)式兩邊同取極限得

矛盾.所以(15)式成立.證畢.

3 數(shù)值試驗(yàn)

本節(jié)將對(duì)MDY算法與傳統(tǒng)DY算法在求解大規(guī)模非線性方程組方面進(jìn)行數(shù)值試驗(yàn)和比較，測(cè)試的所有程序都是在Matlab R2010b上運(yùn)行. 承擔(dān)測(cè)試任務(wù)的計(jì)算機(jī)配置如下：Win 7.Pentium Dual E5800 3.20 GHz，內(nèi)存2.0 G. 本次試驗(yàn)共選取文獻(xiàn)[4]中的9個(gè)非線性函數(shù)進(jìn)行測(cè)試，測(cè)試函數(shù)見(jiàn)表1．

表1 測(cè)試問(wèn)題

續(xù)表2

上表中No.表示測(cè)試問(wèn)題的序號(hào)，Dim表示問(wèn)題的維數(shù)，NI表示算法迭代次數(shù)，NF表示函數(shù)值的計(jì)算次數(shù)，GN表示程序終止時(shí)f(x)的范數(shù)值，CPUtime表示實(shí)驗(yàn)所需時(shí)間(單位為秒)，F(xiàn)表示失敗.從表2中的數(shù)據(jù)容易看出，針對(duì)測(cè)試問(wèn)題1，2，3，MDY算法能成功求解，而DY算法對(duì)這3個(gè)問(wèn)題基本失敗(問(wèn)題2中的5 000維和30 000維情形除外).對(duì)問(wèn)題4和5來(lái)說(shuō)，MDY算法無(wú)論是迭代次數(shù)、函數(shù)值計(jì)算次數(shù)，或者是運(yùn)算消耗時(shí)間上均優(yōu)于DY算法.對(duì)問(wèn)題7和9的求解效果，兩種算法基本一致. 當(dāng)然，在問(wèn)題6和8的求解上，DY方法也一定程度上表現(xiàn)出了它的優(yōu)勢(shì). 綜上所述，我們認(rèn)為新算法能夠有效求解大規(guī)模非線性方程組問(wèn)題，而且新算法MDY總體上的數(shù)值表現(xiàn)要優(yōu)于傳統(tǒng)的DY算法．

[1] 戴彧虹， 袁亞湘. 非線性共軛梯度法[M].上海:上?？萍汲霭嫔?，1999．

[2] YUAN G， ZHANG M. A three-terms Polak-Ribière-Polyak conjugate gradient algorithm for large-scale nonlinear equations[J]. Journal of Computational and Applied Mathematics， 2015，286: 186-195．

[3] YUAN G， ZHANG M， LI Y. A modified hestenes and stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations[J]. Journal of Optimization Theory and Application， 2016，168: 129-152．

[4] LI Q， LI D. A class of derivative-free methods for large-scale nonlinear monotone equations[J]. IMA Journal of Numerical Analysis， 2011，31(4):1625-1635．

[5] SOLODOV M V， SVAITER B F. A Globally Convergent Inexact Newton Method for Systems of Monotone Equations[C]//FUKUSHIMA M， QI L. Reformulation: Nonsmooth， Piecewise Smooth， Semismooth and Smoothing Methods. US: Springer， 1998:355-369．

AmodifiedDai-Yuanconjugategradientalgorithmforlarge-scalenonlinearequations

LI Yong, DENG Lili

(School of Mathematics and Statistics， Baise University， Baise， Guangxi 533000, China)

This paper gives a modified Dai-Yuan conjugate gradient algorithm for large-scale nonlinear equations.The presented search direction not only possesses the sufficient descent property but also belongs to a trust region.The new algorithm has the global convergence under appropriate conditions.Numerical results show that this proposed algorithm is more effective than that of the normal method for large scale nonlinear equations．

nonlinear equation; conjugate gradient methods; large-scale; trust region; global convergence

2017-02-20.

國(guó)家自然科學(xué)基金項(xiàng)目(11661001，11661009)； 廣西省自然科學(xué)基金項(xiàng)目(2014GXNSFAA118030)；廣西省教育廳科研項(xiàng)目(YB2014389)．

*E-mail: liyong@3922@163.com．

10.19603/j.cnki.1000-1190.2017.06.002

1000-1190(2017)06-0731-05

O224

A