一种新的求解无约束规划的共轭梯度法

关　哲，于宪伟

(渤海大学 数理学院，辽宁 锦州 121000)



一种新的求解无约束规划的共轭梯度法

关哲，于宪伟*

(渤海大学 数理学院，辽宁 锦州 121000)

摘要：研究无约束优化问题的共轭梯度法，推导出一种新的共轭梯度法，算法在新Wolfe线搜索条件下具有充分下降性与全局收敛性.

关键词：共轭梯度法；无约束优化；全局收敛性；Wolfe线搜索

共轭梯度法是求解无约束优化问题的重要方法之一，基于其算法简单，存储量小的特点，常用于求解大规模优化问题.

考虑无约束优化问题:

(1)

其中f:Rn→R连续可微，对于为问题(1)的共轭梯度法，一般采用如下的迭代格式：

(2)

(3)

其中：gk=f(xk)是f在xk处的梯度，αk是由线性搜索产生的步长，βk是标量，由αk和βk的选取不同，可以产生不同的共轭梯度法.常用的共轭梯度法有：FR算法[1]、PRP算法[2-3]、HS算法[4]、DY算法[5]、LS算法[6]、CD算法[7]，参数公式分别为：

此外还有许多学者对共轭梯度法进行深入研究，并取得丰硕成果[8-13].步长αk步长通常用非精确线性搜索求得，常用的线搜索有Armijio型线搜索和Wolfe型线搜索[14-18]：

标准的Armijio型线搜索：

αk=max{ρj,j=0,1,2,…},

(4)

其中:ρ∈(0,1),δ∈(0,0.5).

标准的Wolfe线搜索：

(5)

(6)

其中参数0<δ<σ<1.

(7)

(8)

(9)

当线性搜索精确时，式(9)等价于FR公式.

文献[19]对广义Wolfe线搜索进行改进，得到如下线搜索：

笔者对标准Wolfe线搜索做出如下改进.将搜索条件(6)改为：

(10)

1算法及性质

算法1

步1给定初始值x1∈Rn，ε>0，d1=-g1，令k：=1；

步2如果‖gk‖≤ε，则停止，否则转步3；

步3由线搜索式(5)和式(10)求出步长αk，由式(2)得出xk+1；

(11)

由式(3)有dk=-gk+βkdk-1，等式两端分别与gk做内积，并结合式(9)可得：

由数学归纳法知命题1成立.

2算法的全局收敛性

本文做如下假设Η：

(i)水平集Ω={x∈Rn|f(x)≤f(x1)}有界，f(x)在Ω下方有界.

(ii)在Ω邻域N内，f(x)连续可微且梯度函数g(x)是Lipschitz连续的，即存在常数L>0,使得‖g(x)-g(y)‖≤L‖x-y‖，∀x,y∈N恒成立.

命题2[20]设目标函数满足假设Η，xk由迭代式(2)和式(3)产生，其中dk满足dkgk<0，步长由搜索式(5)和式(10)求得，则有：

(13)

(14)

由假设(ii)得：

(15)

由式(14)和式(15)得：

(16)

由式(16),{fk}为单调减的收敛数列得：

(17)

对上式两端分别求和得:

(18)

得证.

证明若命题3不成立，则存在r>0，使得对任意k≥1有：

(19)

由式(3)可得：dk+gk=βkdk-1，两端取模平方，移项得：

(20)

由式(9)和式(12)易知：

(21)

利用d1=-g1，并递推得 ：

(22)

结合式(22)可以得出：

(23)

3数值实验

为了测试算法的数值表现，用Matlab编程，对如下函数进行数值实验，并与经典算法进行比较：

问题1f(x)=[-13+x1+((5-x2)x2-2)x2]2+[-29+x1((x2+1)x2-14)x2]2,x0=[3,5]Τ.

问题2f(x)=100(x2-x12)2+(1-x1)2,x0=[-1.2,2]Τ.

问题3f(x)=(x12+x22)/(1-x1)2,x0=[-1.5,0.5]Τ.

问题4f(x)=x12+2x22+2x32+x42-5(x1+x2)-21x3+7x4,x0=[1,1,1,1]Τ.

表1　数值测试结果

对以上的4个函数进行数值实验，结果见表1，其中参数取δ=0.4，σ=0.6，终止条件为‖gk‖<10-4或迭代次数超过1 000.

4结语

通过对经典共轭梯度法与线性搜索的研究，推导出一种新的共轭梯度法，并且在新的搜索条件下证明了算法的充分下降性与全局收敛性，该方法可以类似DY方法，使用简短的证明过程即可证明算法的全局收敛性.数值实验表明算法可行.该算法的其他性质还有待进一步研究.

参考文献:

[1]FLETCHER R,REEVES C.Function minimization by conjugate gradient[J].Computer Journal，1964,7:149-154.

[2]POLAK E，RIBIERE G.Note sur la convergence de dirctions conjugees[J].Rev Francaise Informat Recherche Opertionelle，1969，16:35-43.

[3]POLAK B T.The Conjugate Graidnt Method in Extremem Problems[J].USSR Comp Math and Math,Phys,1969,9:94-112.

[4]HESTENES M R,Stiefel E.Methods of Conjugate Gradients for Solving Linear Systems[J].Res Nat Bur Standards Sect，1952,49:409-436.

[5]DAI Y H，YUAN Y.A nonlinear conjugate gradient with a strong global convergence property[J].SIAM Journal on Optimization，1999，10:177-182.

[6]LIU Y，STOREY C. Efficient Generalized Conjugate Gradient Algorithms.Part1 Theory[J].Journal of Optimization Theory and Applications，1991,69:129-137.

[7]FLETHER R.Practical method of optimization,Unconstrained Optimization[M].New York:John Wiley and Sons,1987.

[8]CHENG W Y，LIU X J. A hybrid nonlinear conjugate gradient method with sufficient descent property[J].Applied Mechanics and Materials，2011，943:58-60.

[9]ANDREI N. Another hybrid conjugate gradient algorithm for unconstrained optimization[J].Numerical Algorithms，2008，47:143-156.

[10]DAI Z F，CHEN L P. A mixed conjugate gradient method by HS and DY[J].Journal of Computational Mathematics，2005，27:429-436.

[11]乔峰.Wolfe线性搜索下一类带误差的共轭梯度法[J].云南民族大学学报(自然科学版),2013,22(4):266-269.

[12]吴双江,杜学武.一个带有扰动因子的修正DL共轭梯度法[J].湖北民族学院学报(自然科学版),2015,33(4):375-378.

[13]周雪琴.一个新的PRP共轭梯度法的全局收敛性[J].重庆工商大学学报(自然科学版),2015,32(11):31-33.

[14]陈忠.一个具有全局收敛性质的共轭梯度法[J].长江大学学报(自然科学版),2014,11(7):1-4.

[15]戴彧虹，袁亚湘.非线性共轭梯度法[M].上海：上海科学出版社，2000.

[16]GRIPPO L,LUCIDI S.A globally convergent version of the Polak-Ribiere conjugate gradient method[J].Math Prog,1997,78:375-391.

[17]WOLFE P.Convergence Conditions for Ascent Methods[M].SIAM Rev,1969,11:226-235.

[18]GILBERT J C,NOCEDAL J.Global convergence propertiea of conjugate gradient methods for optimization[J].SIAM Journal on Optimization,1992,1:21-42

[19] 崔少勇，李廷锋，孙惠娟.一种改进的非线性共轭梯度法[J].河北理工大学学报(自然科学版)，2008,30(4):78-80.

[20] ZOUTENDIJK G.Nonlinear Programming,Computational Methods[M].Amsterdam:North-Holland Publishing Company,1970.

责任编辑：时凌

A New Conjugate Gradient Method for Solving Unconstrained Optimization Problems

GUAN Zhe,YU Xianwei*

(School of Mathematics and Physcis,Bohai University,Jinzhou 121000,China)

Abstract：A new conjugate gradient method for unconstrained optimization problems is studied in this paper，The algorithm in the new Wolfe line search satisfies the sufficient descent condition，and the global convergence.

Key words：conjugate gradient method;unconstrained optimization;global convergence;Wolfe line search

收稿日期：2015-11-18.

基金项目：辽宁省教育厅科学研究项目(2010009).

作者简介：关哲(1990- )男，硕士生，主要从事最优化理论与算法研究；*通信作者：于宪伟(1963- )，男，副教授，主要从事可积系统、最优化理论的研究.

文章编号：1008-8423(2016)01-0016-04

DOI:10.13501/j.cnki.42-1569/n.2016.03.004

中图分类号：O224

文献标志码：A