Wolfe线搜索下一种修正的HS共轭梯度法及其全局收敛性

王安平，陈 忠

考虑无约束优化问题

其中：f：Rn→R为连续可微函数.因为共轭梯度法具有算法简单，易于编程及存储空间小等优点，所以共轭梯度法是求解无约束优化问题（1）的一类重要方法，一般共轭梯度法的迭代公式为

其中：x1为初始点，dk为搜索方向，αk由某种线性搜索或由特定公式计算出的步长因子，βk为参数，gk＝▽f（xk）.

关于βk的著名公式有

其中：‖·‖为欧式范数，它们对应的共轭梯度法依次称为 FR［1］方法、PRP［2－3］方法、HS［4］方法、CD［5］和DY［6］方法.对于目标函数非凸的情况下，这些共轭梯度方法的收敛性分析和数值表现差别较大，一般情况下，FR、CD和DY方法有较强的收敛性，HS和PRP方法却有很好的数值实验效果.作者继续关注HS方法.许多学者从不同角度研究了HS共轭梯度法.文［7］提出了一种改进的HS算法，并在Wolf e线搜索下证明该算法的全局收敛性，其中

文［8］提出了一种充分下降HS算法，并在强Wolfe线搜索下证明该算法的全局收敛性，其中

文［9］提出了一种充分下降的3项HS方法，并在Wolfe线搜索下证明该算法的全局收敛性，其中

文［10］提出了一种充分下降的PRP方法

其中

受上述文献的启发，作者尝试对HS方法进行改进，希望获得其更多优点，在每一步迭代的搜索方向均为充分下降的.搜索方向dk利用式（7），其中

1 新算法及其全局收敛性分析

论文的步长策略为Wolfe 线搜索，即选取αk＞0，满足

其中：δ和σ是满足0＜δ＜σ＜1的常数.

作者提出了一种修正的HS共轭梯度算法，记为WHS方法：

步骤1 给定初始点x1∈Rn及收敛精度ε＞0，d1＝－g1，令k：＝1；

步骤2 若‖gk‖≤ε，则停止迭代；否则由式（7）和（9）求得dk；

步骤3 按照 Wolfe线搜索式（10）、（11）来计算步长αk；

步骤4 计算xx＋1＝xk＋αkdk，置k：＝k＋1，转步骤2.

为了证明论文算法的全局收敛性，作如下必要的假设：

（1）f（x）在水平集L1＝｛x∈Rn｜f（x）≤f（x1）｝有界，其中x1为初始点；

（2）f（x）在水平集L1的某个邻域U 内连续可微，其梯度g（x）是Lipschitz连续的，即存在常数L＞0，使得

引理1 设目标函数f（x）满足假设，αk满足式（10）、（11），有

此关系式称为Zoutendijk条件.

证明 由式（11）、（12），则有

再联合式（10）可以得到

对式（15）两端进行累加，并注意到假设中（1），所以，有

定理1 设目标函数f（x）满足假设条件，迭代点列xk由式（2）确定，αk满足式（10）和式（11），dk由式（7）和式（9）产生.假设存在一个正数α＊，满足αk≥α＊，则有

证明 由假设中的（1），则存在一个常数M＞0，使得‖αkdk‖＝‖sk‖≤M，由式（18）和αk≥α＊，得到

由式（12）、（13）和－dTkgk＝‖gk‖2，可以得到式（17），即定理得证.

2 数值试验

利用文［11－12］中的部分测试函数检验论文算法，并将结果与文［9］的方法和标准HS方法比较.所有实验均采用Wolfe线搜索，均不采用重新开始策略.测试环境为MATLAB7.9.0，运行环境为内存4.00 GB、CPU为2.60 GHz的个人计算机.参数设置为：δ＝0.1，σ＝0.45，论文算法中μ＝0.3，终止条件为‖gk‖≤10－6或It－li mit＞9 999.计算得到3种方法的数值结果如表1所示.

通过测试可以看出，论文提出的WHS算法要比HS方法优越很多，而且大部分算例的计算效果比文［9］中的方法更有效.总体上说，作者提出的共轭梯度法具有良好的数值性能.但为了能得到更好的数值效果，还有待进一步研究搜索条件的选择.

表1 数值测试结果及其比较Tab.1 The results of numerical test and comparison

致谢 作者感谢万仲平教授在此论文写作上的帮助.

［1］ Fletcher R，Reeves C.Function mini mization by conjugate gradients［J］.Co mputer Jour nal，1964（7）：149－154.

［2］ Polak B，Ribiere G.Note surla conver gence de directions conjugees［J］.Rev Fran－caise Infor mat Recherche Opertionelle，1969，16：35－43.

［3］ Polyak B T.The conjugate gradient method in extreme problems［J］.USSR Computational Mat hematics and Mathematical Physics，1969，9：94－112.

［4］ Hestenes M R，Sriefel E L.Methods of conjugate gradient for solving linear systems［J］.Jour nal of Research of the National Bureau of Standards，1952，49（6）：40－43.

［5］ Fletcher R.Practical methods opti mization［C］／／John Wiley ＆ Sons，Unconstrained Opti mization，1987：26－31.

［6］ Dai Y H，Yuan Y.A nonlinear conjugate gradient with a str ong global conver－gence pr operty［J］.SIA M Jour nal on Opti mizton，2000，10：177－182.

［7］ 王开荣，刘金魁，邹黎敏.一种修正的HS共轭梯度法及全局收敛性［J］.高等学校计算数学学报，2010，32（2）：150－156.

［8］ Wei Z X，Huang H D，Tao Y R.A modified Hestenes－Stiefel conjugate gradient method and its convergence［J］.Journal of Mathematical Research and Exposition，2010，30（2）：297－308.

［9］ Zhang L，Zhou W，Li D.So me descent three－ter m conjugate gradient methods and their global convergence［J］.Optimisation Methods and Soft ware，2007，22（4）：697－711.

［10］ Chen Y Y，Du S Q.Nonliear conjugate gradient methods with Wolfe type line search［J］.Abstract and Applied Anlysis，2013，2：1－5.

［11］ More J J，Garbow B S，Hillstrome K E.Testing unconstrained opti mization soft ware［J］.ACM Trans Math Sofeware，1981，7：17－41.

［12］ Andrei N.An unconstrained opti mization test f unctions collection［J］.Advanced Modeling and Opti mization，2008，10（1）：147－161.