解大规模非线性方程组的新型梯度类投影算法

李丹丹，李远飞

（广州华商学院数据科学学院，广东 广州 511300）

0 引言

本文考虑非线性单调方程组

其中F：Rn→Rn是连续可微函数且单调的，即对∀x，y∈Rn满足不等式

因此非线性单调方程组问题可转化为无约束优化问题。

非线性单调方程组广泛应用于不同领域，如单位球面优化问题［1］、L1范数正则稀疏优化问题［2］和压缩感知中的信号恢复问题［3］等。目前用于求解非线性方程组的经典算法有牛顿法［4］、拟牛顿法［5］、信赖域法［6］、共轭梯度法［7］。研究表明牛顿法与拟牛顿法虽局部收敛较快，但每次迭代都需计算一个与雅可比矩阵相关的方程组，导致算法在求解大规模问题时，计算量过大，效率低。而在信赖域方法中，信赖域半径的选取往往依赖经验，具有一定的盲目性。共轭梯度法因具有算法简易和存储量小的特点，近年来被广泛应用于求解大规模非线性方程组。如何利用共轭梯度法高效求解大规模非线性方程组，成为优化领域的热点之一。在共轭梯度法中其搜索方向和线搜索技术直接决定共轭梯度法理论的优良性及算法的高效性。Fang［8］给出新的搜索方向，有效提高了非线性大规模问题的求解效率，本文在Fang［8］的基础上，设计出一个新型的搜索方向，结合经典且高效的线搜索方法［9］和超平面投影技术［10］，提出了一个无导数型共轭梯度投影算法用于求解大规模非线性单调方程组问题。

1 算法

一般共轭梯度法公式为

其中αk为给定的步长，dk为搜索方向，一般的迭代公式为

其中βk称为共轭参数，F(xk)简写为Fk。

Fang［8］搜索方向的迭代公式记为

其中。同 时Fang［8］定 义 了 两 种 不 同 参 数θk的 形 式，此 处 记 为

其中0＜γ＜1。将分别带入式（3）得到搜索方向上述搜索方向虽具有充分下降性质，但并不满足信赖域性质，而信赖域性质对算法全局收敛性的证明起到促进作用。

基于βk的定义和的构造形式，本文提出了一个具有充分下降性与信赖域性质的搜索方向

算法MRMILL具体步骤为：

步骤1给定初始点x0∈Rn，常数μ＞0，ε∈(0，1)，τ＞0，令k：=0；

步骤2若‖F(xk)‖≤ε，则算法停止，否则转下一步；

步骤3按照式（6），计算搜索方向dk；

步骤4由线搜索技术［9］，令步长αk为序列{s，ρs，ρ2s，…}中满足以下不等式的最大元素：

其中常数σ＞0，s＞0，ρ∈(0，1)，求出步长αk；

步骤5计算试探点zk=xk+αkdk；

步骤6若‖F(zk)‖≤ε，则算法停止；否则通过以下超平面投影技术［10］计算新的迭代点xk+1：

步骤7令k：=k+1，转步骤1。

2 充分下降性条件

证明算法MRMILL中的dk满足自动充分下降性条件，为分析算法MRMILL的全局收敛性提供保证。

引理1由式（6）产生搜索方向dk，则有

证明当k=0时，得显然式（8）成立。当k≥1时，在式（6）两边左乘，得

故式（8）成立。证毕。

3 全局收敛性分析

为讨论算法MRMILL的全局收敛性质，需作如下一般性假设：

假设A

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

（A2）函数F：Rn→Rn是Lipschitz连续的，即存在常数M＞0，对任意的x，y∈Rn满足‖F(x)-F(y)‖≤

由假设A可推出，存在常数ξ＞0，有

下面的引理2和引理3可由文献［11］的引理4和文献［12］引理3.2类似可证，故省略其证明过程。

引理2在假设A条件下，算法MRMILL产生无穷序列{xk}，那么问题（1）的最优解x*满足此外，序列{xk}有界且满足。

引理3在假设A条件下，算法MRMILL的线搜索是有限步终止的。

引理4在假设A条件下，由式（6）产生搜索方向dk，则有

证明当k=0时，得‖d0‖=‖F0‖≤(2M+1)‖F0‖，显然结论成立。当k≥1时，由式（6）得

此外，由yk-1的定义及假设（A2）得

结合式（10）得‖dk‖≤(2τM+1)‖Fk‖。另外，由引理1得‖dk‖≥‖Fk‖，故结论成立。证毕。

定理1在假设A条件下，序列{αk，dk，xk，Fk}由算法MRMILL产生，则有。

证明采用反证法。假设结论不成立，则对任意的k∈N，存在常数ε＞0，有‖Fk‖＞ε，由引理4得

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

对于式（13），当k趋于无穷时，由极限运算法则可得

由 式（12）、（14）和（15）得F()T＞0，对于式（8），当k趋于无 穷时，由极限运算法则可得由式（14）和（15）得F()T≤0，产生矛盾。故假设不成立，成立。证毕。

4 数值试验

为检验算法MRMILL的有效性，对MRMILL算法、MRMIL1算法、MRMIL2算法在求解式（1）问题上进行数值试验，并对数值试验结果进行比较分析。测试问题来自文献［9］、［12-14］，初始点随机产生，即：rand（n，1）。

程序运行环境：Windows 10操 作 系 统，Inel Pentium（R）DuaCore CPU，E58003.2 GHz，内 存8 G，由MATLA2014a编写运行。终止条件：‖F(x)‖≤10-5或Iter≥3000。参数设置：s=1，ρ=0.48，σ=0.024，τ=1，维数为［3000，6000，9000，30000，60000，90000］。测试问题见表1，试验结果见表2。

表1 测试问题Tab.1 Test problems

表2 三种算法的数值结果Tab.2 Numerical results of three methods

续表2 三种算法的数值结果Continued Tab.2 Numerical results of three methods

为更直观地反映各类算法的性能，针对三种指标，采用文献［15］的评价方法，描绘出三类性能图，如图1。评价标准为：曲线越靠上，所表示的算法性能越好。

图1 三类性能图Fig.1 Three performance profiles

从表2与图1中可得出如下结论：

（1）表2的数值结果表明在相同的精度、问题和维度下，算法MRMILL在迭代次数、目标函数计算次数和CPU运行时间等三个指标上总体效果优于算法MRMIL1和算法MRMIL2；随着维数的增加，算法MRMILL的求解效果并没有受到影响，说明算法具有稳定性，适合求解大规模非线性单调方程组问题。

（2）性能图（图1）中算法MRMILL在三种指标下，所对应的曲线均高于算法MRMIL1和算法MRMIL2，表明三种算法中MRMILL性能最优，具有较强的鲁棒性。

综上所述，新算法具有良好的理论性质，数值结果验证了新算法的有效性与鲁棒性，后续可进一步研究将新算法推广到求解图像恢复与信号处理问题中，验证其实用性。