求解大规模非线性单调方程组的修正HS投影算法

2020-03-25王松华黎勇黄必昌

河南理工大学学报(自然科学版) 2020年3期

关键词：共轭收敛性单调

王松华，黎勇，黄必昌

(百色学院数学与统计学院，广西百色 533000)

0 引言

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

F(x)=0，x∈Rn，

(1)

其中函数F是连续可微且单调的，对∀x，y∈Rn，有

〈F(x)-F(y)，x-y〉≥0。

(2)

minQ(x)，x∈Rn，

(3)

一般地，好的共轭梯度法取决于好的共轭梯度方向和一个非精确线搜索技术。搜索方向在很大程度上决定了搜索效率，而搜索方向的充分下降和信赖域性质对共轭梯度法的全局收敛性起到积极作用[7-8]。M.V.Solodov等[9]提出将投影技术应用于大型非线性方程，取得了有效成果。目前，结合投影技术，将共轭梯度法应用到大规模非线性方程组成为最优化领域研究的一个热点[10-14]。同时，针对单调非线性问题，文献[15]给出著名的线搜索技术，能有效解决非线性大规模问题，其公式为

(4)

其中αk=max{s，ρs，ρ2s，…}，σ>0，s>0，ρ∈(0，1)。

本文在文献[5]的基础上，设计一个新的搜索方向，采用M.V.Solodov等[9]的投影技术，结合文献[15]线搜索方法，提出一个求解大规模非线性单调方程组的修正HS投影算法。

1 修正的HS投影算法

共轭梯度法迭代公式的一般形式为

xk+1=xk+αkdk，

(5)

式中：xk为当前迭代点；xk+1为下一个迭代点；αk为步长，由某种线搜索确定；dk为搜索方向，迭代公式定义为

(6)

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

令zk=xk+αkdk，有F(zk)T(x-zk)>0。如果对某个点x*满足f(x*)=0，由函数F的单调性质有F(zk)T(x-zk)≤0。则通过超平面

Hk={x∈Rn|F(zk)T(x-zk)=0}

严格将当前迭代点xk从式(1)的解中分离出来，M.V.Solodovy等[9]建议将当前点xk投影到超平面Hk方便确定下一个迭代点，即

(7)

式(7)是有效的，不仅得到了较好的数值结果，而且具有较好的理论性质。

针对大规模无约束优化问题，经典共轭梯度法有PRP、HS、FR、CD、DY和LS等[16]。经典的PRP方法、HS方法和LS方法在数值结果表现上非常有效，但是其全局收敛性并不令人满意。文献[5]在文献[17]的基础上修正了βPRP公式，该公式具有充分下降性，在标准WWP线搜索上算法全局收敛，数值结果良好，但该βPRP公式不具有信赖域性质。同时文献[5]给出了修正βHS公式，并给出了相应算法的初步数值试验结果和分析，但是没有证明该算法的充分下降性和全局收敛性。修正βHS公式[5]定义为

受此启发，本文在文献[5]的基础上，结合文献[7]和[14]关于共轭参数的修正方法，设计一个新的搜索方向dk+1，

dk+1=

(8)

其中，μ>1/4，λ≥2，γ≥2。

算法1

步骤3 采用线搜索式(4)计算步长αk；通过式(8)计算搜索方向dk。

步骤4 令迭代公式为zk=xk+αkdk。

步骤6 令k:=k+1，转步骤2。

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

首先证明算法1的搜索方向dk具有充分下降和信赖域性质。

引理1 搜索方向dk由式(8)定义，则存在c2>c1>0，使得下式成立：

(9)

(10)

首先证明不等式(9)成立。

证明k=0时，不等式(9)成立。以下证明k≥1时，不等式(9)成立。

根据式(8)，结合范数性质，得到

由式(9)可直接推导出式(10)的左半部分，下面证明式(10)的右半部分。

3 全局收敛性分析

假设1

(1)式(1)的解集非空，且水平集Ω={x∈Rn:F(x)≤F(x1)}有界。

(2)函数F:Rn→Rn是Lipschitz连续的，即∃L>0，使得

(11)

即存在一个常数ϑ=2ωL>0，使得

(12)

以下给出引理2和引理3。引理2说明线搜索能够保证得到一个正数步长，使得算法1在有限步内停止，从而说明提出的算法1是有意义的。

引理2 若假设(1)和假设(2)成立，则MMHS算法有意义。

证明假设不成立，或者MLS算法不停止，那么，使得

‖gk‖≥η,∀k∈N∪{0}。

(13)

下面证明满足式(4)的步长αk存在下界。

由式(9)和假设1的(2)有

(14)

由式(10)和式(12)可得

(15)

结合式(10)、(14)和(15)，可得

引理3 如果假设1成立，且{xk}是由MHS算法生成。设x*是式(1)的解，则有

(17)

成立。

证明因为F是单调的，x*是式(1)的解，结合超平面Hk的定义，得到

〈F(zk)-F(x*)，x*-zk〉=

〈F(zk)，x*-zk〉≤0,

(18)

容易验证xk+1是xk在半平面Mk={x∈Rn|〈F(zk)T，x-zk〉≤0}上的投影。如果x*处在半平面Mk空间里，根据投影算子基本性质，得到〈xk-xk+1，xk+1-x*〉≥0。则有

由此得出式(16)成立。

再将式(16)移项，整理得

将上式累加，令k→+∞，推出式(17)成立。

由式(4)和(7)，可得

联合式(17)，可得到

因此，有

(19)

由引理1、引理2和引理3，结合假设1和式(19)，利用反证法，可以得到算法1全局收敛性的结论。

(20)

成立。

证明采用反证法。假设式(20)不成立，则存在一个常数ν>0，使

由式(12)，有

(21)

根据式(10)和(15)得到

联合式(19)，可得

当k→∞时，对∀k∈N2，上式两边取极限，即有

而式(11)两边同取极限，得到

显然矛盾。所以假设不成立，即式(20)成立。证毕。

4 数值试验

本节通过对算法1与经典HS、三项HS算法在求解大规模非线性单调方程组问题上进行数值试验和比较分析，检验算法1的有效性。在算法1的步骤3中，分别使用式(22)和式(23)替代搜索方向dk，其他步骤和算法1的步骤一致，则对应为经典HS算法和三项HS算法，在文中分别称之为算法2和算法3。

其中yk=Fk+1-Fk。

具有固定初始点的函数来自于文献[7，14]，具体的函数名称与初始点，如表1所示。

表1 测试函数

表2 数值计算结果

续表2

从表2可以看出，在精度相同条件下，NI、NF和CPU运行时间3个测试指标中，算法1最好，算法2其次，算法3最差。为直观反映3种算法的性能差异，本文采用文献[17]的曲线分析比较方法，分别作出3种算法关于NI、NF和CPU运行时间的曲线比较图，见图1～3。由图1～3可知，总体上算法1比算法2和算法3更优，鲁棒性更好，是一种有效的算法。