一个新的修正HS共轭梯度法及全局收敛性

陈凤华，李双安，程慧燕

（河南理工大学 万方科技学院，河南 郑州 451400）

一个新的修正HS共轭梯度法及全局收敛性

陈凤华，李双安，程慧燕

（河南理工大学 万方科技学院，河南 郑州 451400）

提出了一个新的修正HS共轭梯度算法解决无约束优化问题，该算法的特点是，搜索方向总是目标函数的下降方向，且不依赖于使用何种线搜索；特别是，若使用精确线搜索，该算法退化成标准的HS共轭梯度法.且在适当的假设条件下，证明了文章提出的算法具有全局收敛性，最后数值实验表明，文章提出的算法是可行的.

无约束优化；修正HS共轭梯度法；Wolfe线搜索；全局收敛性；数值实验

共轭梯度法是解决大规模无约束优化问题的有效方法，至今对共轭梯度优化算法各种新的变形的研究仍然很活跃，其原因是它既能克服最速下降法迭代过程中产生的锯齿现象，又能避免牛顿法在求Hessian矩阵及其逆矩阵时的困难，它具有运算简便和占用存储空间少的优点，在经济、管理和工程计算等方面有着广泛的应用，相关研究见文献[1-7].

本文考虑如下优化问题：

其中f∶Rn→R为连续可微函数.

求解问题（1）的共轭梯度法的迭代公式为：

其中αk>0为搜索步长，dk为搜索方向，gk=g（xk），βk为参数.

共轭梯度法的关键是参数βk的选取，常用的βk公式有如下几种：

其中yk-1=gk-gk-1.

文献[8-9]对βk的构造及算法的收敛性做了大量的研究.文献[9]指出，PRP，HS方法在数值计算中有很好的表现，但是即使使用精确线搜索PRP方法也不会有全局收敛性.FR，DY方法则具有较好的收敛性质.为寻求兼具良好收敛性和优秀数值结果的算法，许多研究者在经典共轭梯度法的基础上推出新的βk公式.

本文提出一个新的修正HS共轭梯度法，优点是：

（i）由修正HS共轭梯度法产生的方向总是目标函数的下降方向，且不依赖于使用何种线搜索；

（ii）若使用精确线搜索，则修正HS共轭梯度法退化成标准的HS共轭梯度法；

（iii）本文定理3.3中的条件比文献[1]中的一致凸条件弱.

在一些适当的假设条件下，证明本文提出的算法具有全局收敛性，且数值实验表明本文的算法具有较好的数值结果.

1 新的修正HS共轭梯度法

受文献[10]的启发，改进（3）中的搜索方向，构造如下搜索方向：

对任一线搜索有：

这表明搜索方向dk是目标函数的下降方向，若使用精确线搜索，有dk-1=0，即θk=0，则本文提出的修正HS共轭梯度法退化成标准的HS共轭梯度法.

概括上述讨论，显然有下面的定理：

定理1 搜索方向dk由（4）式定义，则在任何线搜索下，dk是f（x）在xk处的下降方向.进一步，若使用精确线搜索，则dk与标准的HS共轭梯度法产生的方向相同.

基于定理1，提出一个新的修正HS共轭梯度法.算法1 新的修正HS共轭梯度法（MHSCG）

步0：初始点 x0∈Rn，参数0<μ1<μ2<1，误差限0<ε<1，令k=0；

步1：若‖‖

gk≤ε，算法停止；否则转下一步；

步2：计算（4）式定义的搜索方向dk；

步3：计算步长αk：

步4：令xk+1=xk+αkdk；

步5：循环k≔k+1.令，转步1.

2 全局收敛性分析

为证明算法1具有全局收敛性，先作如下基本假设.

H1水平集Ω={x0∈Rn|f (x)≤f(x0)}有界.

H2在Ω的某邻域N内，f（x）连续可微，且其梯度g（x）是Lipchitz连续的，即存在一常数L>0使得

由假设H1、H2知，存在一常数M>0满足

[1]、文献[10]，有如下两个引理.

引理1[10]若假设条件H1、H2成立，则算法是良定的.

引理2[1]若假设条件H1、H2成立，对任一共轭梯度法的迭代形式（2），其中dk满足dk<0且αk满足Wolfe条件（6）和（7），则

式（11）结合式（5）有

定理2 如果假设H1、H2成立，在新的修正HS共轭梯度法下产生一无穷序列，若存在一常数满足

由（10）知，存在一常数ρ∈(0,1)，存在一正整数k，使得当k≥k0有

因此，对∀k>k0有

3 数值实验

为进一步从数值计算的角度分析算法的可行性，通过Matlab编程将算法进行数值实验，实验结果表明本文提出的新的修正HS共轭梯度法是可行的.

问题1的实验结果见表1.

表1 问题1的数值实验结果Tab.1 Numerical results for question 1

问题1的实验结果见表1.

表2 问题2的数值实验结果Tab.2 Numerical results for question 2

表3 问题3-9的数值实验结果Tab.3 Numerical results for question 3-9

4 结论

本文提出了一个新的修正HS共轭梯度算法，该算法的特点是：搜索方向总是目标函数的下降方向，且不依赖于使用何种线搜索；若使用精确线搜索，该算法退化成标准的HS共轭梯度法；定理2中的条件比文献[1]中一致凸条件弱.

在适当的假设条件下，本文证明了提出的新的修正HS共轭梯度法具有全局收敛性，最后数值实验结果表明提出的算法是可行的.

参考文献：

[1]Ioannis E,Livieris,Panagiotis Pintelas.Globally convergent modified Perry's conjugate gradient method[J].Applied Mathematics and Computation,2012,218:9197-9207.

[2]Shi Z J.Restricted PR conjugate gradient method and its global convergence[J].Adv Math,2002,31(1):47-55.

[3]Shi Z J.Convergence of PRP method with new non-mono⁃tone line search[J].Applied Mathematics and Computation, 2006,181:423-431.

[4]景书杰,邓涛.精确搜索下具有充分下降性的混合共轭梯度法[J].河南理工大学学报:自然科学版,2010,29(2):266-270．

[5]景书杰,赵海燕,邓涛.修正的共轭梯度法在两种线搜索下的全局收敛性[J].河南理工大学学报:自然科学版,2012, 31(3):364-368．

[6]黄海.Wolfe线搜索充分下降的修正DY共轭梯度法[J].河南理工大学学报:自然科学版,2013,32(3):368-372．

[7]李敏,陈宇,屈爱平.一种充分下降的DY共轭梯度法及其收敛性[J].山东大学学报:理学版,2011,46(7):101-106.

[8]AL BAALI M.Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J]. IMA Journal of Numerical Analysis,1985,5(1):121-124.

[9]POWELL M J D.No-convex minimization calculations and the conjugate gradient method[C].Lecture Notes in Mathematics:Vol 1066.Berlin:Springer-Verlag,1984:122-141.

[10]Zhang L,Zhou W,Li D.A descent modified PRP conju⁃gate gradient method and its global convergent[J].IMA Journal of Numerical Analysis,2006,26:629-640.

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

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

责任编辑：毕和平

A New Modified HS Conjugate Gradient Method and the Global Convergence

CHEN Fenghua，LI Shuangan，CHEN Huiyan
（Wanfang Institute of Science and Technology，Henan Polytechnic University，Zhengzhou451400，China）

In this paper,we propose a new modified HS conjugate gradient method for unconstrained optimization.An at⁃tractive property of the proposed method is that the direction generated by the method is always a descent direction for the ob⁃jective function.This property is independent of the line search used.In particular,exact line search is used,the method re⁃duces to the standard HS conjugate gradient method.Under appropriate conditions,we show that the new modified HS conju⁃gate gradient method with Wolfe line search is globally convergent.Numerical experiments show that the proposed algorithm is effective.

unconstrained optimization；modified HS conjugate gradient method；Wolfe line search；global convergence；numerical experiments

O 224

：A

：1674-4942（2015）01-0001-04

2014-10-29

国家自然科学基金（11361018）；广西杰出青年基金（2012GXSFFA060003）；河南省教育厅科学技术研究重点项目（12B110011）