APP下载

修正的Dai-Liao三项共轭梯度方法

2019-11-12陈贞晶

关键词:共轭收敛性梯度

陈贞晶

(重庆师范大学数学科学学院, 重庆 401331)

引 言

共轭梯度法是求解大规模无约束优化问题的最经典、最有效的方法之一,具有低存储要求、强收敛性、计算简单等优点。

考虑下面的无约束优化问题:

minf(x),x∈Rn

(1)

其中f:Rn→R是连续可微的。

共轭梯度法的迭代格式如下:

xk+1=xk+αkdk

(2)

d1=-g1,dk+1=-gk+1+βkdk

(3)

其中αk>0是通过某种线搜索获得的步长,dk+1是搜索方向,gk+1=g(xk+1)是目标函数f(x)在xk+1处的梯度,βk是共轭梯度法参数,简称CG参数,不同的βk值对应不同的共轭梯度方法[1]。

常用的线搜索有很多,本文只考虑Wolfe线搜索(4)-(5)和强Wolfe线搜索(4)-(6),如下所示:

f(xk+αkdk)-f(xk)≤δαk▽f(xk)Tdk

(4)

▽f(xk+αkdk)Tdk≥σ▽f(xk)Tdk

(5)

|▽f(xk+αkdk)Tdk|≤-σ▽f(xk)Tdk

(6)

共轭条件如下所示:

(7)

(8)

简称为DL方法且在Wolfe线搜索下满足DL共轭条件(7),但是不满足充分下降条件

(9)

2005年,Hager和Zhang[4]提出了一种在任何线搜索下满足充分下降条件的DL类型的共轭梯度方法,简称HZ方法,如下所示:

为了得到更好的收敛性,对HZ进行非负限制,得到如下截断形式:

2011年,Narushima[5]等人提出了一类三项共轭梯度法的搜索方向的一般形式,如下所示:

(10)

2013年,Dai和Kou[6]在2013年提出一个共轭参数:

以及截断形式:

这也是一个DL类型的共轭梯度法,满足充分下降条件,是目前经典的共轭梯度方法中计算性能最佳的方法。

这个方法简称为DDL方法,在Wolfe条件下满足充分下降条件(9),并且对一致凸函数全局收敛,在计算上与HZ、DK、DL方法作比较,结果均优于HZ、DK、DL方法,故DDL方法有效可行。

基于上述方法的优缺点,对以下两种修正的DL方法做进一步的修正,使得数值结果更加理想可行。

1 修正MDL+的方法

2017年,Narushima[8]等人对无约束优化问题,基于割线方程提出了下降的三项共轭梯度法。搜索方向和CG参数如下所示:

(11)

将其代入DL共轭条件(7)式可得出新的CG参数如下:

(12)

其中,

为了避免(12)式的分母为0,修正它为如下的形式:

(13)

其中,ξk是一个参数,定义如下:

(14)

(15)

其中,

(16)

(17)

(18)

因此,搜索方向可以表示成三项CG方法的形式,如下:

(19)

式(19)还可以写成以下三项CG形式:

(20)

其中,

(21)

基于文献[8]和[9]的思想,对文献[9]中的参数ηk运用文献[8]中的截断形式加以截断,提出以下两种截断形式,因此式(20)可以修正成以下形式:

(22)

其中,

(23)

(24)

(25)

其中,

(26)

(27)

TMDL1+算法[9]:

Step2计算αk使得Wolfe条件(4)-(5)成立;

Step5令k:=k+1,转至Step2。

2 收敛性

接下来,研究TMDL1+算法的收敛性质。假设gk≠0,否则将会发现一个平稳点。为了证明TMDL1+方法全局收敛,对目标函数作以下两个基本假设[12]:

假设A:

(i)f在水平集Γ={x∈Rn:f(x)≤f(x1)}上是有界的,即存在一个数B>0,使得

(28)

(ii)在Γ的某些邻域Ω中,f(x)是连续可微的且梯度g(x)是Lipschitz连续的,即存在L>0,使得

(29)

(30)

引理1(充分下降性)[6]

(31)

成立。

证明当k=0时,d1=-g1。因此不等式(31)恒成立。当k≥1时,dk+1与gk+1做内积可得:

(32)

引理2

假设目标函数满足假设A,如果步长αk满足Wolfe条件(4)-(5),则有

(33)

接下来给出的引理3表明上述的TMDL1+算法满足Zoutendijk条件[10]。

引理3

假设序列{dk}由(22)产生,其中参数tk如(24)所示,步长αk满足Wolfe条件(4)-(5),若f(x)满足假设A,则有Zoutendijk条件成立:

(34)

Nocedal[11]建立的以下研究结果对证明共轭梯度法的全局收敛性具有重要作用。

引理4

假设条件A对目标函数成立,考虑共轭梯度方法(2),其中dk是下降方,步长αk满足强Wolfe条件(4)和(5)。如果

(35)

则有

(36)

对一致凸函数,我们可以证明TMDL1+算法收敛,即(36)成立。

定理5

假设目标函数f(x)满足假设条件A,如果函数f(x)是一致凸的,TMDL1+算法收敛,即(36)成立。

证明:

(37)

基于(24)式可知

(38)

(39)

由方程(34)可得

成立。在引理4的基础上,可得:

3 数值分析

Hager和Zhang[4]在2005年提出了一个具有充分下降性的共轭梯度方法,简称HZ方法,参数如下:

以及截断形式:

Dai和Kou[6]在2013年提出一个共轭参数:

以及截断形式:

图1~图4分别对应的是HZ+、MDL+、TMDL1+、TMDL2+这四种方法解决测试问题所用的计算时间,迭代次数,函数值计算次数,梯度值计算次数的Dolan and More性能曲线图。从表1中可知数值越小,计算效果就越好,由此可以看出在计算时间上TMDL1+和TMDL2+方法优于HZ+、DK+和MDL+方法。

解决测试问题所用的计算时间,迭代次数,函数计算次数,梯度计算次数结果见表1。

表1 测试结果

解决测试问题所用的计算时间,迭代次数,函数值计算次数,梯度计算次数的Dolan and More[13]性能曲线图如图1~图4所示:

图1 计算时间

图2 迭代次数

图3 函数计算次数

图4 梯度计算次数

因此,通过以上的表1和图1~图4可知TMDL1+和TMDL2+方法在计算时间上优于HZ+,DK+和MDL+方法,故我们的方法是有效可行的。

4 结束语

通过对三项的MDL+方法,利用HZ和DK方法的截断形式的优点和3TCG方法的截断思想,提出了MDL+方法的两种新的截断形式,简称TMDL1+和TMDL2+方法,全局收敛性与MDL+方法一致。研究表明,TMDL1+和TMDL2+方法在计算效果上优于MDL+方法和HZ+方法,是有效可行的。

猜你喜欢

共轭收敛性梯度
一个带重启步的改进PRP型谱共轭梯度法
一个改进的WYL型三项共轭梯度法
随机加速梯度算法的回归学习收敛速度
强Wolfe线搜索下的修正PRP和HS共轭梯度法
Lp-混合阵列的Lr收敛性
巧用共轭妙解题
WOD随机变量序列的完全收敛性和矩完全收敛性
一个具梯度项的p-Laplace 方程弱解的存在性
END随机变量序列Sung型加权和的矩完全收敛性
松弛型二级多分裂法的上松弛收敛性