王 勝，關(guān)洪波

(湖南工學(xué)院數(shù)理部,湖南 衡陽 421002)

一種求解單調(diào)非線性方程組的凸組合算法*

王 勝，關(guān)洪波

(湖南工學(xué)院數(shù)理部,湖南 衡陽 421002)

將求解單調(diào)非線性方程組的CGD算法和MPRP算法的下降方向進(jìn)行凸組合，構(gòu)造出新的下降方向，從而提出新的算法，并給出新算法的全局收斂性定理.通過數(shù)值實(shí)驗(yàn)比較新算法與CGD算法和MPRP算法的結(jié)果，可知新算法優(yōu)于原算法.

MPRP算法；CGD算法；凸組合；單調(diào)非線性方程組；全局收斂性

單調(diào)的非線性方程組是非線性方程組的一種，若F是單調(diào)映射，即F滿足

(F(x)-F(y))T(x-y)≥0 ?x,y∈Rn，

則稱方程組F(x)=0為單調(diào)非線性方程組.

求解單調(diào)非線性方程組的方法很多[1-4]，共軛梯度算法是其中一種常見的算法.共軛梯度算法是由求解優(yōu)化問題的共軛梯度法發(fā)展而來，算法產(chǎn)生的下降方向?yàn)槌浞窒陆捣较?，其方向既不依賴于線性搜索也不依賴于迭代點(diǎn)，它具有存儲量小、計(jì)算上容易實(shí)現(xiàn)、收斂速度較快的優(yōu)點(diǎn).CGD算法和MPRP算法都是共軛梯度算法中比較好的算法.筆者將這2種算法的下降方向進(jìn)行凸組合，得到一個(gè)新的下降方向，新的下降方向同時(shí)具有CGD算法和MPRP算法下降方向的優(yōu)勢.

1 凸組合下降方向算法

(1)

yk=γk+λktk‖F(xiàn)(xk)‖dk，

γk=F(xk+1)-F(xk)，

(2)

yk=γk+λktk‖F(xiàn)(xk)‖dk，

γk=F(xk+1)-F(xk)，

其中tk為線性搜索的步長，它的定義由后面算法中的線性搜索確定.

(3)

下面給出對應(yīng)上述凸組合下降方向的算法.

算法1 凸組合下降方向的算法.

step1 給定初始點(diǎn)x0∈R，取常數(shù)σ∈(0,1)，ρ∈(0,1)，令k∶=0，取精度ε>0；

step3 由線搜索計(jì)算步長tk，tk=max {ρi:i=0,1,2,...}，使之滿足-F(xk+tkdk)Tdk≥σtk‖dk‖2，令zk=xk+tkdk；

step6 令k∶=k+1，轉(zhuǎn)step2.

2 全局收斂性

為了保證凸組合下降方向算法的全局收斂性，做如下2個(gè)假設(shè)：

假設(shè)1 單調(diào)映射F在Rn上Lipschiz連續(xù)，即存在正數(shù)L，使得

‖F(xiàn)(x)-F(y)‖≤L‖x-y‖ ?x,y∈R.

假設(shè)2 單調(diào)非線性方程組F(x)=0的解集S非空，不妨設(shè)x*為方程的解.

當(dāng)假設(shè)1和假設(shè)2成立時(shí)，有如下全局收斂性定理：

定理1(全局收斂性定理) 序列{xk}是由凸組合下降方向算法生成，則有

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

這一節(jié)對凸組合下降方向算法進(jìn)行數(shù)值試驗(yàn)，并將其數(shù)值結(jié)果與CGD算法和MPRP算法的數(shù)值結(jié)果進(jìn)行比較.設(shè)置精度ε=10-5，參數(shù)ρ=0.6,μ=0.45,σ=0.000 1.另外，假如迭代次數(shù)達(dá)到5 000次時(shí)還不滿足終止條件也終止算法，此時(shí)算法終止于非穩(wěn)定點(diǎn).所有的程序在相同條件的平臺上運(yùn)行.

考察單調(diào)非線性方程組F(x)=0的求解問題，這里F(x)=(f1(x),f2(x),...,fn(x))T，fi(x)=exi-1，x=(x1,x2,...,xn)T,i=1,2,...,n，x∈Rn，初始迭代點(diǎn)取不同維數(shù)的(1,1,...,1)T，(10,10,...,10)T，

(-10,-10,...,-10)T，(1,0,1,0,...,1,0)T.數(shù)值試驗(yàn)的結(jié)果如表1所示.

表1 CGD算法、MPRP算法和凸組合下降方向算法的數(shù)值結(jié)果

注a,b,c分別表示CGD算法、MPRP算法和凸組合下降方向算法的數(shù)值結(jié)果

4 結(jié)語

通過比較3個(gè)算法的數(shù)值試驗(yàn)結(jié)果，凸組合下降方向算法在2個(gè)重要指標(biāo)迭代次數(shù)和CPU計(jì)算時(shí)間上都明顯優(yōu)于CGD算法和MPRP算法，因此它是求解單調(diào)非線性方程組的一種比較好的算法.另外，在凸組合算法的下降方向時(shí)，所選取的參數(shù)是一個(gè)固定的、靜態(tài)的數(shù)值，是否按照某些規(guī)則動態(tài)的選取參數(shù)是需要進(jìn)一步思考的問題.

[1] ZHOU Weijun,LI Donghui.A Globally Convergent BFGS Method for Nonlinear Monotone Equations Without Any Merit Functions[J].Mathematics of Computation,2008,77(264):2 231-2 240.

[2] YAN Qinrong,PENG Xiaozhen,LI Donghui.A Globally Convergent Derivative-Free Method for Solving Large-Scale Nonlinear Monotone Equations[J].Journal of Computational and Applied Mathematics,2010,234(3):649-957.

[3] ZHOU Weijun,LI Donghui.Limited Memory BFGS Method for Nonlinear Monotone Equations[J].Journal of Computational and Applied Mathematics,2007,25:89-96.

[4] DAI Yuhong,YUAN Yaxiang.A Nonlinear Conjugate Gradient Method with a Strong Global Convergebce Property[J].SIAM Journal on Optimization,1999,10(1):177-182.

[5] XIAO Yunhai,ZHU Hong.A Conjugate Gradient Method to Solve Convex Constrained Monotone Equations with Applications in Compressive Sensing[J].Journal of Mathematical Analysis and Applications,DOI:http:∥dx.doi.org/10.1016/j.jmaa.2013.04.017.

[6] ZHANG Li,ZHOU Weijun,LI Donghui.A Descent Modified Polak-RibiéRe-Polyak Conjugate Gredient Method and Its Global Convergence[J].IMA Journal of Numerical Analysis,2006,26(4):629-940.

(責(zé)任編輯 向陽潔)

AnAlgorithmofConvexCombinationforSolvingMonotoneNonlinearEquations

WANG Sheng，GUAN Hongbo

(Mathematics and Physics Department，Hunan Institute of Technology,Hengyang 421002,Hunan China)

In this paper the authors convexly combine the the descent directions of the CGD algorithm and the MPRP algorithm for solving the monotone nonlinear equations,construct the new descent direction and give the new algorithm,and give the globally convergent theorem of the new algorithm.At last the authors compare the algorithms through the numerical experiments and find that the new algorithm is better than the original algorithms.

MPRP algorithm;CGD algorithm;convex combination;monotone nonlinear equations;global convergence

1007-2985(2014)01-0012-03

2013-05-07

湖南省教育廳科學(xué)研究項(xiàng)目(12C0664)；湖南工學(xué)院院級項(xiàng)目(HY11006，HY12007)

王 勝(1981-)，男，湖南長沙人，湖南工學(xué)院數(shù)理部講師，碩士，主要從事最優(yōu)化理論研究.

O224;O241.6

A

10.3969/j.issn.1007-2985.2014.01.004