一种求解单调非线性方程组的凸组合算法*

王 胜，关洪波

(湖南工学院数理部,湖南 衡阳 421002)

一种求解单调非线性方程组的凸组合算法*

王 胜，关洪波

(湖南工学院数理部,湖南 衡阳 421002)

将求解单调非线性方程组的CGD算法和MPRP算法的下降方向进行凸组合，构造出新的下降方向，从而提出新的算法，并给出新算法的全局收敛性定理.通过数值实验比较新算法与CGD算法和MPRP算法的结果，可知新算法优于原算法.

MPRP算法；CGD算法；凸组合；单调非线性方程组；全局收敛性

单调的非线性方程组是非线性方程组的一种，若F是单调映射，即F满足

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

则称方程组F(x)=0为单调非线性方程组.

求解单调非线性方程组的方法很多[1-4]，共轭梯度算法是其中一种常见的算法.共轭梯度算法是由求解优化问题的共轭梯度法发展而来，算法产生的下降方向为充分下降方向，其方向既不依赖于线性搜索也不依赖于迭代点，它具有存储量小、计算上容易实现、收敛速度较快的优点.CGD算法和MPRP算法都是共轭梯度算法中比较好的算法.笔者将这2种算法的下降方向进行凸组合，得到一个新的下降方向，新的下降方向同时具有CGD算法和MPRP算法下降方向的优势.

1 凸组合下降方向算法

(1)

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

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

(2)

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

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

其中tk为线性搜索的步长，它的定义由后面算法中的线性搜索确定.

(3)

下面给出对应上述凸组合下降方向的算法.

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

step1 给定初始点x0∈R，取常数σ∈(0,1)，ρ∈(0,1)，令k∶=0，取精度ε>0；

step3 由线搜索计算步长tk，tk=max {ρi:i=0,1,2,...}，使之满足-F(xk+tkdk)Tdk≥σtk‖dk‖2，令zk=xk+tkdk；

step6 令k∶=k+1，转step2.

2 全局收敛性

为了保证凸组合下降方向算法的全局收敛性，做如下2个假设：

假设1 单调映射F在Rn上Lipschiz连续，即存在正数L，使得

‖F(x)-F(y)‖≤L‖x-y‖ ∀x,y∈R.

假设2 单调非线性方程组F(x)=0的解集S非空，不妨设x*为方程的解.

当假设1和假设2成立时，有如下全局收敛性定理：

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

3 数值试验

这一节对凸组合下降方向算法进行数值试验，并将其数值结果与CGD算法和MPRP算法的数值结果进行比较.设置精度ε=10-5，参数ρ=0.6,μ=0.45,σ=0.000 1.另外，假如迭代次数达到5 000次时还不满足终止条件也终止算法，此时算法终止于非稳定点.所有的程序在相同条件的平台上运行.

考察单调非线性方程组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，初始迭代点取不同维数的(1,1,...,1)T，(10,10,...,10)T，

(-10,-10,...,-10)T，(1,0,1,0,...,1,0)T.数值试验的结果如表1所示.

表1 CGD算法、MPRP算法和凸组合下降方向算法的数值结果

注a,b,c分别表示CGD算法、MPRP算法和凸组合下降方向算法的数值结果

4 结语

通过比较3个算法的数值试验结果，凸组合下降方向算法在2个重要指标迭代次数和CPU计算时间上都明显优于CGD算法和MPRP算法，因此它是求解单调非线性方程组的一种比较好的算法.另外，在凸组合算法的下降方向时，所选取的参数是一个固定的、静态的数值，是否按照某些规则动态的选取参数是需要进一步思考的问题.

[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.

(责任编辑 向阳洁)

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

湖南省教育厅科学研究项目(12C0664)；湖南工学院院级项目(HY11006，HY12007)

王 胜(1981-)，男，湖南长沙人，湖南工学院数理部讲师，硕士，主要从事最优化理论研究.

O224;O241.6

A

10.3969/j.issn.1007-2985.2014.01.004