求解非线性方程组的一种三项共轭梯度法

胡午杰，袁功林

(广西大学 数学与信息科学学院，广西 南宁 530004)

0 引言

本文考虑如下非线性方程组问题：

h(x)=0,x∈Rn,

(1)

其中目标函数连续可微，满足：

(h(x)-h(y))T(x-y)≥0, ∀x,y∈Rn。

(2)

minh*(x),x∈Rn。

(3)

其中‖·‖是欧几里得范数。求解问题(3)的迭代公式为：

xk+1=xk+αkdk,

其中dk表示搜索方向，αk为搜索步长。由上述迭代公式可知，算法的效率不仅与搜索方向有关，而且与搜索技术也密不可分[4-10]。众所周知，共轭梯度算法简单、高效和易操作，是求解大规模复杂问题的一种有效工具。共轭梯度法搜索方向定义为：

不同的βk决定不同的共轭梯度算法。其中著名的PRP[11-12]公式定义为：

该算法效率高，但收敛性不理想。基于此公式，Zhang[8]提出如下的三项共轭梯度公式：

(4)

该算法具有充分下降性，满足：

(5)

受此公式启发，Yuan等[12]提出求解模型(1)的三项共轭梯度公式：

其中μ>0，此公式满足式(5)和信赖域性质。

(6)

受上述两种方法的启发，本文设计如下三项共轭梯度公式：

(7)

其中，yk=hk+1-hk，μ1>1,μ2>1。

本文将证明修正的三项共轭梯度算法(modified three-lerm conjugate gradient algorithm, MTCG)同时满足下降性和信赖域性，且下降量更大。

1 修正的三项共轭梯度算法(MTCG)

算法MTCG步骤如下：

Step0：给定初始点x0=Rn，常数μi>1,σ,γ,s>0,i=1, 2;ρ,ε∈(0,1)。令dk=-μkhk,k:=1。

Step1:若‖hk‖<ε，则算法终止；否则进行下一步。

Step2:基于如下的线搜索技术[10]选择合适步长αk。

-h(xk+αkdk)Tdk≥σαk‖h(xk+αkdk)‖‖dk‖2,

(8)

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

Step3：令迭代公式为zk=xk+αkdk。

(9)

Step5：基于式(5)更新dk。

Step6：令k:=k+1，转step 1。

备注：式(9)是Solodov[13]提出的基于超平面和投影更新当前迭代点的技术，其中超平面Hk={x∈Rn|〈h(zk),(x-zk)〉=0}，xk+1为xk在超平面Hk上的投影。

2 算法MTCG的充分下降性及全局收敛性

证明算法MTCG的全局收敛性，需作基本的假设条件：

假设1：目标模型(1)的解集非空。

假设2：目标函数h(x)在Rn上Lipschitz连续，即存在一个常数L>0，使得：

‖h(x)-h(y)‖≤L‖x-y‖, ∀x,y∈Rn。

由假设2可知：

(10)

其中ζ为一个正数。

引理1若dk是由式(5)定义，则有：

(11)

和：

‖dk‖≤(μ1+2μ2)‖hk‖。

(12)

证明：当k=0时，式(10)、(11)显然成立。

当k>0时，由式(5)可知，

所以式(11)成立，对于式(12),由：

故式(12)成立。综上所述，引理1成立。在式(11)、(12)和文献[12]的基础上，本文仅仅给出相应的引理和收敛性定理，省略其证明过程。

引理2[12]若假设1、2成立，则算法MTCG生成有界的迭代点列且点列{xk}满足关系式：

‖xk+1-x*‖2≤‖xk-x*‖2-‖xk+1-x*‖2，

其中，x*为迭代数列的极限点。

引理3[12]若假设1、2成立，则算法MTCG经过有限次迭代生成点列{xk}且点列满足公式xk+1=xk+αkdk。

定理1[12]若假设1、2成立，算法MTCG生成相应的迭代序列{hk}，{αk}，{dk}，{xk},则：

(13)

3 数值实验

为检验算法效率，目标算法与类似算法作数值比较。其中类似算法的搜索方向是式(4)简记为算法(4)，其余步骤相同。相关测试函数选自文献[14-16]，本文随机挑选了其中的6个经典函数，见表1所示。

表1 测试函数

测试环境：本文数值实验代码都在Matlab R2010b编写运行，电脑配置为Intel Pentium(R)Dual-Core E5800 3.2 GHz的Windows 7操作系统。

实验参数设置：σ=0.98,s=1.5,γ=0.95，ε=10-5,μ1=1.01,μ2=1.5。

实验终止条件：‖h(x)‖≤10-5或NI≥1 000.实验结果见表2。

参数说明：NI为算法迭代次数；NG为目标函数计算次数；t为Cputime算法运行时间。

表2 数值结果

为了更直观地比较两种算法的性能，本文引用文献[17]方法进行算法MTCG与算法(4)的性能比较，其结果见图1。

从图1可以看出，算法MTCG相比算法(4)更加高效快速解决复杂问题，从而算法MTCG的鲁棒性更强。

图1 算法MTCG与算法(4)的性能比较(CPU-Time)

4 结语

针对大规模非线性方程组问题，本文在三项共轭梯度算法的启发下，提出了一种新的三项共轭梯度算法。其中，算法自动拥有充分下降性和信赖域性质且在一定条件下具有全局收敛性。数值实验表明算法MTCG比算法(4)更有效，因此算法MTCG的提出是有意义的。