解大规模非线性方程组的一种三项型投影算法

李丹丹，王松华

（1.广州华商学院 应用数学系，广东 广州 511300；2.百色学院 数学与统计学院，广西 百色 533000）

考虑如下非线性单调方程组

其中，g是连续可微函数且单调的，即

非线性单调方程组广泛应用于科学领域，如化学平衡体系［1］、经济均衡问题［2］和图像恢复［3］等.因此，有关非线性单调方程组算法的研究显得十分重要.目前求解非线性单调方程组有若干方法，且效果显著.常用方法主要分为2类：矩阵类和无矩阵类.矩阵类主要包含信赖域法［4］、牛顿法［5］和拟牛顿法［6］等；无矩阵类主要包括无导数法［7］和梯度投影法［8］等.近年来，具有良好性质（充分下降性和信赖域特性）的共轭梯度法，结合超平面投影技术，能高效地求解大规模非线性方程组问题，且在相对较弱条件下可得到全局收敛性.

在Fang［10］搜索方向的研究基础上，笔者构建出一个新的搜索方向，结合Solodov和Svaiter［11］的投影技术和线搜索技术，提出了一个求解大规模非线性单调方程组的三项无导数型共轭梯度算法.新算法优点如下：

1）搜索方向自动满足充分下降性和信赖域特性；

2）在合理的假设下，新算法具有全局收敛性；

3）试验结果表明新算法与同类算法相比更具有竞争力，具有良好的鲁棒性.

1 算 法

其迭代公式为

其中，x k为当前迭代点，x k+1为新的迭代点，αk为给定的步长，d k为搜索方向，经典的迭代公式定义为

其中，βk是一个共轭参数，g(x k)的简写为gk.

Solodov和Svaiter［11］提出了一种投影技术来更新下一个迭代点，该技术在理论和数值试验上保证算法的高效性和鲁棒性，令z k=x k+αk d k，更新新的迭代点公式为

其次，Fang［10］提出了一类求解大规模非线性单调方程组的无导数型共轭梯度法，其搜索方向为

性

，但不具备信赖域特性.

最后，受式（3）结构的启发，构造一个新的搜索方向

基于以上阐述，给出求解问题（1）的算法描述：

算法LCGP

步骤1给定初始点x0∈Rn，正常数s，σ>0，ε，ρ∈(0，1)，μ2，μ3>0，μ1>μ2+μ3.令k：=1；

步骤2若，则算法停止；否则转步骤3；

步骤3通过式（4）计算搜索方向d k；

步骤4（线搜索［9］）计算步长αk=ρsmk且mk为满足如下不等式的最小非负整数

其中，σ>0，s>0，ρ∈(0，1)；

步骤5令z k=x k+αk d k，若，则算法停止，并令新的迭代点x k+1=z k；否则，通过式（2）计算新的迭代点x k+1；

步骤6令k：=k+1，转步骤2.

2 充分下降性和信赖域特性

为分析算法的全局收敛性质，证明搜索方向d k的充分下降性和信赖域特性.

引理1 由式（4）定义的搜索方向d k，满足以下不等式和

其中，μ1>|μ2-μ3|，μ2，μ3>0.

证明当k=0时即式（6）成立.当k≥1时，式（4）两边左乘得

因此，式（6）成立.

当k=0时，式（7）显然成立.当k≥1时，由式（4）可推出

综上所述，式（7）成立.

证毕.

3 全局收敛性分析

为分析算法LCGP的全局收敛性质，需作合理假设：假设A

A1问题（1）的解集非空；

A2函数g(x)在Rn上是Lipschitz连续的，即存在正整数a，对任意的x，y∈Rn，使得如下不等式成立

由假设A可知，存在正整数b，有

引理2 在假设A条件下，x*为问题（1）的最优解，即g(x*)=0，那么由算法LCGP产生的序列{x k}具有以下性质

1）

2）序列{x k}是有界的；

3）

引理3 在假设A条件下，算法LCGP是适定的，即算法LCGP的线搜索是有限步终止的.

提出的引理2和引理3可由Yuan［12］的引理3.1和引理3.2类似可证，故省略其证明过程.

给出算法LCGP全局收敛性定理.

定理1在假设A条件下，算法LCGP产生的序列{gk}满足如下式子

证明假设对任意的k∈N且存在正数ε，都有

上式结合式（7）得

另外，由引理2 2）可知，存在无穷指标集K1和聚点，使得当k∈K1时，有

一方面，式（12）两边取极限，结合式（11）、（13）和（14）得

另一方面，式（6）两边取极限得

相矛盾，结论成立.

证毕.

4 数值试验

为了验证算法的有效性，通过数值实验将新算法与同类算法作比较.在算法LCGP的步骤3中，分别采用MRMIL1［10］、MRMIL2［10］和MRMIL3［10］产生搜索方向，其余步骤与算法LCGP一致，所对应的算法分别记为MRMIL1算法、MRMIL2算法和MRMIL3算法.

相关参数如下

采用Matlab（2014a）实现上述各类算法，且运行环境为：Windows10（64 bite），RAM：8GiB，CPU 3.60 GHz，终止准则为：gk≤10-5，设置算法的迭代次数上限为1 000，维数为［4 500，12 000，24 000，30 000，45 000］.测试问题共有10个：文献［13］的问题2、7、9、12；文献［14］的问题4.2；文献［15］的问题4、6、7、9；文献［16］的问题9.数值结果如表1所示，其中Pro表示问题序号，Dim表示维数，Iter表示迭代次数，NG表示函数计算次数，Time表示程序运行时间.

表1 各类算法数值结果

为更加直观分析4种算法在3种指标下的优劣势，描绘出3种指标性能图［17］，分别为CPU运行时间性能图（如图1所示）、迭代次数性能图（如图2所示）和目标函数值计算次数性能图（如图3所示）.所描绘性能图的计算公式

图1 CPU运行时间性能图

图2 迭代次数性能图

图3 目标函数值计算次数性能图

其中，P是测试集，|P|是测试集的问题个数，V是算法集合，τp，v是某种指标（运行时间、迭代次数和函数计算次数），t是给定的数值比率.

表1的数值结果显示，在相同的问题、维数、参数和精度下，算法LCGP在3个衡量指标（迭代次数Iter、目标函数计算次数NG和运行时间Time）下总体优于MRMIL1算法、MRMIL2算法和MRMIL3算法.此外，从图1～3可知，算法LCGP相比MRMIL1算法、MRMIL2算法和MRMIL3算法更加有效地、快速地求解大规模非线性方程组问题，且具有更好的鲁棒性.

5 小结

针对大规模非线性单调方程组问题，在Fang［10］所构造的搜索方向形式的基础上，利用Li［9］的新型线搜索技术，设计出一种新的三项共轭梯度算法，该方法在任何线搜索下自动满足充分下降性条件和信赖域性质.在一定的假设下，证明了新方法具有良好的全局收敛性质.通过大规模算例进行数值试验，其结果表明新算法更适用于求解大规模非线性单调方程组问题，且求解效率高于同类算法.