两个修正的DL共轭梯度法

柳 馨

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

两个修正的DL共轭梯度法

柳 馨

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

基于带有割线条件的DL方法，提出了两个满足改进的割线条件的修正共轭梯度方法——MDDL1方法与WMDDL1方法.在步长满足Wolfe线搜索的条件下，证明了MDDL1方法具有充分下降性；进一步地证明了WMDDL1方法不依赖任何线搜索具有充分下降性；最后分析和证明了两个方法在步长满足强Wolfe线搜索的条件下对一般函数均具有全局收敛性.

无约束优化；共轭梯度法；修正的DL共轭梯度法；强Wolfe线搜索；全局收敛性

0 引 言

考虑如下形式的无约束优化问题：

minf(x),x∈Rn

(1)

其中，f:Rn→R是连续可微的非线性函数.

共轭梯度算法是求解这类大规模无约束优化问题的有效方法之一，其迭代格式如下：

xk+1=xk+αkdk

(2)

(3)

其中，αk是步长，且通常满足Wolfe线搜索或强Wolfe线搜索，Wolfe线搜索如下：

(4)

(5)

强Wolfe线搜索如下：

(6)

(7)

其中0<δ<σ<1，dk是搜索方向，gk=f(xk)是函数梯度，βk是一个参数.

最早的共轭梯度法是由Fletcher和Reeves于1964年提出的，称为FR[1]方法，FR方法的参数βk定义如下：

(8)

另外著名的有PRP[2-3]方法、HS[4]方法、CD方法、LS[5]方法以及DY[6]方法，它们的参数βk分别给出如下：

近年来，改进的共轭条件已经被用于非线性共轭梯度法.特别地，Dai和Liao[7]利用共轭条件：

(9)

其中sk=αkdk=xk+1-xk，t是某个参数，提出了一个新的βk公式：

(10)

其中t≥0.为方便起见，称参数βk选用公式(10)的方法为DL方法.显然，若t=0，则DL方法即为HS方法.吴双江[8]提出了一种带有最优参数选择的修正DL共轭梯度法，并证明了其全局收敛性.

结合DL方法和自调比无记忆BFGS方法的思想，Hager和Zhang[9]提出了新的βk公式：

(11)

(12)

在文献[11]中，Dai和Cou基于自调比无记忆BFGS方法，提出了一族共轭梯度法，其参数βk如下：

(13)

另一方面，Li和Fukushima在文献[12]中提出了一个改进的割线条件：

2f(xk)sk-1=zk-1

(14)

其中，

C>0,r>0

基于此，为了不依赖目标函数的凸性假设得到DL方法的全局收敛性，Zhou和Zhang在文献[13]中提出了一个修正的DL共轭梯度法，其参数公式如下：

(15)

可得

则hk=C，zk变为

(16)

在文献[14]中，Saman Babaie Kafakia和Reza Ghanbari提出了一个使DL方法产生下降性的参数t：

(17)

(18)

受上述文献的启发，此处提出了如下形式的βk：

(19)

基于割线条件式(16)，给出了如下新的βk公式：

(20)

方法(20)称为MDDL1方法.

在文献[15]中，Yao等人提出了一个修正的DL共轭梯度法，称为MHSDL方法，参数βk如下：

(21)

(22)

1 MDDL1方法和WMDDL1方法的充分下降性

为了便于后文研究MDDL1方法和WMDDL1方法的收敛性，对目标函数作出如下标准假设：

假设1 1) 水平集Γ={x∈Rn|f(x)≤f(x0)}有界，其中x0为初始点，即存在常数B>0，使得

∀x∈Γ

(23)

2)f在水平集Γ的某个邻域N内连续可微，且其梯度gLipschitz连续，即存在常数L,使得

∀x,y∈N

(24)

∀x∈Γ

(25)

定理1 考虑迭代形式为式(2)(3)，参数βk由MDDL1方法给出的共轭梯度法，步长αk满足Wolfe线搜索条件式(4)(5)，则方法MDDL1满足充分下降条件：

其中c>0.

证明对于MDDL1方法，由文献[14]，可得MDDL1方法满足充分下降条件：

定理2 考虑迭代形式为式(2)(3)，参数βk由WMDDL1方法给出的共轭梯度法.则方法WMDDL1满足充分下降条件：

∀k≥0

(26)

(27)

2 MDDL1方法和WMDDL1方法的全局收敛性

引理1[7]若假设1成立，考虑迭代形为式(2)(3)的共轭梯度法，其中dk是充分下降方向，步长αk满足强Wolfe线搜索条件(6)(7).若

(28)

则该方法具有全局收敛性：

(29)

定理3 若假设1成立，考虑迭代形式为式(2)(3)的共轭梯度法，其中搜索方向dk是由如下形式的参数βk计算得到：

(30)

其中dk是下降方向，步长αk满足强Wolfe线搜索条件(6)(7).若存在正常数c1,c2，使得

(31)

(32)

(33)

则式(29)成立.

证明由式(30)(31)和式(33)，有

(34)

根据柯西不等式以及式(3)(25)(30)(31)(32)(34)，可得：

下述定理将说明MDDL1方法对一般函数具有全局收敛性.

定理4 若假设1成立，考虑迭代形式为式(2)(3)的共轭梯度法，其中搜索方向dk是由MDDL1方法的参数βk式(20)计算得到，步长αk满足强Wolfe线搜索条件式(6)(7)，则式(29)对MDDL1方法成立.

由式(20)(24)(25)，有

引理2 下面的不等式总是成立：

(35)

则有

(36)

结合式(36)，利用三角不等式、柯西-施瓦兹不等式以及向量运算的正齐次性，可得

因此，

因此，不等式(35)总是成立，证毕.

定理5 若假设1成立，考虑迭代形式为式(2)(3)的共轭梯度法，其中搜索方向dk是由WMDDL1方法的参数βk式(22)计算得到，步长αk满足强Wolfe线搜索条件式(6)(7)，则式(29)对WMDDL1方法成立.

由式(22)(24)及式(25)，可得

由式(24)和式(35)，可得

(37)

[1] FETCHER R,REEVES C.Function Minimization by Conjugate Gradients[J].Computer Journal,1964,7(2):149-154

[2] POLAK E,RIBIERE G.Note Sur La Convergence de Methods de Directions Conjugees[J].Rev Francaise Informat Recherche Operatinelle,1969(16):35-43

[3] POLYAK B T.The Conjugate Gradient Method in Extreme Problems[J].USSR Computational Mathematics and Mathematical Physics,1969,9(4):94-112

[4] HESTENES M R,STIEFEL E L.Methods of Conjugate Gradients for Solving Linear Systems[J].Journal of Research of National Bureau of Standards,1952,5(49):409-436

[5] LIU Y,STOREY C.Efficient Generalized Conjugate Gradient Algorithms[J].Journal of Optimization Theory and Applications,1991,69(1):129-152

[6] DAI Y H,YUAN Y X.A Nonlinear Conjugate Gradient Method with a Strong Global Convergence Property[J].SIAM Journal on Optimization,1999,10(1):177-182

[7] DAI Y H,LIAO L Z.New Conjugate Conditions and Related Nonlinear Conjugate Gradient Methods[J].Applied Mathematics and Optimization,2001,43(1):87-101

[8] 吴双江.带有最优参数选择的修正DL共轭梯度法[J].重庆工商大学学报(自然科学版),2015,32(8):6-8

WU S J.The Modified DL Conjugate Gradient Method with Optimal Parameter Choices[J].Journal of Chongqing Technology and Business University (Natural Science Edition),2015,32(8):6-8

[9] HANGER W W,ZHANG H.A New Conjugate Gradient Method with Guaranteed Descent and Efficient Line Search[J].SIAM Journal on Optimization,2005,16(1):170-192

[10] HANGER W W,ZHANG H.A Survey of Nonlinear Conjugate Gradient Methods[J].Pacific Journal of Optimization,2006(2):35-58

[11] DAI Y H,KOU C X.A Nonlinear Conjugate Gradient Algorithm with an Optimal Property and an Improved Wolfe Line Search[J].SIAM Journal on Optimization,2013,23(1),296-320

[12] LI D H,FUKUSHIMA M.A Modified BFGS Method and Its Global Convergence in Nonconvex Minimization[J].Journal of Computational and Applied Mathematics,2001,129(1-2):15-35

[13] ZHOU W J,ZHANG L.A Nonlinear Conjugate Gradient Method Based on the Mbfgs Secant Condition[J].Optimization Methods and Software,2006,21(5):707-714

[14] SAMAN B K,REZA G.A Descent Family of Dai-Liao Conjugate Gradient Methods[J].Optimization Methods and Software,2014,29(3):583-591

[15] YAO S W,LU X W.A Conjugate Gradient Method with Global Convergence for Large-Scale Unconstrained Optimization Problems[J].Journal of Applied Mathe-matics,2013(6):1-9

Two Modified DL Conjugate Gradient Methods

LIUXin

(College of Mathematical Science,Chongqing Normal University,Chongqing 401331,China)

Based on the DL conjugate gradient method with secant equation,two modified DL conjugate gradient methods with the modified secant equation are proposed,which are called MDDL1 method and WMDDL1 method.The MDDL1 method can be proved to satisfy the sufficient descent condition when step size is obtained by Wolfe line search.Furthermore,the WMDDL1 method satisfies sufficient descent condition independent of any line search.Alternatively,the two methods can be proved to possess global convergence for general functions when step size is obtained by strong Wolfe line search.

unconstrained optimization; conjugate gradient; modified DL conjugate gradient method; strong Wolfe line search; global convergence

O224

：A

：1672-058X(2017)05-0013-06

责任编辑：李翠薇

10.16055/j.issn.1672-058X.2017.0005.003

2017-03-02；

：2017-04-17.

柳馨(1992-)，女，甘肃张掖人，硕士研究生，从事最优化理论与算法研究.