Wolfe线搜索下的全局收敛修正HS共轭梯度法

李双安,朱志斌,杨柳笑,陈凤华

(1.桂林电子科技大学数学与计算科学学院,广西桂林 541004; 2.河南理工大学万方科技学院,郑州 451400)

Wolfe线搜索下的全局收敛修正HS共轭梯度法

李双安1,朱志斌1,杨柳笑1,陈凤华2

(1.桂林电子科技大学数学与计算科学学院,广西桂林 541004; 2.河南理工大学万方科技学院,郑州 451400)

为解决大规模无约束优化问题,基于Wolfe线搜索技术,提出新的修正HS共轭梯度法。在水平集有界和梯度Lipschitz连续的条件下,证明新算法具有全局收敛性。数值实验证实此算法有效可行。

无约束优化;共轭梯度法;Wolfe线搜索;全局收敛性

考虑无约束优化问题

其中f:Rn→R是一光滑非线性函数,其梯度记为g(x)=∇f(x)。

用共轭梯度法可有效解决大规模无约束优化问题(1)。此方法具有运算简便和占用存储空间少的特点,相关研究可参考文献[1-4]。求解问题(1)的共轭梯度法迭代公式为:

其中:αk＞0为搜索步长;dk为搜索方向;gk= g(xk);βk为更新参数。

共轭梯度法的关键是更新迭代参数βk的选取,不同的βk对应不同的共轭梯度法。著名的βk计算公式有:

其中‖·‖为欧式范数,yk-1=gk-gk-1。式(4)、(5)、(6)、(7)分别为FR、PRP、HS、DY共轭梯度法的迭代更新参数,在某些线搜索下的全局收敛性已被广泛研究,它们的收敛性和数值表现不尽相同。其中FR方法和DY方法具有良好的收敛性,而HS方法和PRP方法则数值性能优良。采用精确线搜索的HS方法与PRP方法对一般的非凸函数不一定收敛。为此,建立一种新的修正HS算法,证明在Wolf线搜索下该算法的全局收敛性结果。改变HS共轭梯度法的更新参数βk,同时在保证算法的搜索方向始终是下降方向前提下,提出新搜索方向dk,得到一种新的修正HS共轭梯度法。在水平集有界和梯度Lipschitz连续的条件下,可证明此算法具有全局收敛性。通过Matlab编程测试,证实新算法具有良好的数值结果。

1 修正的HS共轭梯度法(MHSCG)

文献[5]中,修正的佩里共轭梯度法更新参数为:

受文献[5]更新参数βk的启发,提出新的参数βk为:

式(11)成立可保证式(10)的搜索方向在每一步迭代是下降方向,对确保算法的全局收敛性很重要。

修正的HS共轭梯度法(MHSCG)的算法步骤为:

1)初始点x0∈Rn,且0＜σ1＜σ2＜1,令k=0。

2)若‖gk‖=0,则终止,否则进入下一步。

3)计算式(10)定义的搜索方向dk。

4)由Wolfe线搜索计算步长αk,

5)令xk+1=xk+αkdk。

6)置k∶=k+1,返回步骤2)。

2 全局收敛性分析

为保证全局收敛性,对问题(1)作如下基本假设:

H1 水平集Ω={x∈Rnf(x)≤f(x0)}有界,即存在一常数A＞0满足

H2 在Ω的某一邻域N内,f可微且其梯度g是Lipschitz连续,即存在一常数L＞0,满足

由H1、H2可推得存在一常数m＞0,满足

引理1 若H1、H2成立,则Wolfe线搜索是良定的。

证明 设φk(α)=f(xk+αdk)是关于α的函数,由于φk(α)=f(xk+αdk)在α＞0时有下界且0＜σ1＜1,故射线φ(α)=f(xk)+σ1αdk与曲线φk(α)在α的正半轴上有交点。

记最小的交点为α′k,则

结合式(17),并利用0＜σ1＜σ2＜1及dk＜0,得

由式(9)、(16)及H2,有如下引理。

引理2 若H1、H2成立,序列{xk}由修正的HS共轭梯度法产生,则有

证毕。

一般而言,共轭梯度法只要执行的线搜索满足Wolfe条件(12)和(13),都具有下面引理3所述性质[6],该性质通常用来证明共轭梯度法全局收敛性。

引理3 若H1、H2成立,考虑任一共轭梯度法的迭代形式(2),其中dk满足gTkdk＜0,且αk满足Wolfe条件(12)和(13),则

显然,将式(11)代入式(19),如下不等式成立:

下面对一致凸函数证明修正的HS共轭梯度法的全局收敛性。

定理1 若H1、H2成立,且f是一致凸函数,即存在一常数η＞0满足

{xk}由修正的HS共轭梯度法产生,则存在k,使得gk=0或‖gk‖=0。

由式(14)、(15)、(18)、(22),有

结合式(20),有

证毕。

3 数值实验

为验证MHSCG算法的有效性和稳定性,通过Matlab编程对算法进行数值实验。运行环境为Windows 7,Intel(R)Pentium(R),内存2 GB,CPU为2.13 GHz,测试环境为Matlab v7.8(R2009a)。数值实验所用算例为:

其中x*为算例的最优解。

数值实验分为2组:第1组数值实验针对算例1)用MHSCG算法与传统的FR方法、PR方法以及文献[7-8]提出的方法做对比;第2组数值实验针对算例2)～6)测试MHSCG算法对不同维度算例的可行性和稳定性。

实验参数设置为:σ1=0.2,σ2=0.8,精确度ε＜10-8。算法终止准则为以下二者之一:

1)‖gk‖＜ε;

2)I＞1000。

当终止准则2)出现时认为该方法对此数值例子失效。第1组数值实验结果见表1。

表1 算例1的对比测试结果Tab.1 Comparison of testing results for example 1

由表1的数值结果可知:MHSCG算法寻找算例1)的最优解所需迭代步数显著减少,优势明显。第2组数值实验结果见表2。

表2 算例2)～6)的测试结果Tab.2 Testing results for example 2)-6)

由表2可知,MHSCG算法对不同维度的算例能成功求得最优解,且迭代次数较少,算法稳定。

4 结束语

在传统Hestenes-Stiefel(HS)共轭梯度法基础上,提出一个新的参数βk计算公式,相应提出新的搜索方向dk。在Wolfe线搜索下,证明此方法具有全局收敛性。通过Matlab编程测试,证实MHSCG算法在相同精度下,迭代步数显著减少,适合解决不同维度问题。

[1] Gilbert J C,Nocedal J.Global convergence properties of conjugate gradient methods for optimization[J].SIAM Journal on Optimization,1992,2(1):21-42.

[2] Yuan Yaxiang.Numerical Methods for Nonlinear Programming[M].Shanghai:Shanghai Scientific Technical Publishers,1993:152-209.

[3] Shi Zhenjun.Restricted PR conjugate gradient method and its global convergence[J].Advances in Mathematics,2002,31(1):47-55.

[4] Shi Zhenjun.Convergence of PRP method with new nonmonotone line search[J].Applied Mathematics and Computation,2006,181(1):423-431.

[5] Livieris I E,Pintelas P.Globally convergent modied Perry’s conjugate gradient method[J].Applied Mathematics and Computation,2012,218(18):9197-9207.

[6] Zoutendijk G.Nonlinear Programming[M]//Abadie J. Integer and Nonlinear Programming.Amsterdam:North Holland Press,1970:37-86.

[7] 房明磊,张聪,陈凤华.一种新的Wolfe线搜索技术及全局收敛性[J].桂林电子科技大学学报,2008,28(1):62-65.

[8] 陈凤华,张聪,房明磊.曲线搜索下的新的记忆拟牛顿法[J].广西科学,2008,15(3):254-256.

编辑:翁史振

见习编辑:陈汝伟

Globally convergent modified HSconjugate gradient method with Wolfe line searching

Li Shuang’an1,Zhu Zhibin1,Yang Liuxiao1,Chen Fenghua2
(1.School of Mathematics and Computational Science,Guilin University of Electronic Technology,Guilin 541004,China; 2.Wanfang Institute of Science and Technology,Henan Polytechnic University,Zhengzhou 451400,China)

Based on Wolfe line searching technology,a modified HS conjugate gradient method for large-scale unconstrained optimization problem is presented.When level set is bounded and gradient is Lipschitz continuous,the global convergence of the new method is proved.Numerical experiments show that the proposed algorithm is feasible and effective.

unconstrained optimization;conjugate gradient method;Wolfe line searching;global convergence

O224

A

1673-808X(2015)02-0162-04

2014-05-26

国家自然科学基金(11361018);广西自然科学基金(2012GXSFFA060003);河南省教育厅科学技术研究重点项目(12B110011)

朱志斌(1974-),男,湖南双峰人,教授,博士,研究方向为最优化理论与算法。E-mail:zhuzb@guet.edu.cn

李双安,朱志斌,杨柳笑,等.Wolfe线搜索下的全局收敛修正HS共轭梯度法[J].桂林电子科技大学学报,2015,35(2):162-165.