一个修正的三项LS 共轭梯度法

焦佳佳

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



一个修正的三项LS 共轭梯度法

焦佳佳

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

摘要:基于已有的共轭梯度法的思想，提出了一个三项LS共轭梯度方法，该方法能保证搜索方向在不需要任何线搜索下具有充分下降性，并在适当条件下获得此方法对一般函数的全局收敛性．

关键词:共轭梯度法;充分下降性;全局收敛性

1基础知识

考虑无约束优化问题:

其中f: Rn→R是连续可微函数．共轭梯度法是求解大规模无约束优化问题( 1)的一种有效方法，其迭代格式如下:

其中gk=f( xk)，dk是搜索方向，k是用某线搜索得到的步长，k是参数．不同的参数表达式k对应着不同的共轭梯度法，著名的有FkR，PkRP，HkS等．常用的线搜索有Wolfe线搜索、强Wolfe线搜索、Armijo-type线搜索等，其中Wolfe线搜索要求k满足

与其他共轭梯度法相比，PRP方法的数值表现是目前认为最好的方法之一，但该方法的收敛性不理想．研究发现，PRP方法收敛性不好的另一个原因在于它不具有充分下降性．充分下降性是指对所有的k，式( 7)成立:

其中c为常数，此性质在收敛性分析中起着非常重要的作用．因此，许多学者都希望找到数值表现可与PRP相媲美同时性质又比其好的方法．

Yu，Guan和Li在文献［4］中提出了具有充分下降性的修正PRP方法，其公式为

Zhang等在文献［5］中给出一个三项的PRP共轭梯度法，其方向定义为

与三项PRP方法类似，具有充分下降性的三项LS公式定义为

此方法仅仅利用了梯度值信息，忽略了函数值信息．文献［6］中给出了新的拟牛顿方程:

此拟牛顿方程同时含有函数值信息和梯度值信息，且比原拟牛顿方法具有更好的收敛性和数值表现．受此启发，此处给出一个三项LS共轭梯度方法，其方向定义为

2算法及其全局收敛性分析

为表述需要，称修正的三项LS共轭梯度算法为MMLS算法，其步骤如下: 步0:给出初值x1Rn，≥0，令d1=－g1，k=1;

步1:若g1≤，则停止，否则转步2;

步3:令xk+1=xk+kdk，gk+1=g( xk+1)，若gk+1≤，则停止，否则转步4;

步5:令k=k+1，转步2．

为了讨论新方法的全局收敛性，假定目标函数满足如下基本假设:

成立．

引理1对k≥0，三项LS公式的搜索方向满足

证明如果k=0，则gT0d0=－‖g0‖2，那么式( 15)成立．当k≥1时，利用新方向的定义可得

证毕．

则存在一个常数M＞0，使得

根据dk的定义，由式( 13) ( 14) ( 16)和( 18)可得

由式( 6)和假设( A)知

因此，对所有的k≥k0，由式( 19)和( 21)有

定理1假设( A)和假设( B)成立，dk由式( 11)确定，k由Armijo-type线搜索获得，则gk=0．

由中值定理，引理( 2)，式( 13)和( 15)，存在hk( 0，1)，使得

3结论

对于求解大规模无约束优化问题，给出了一种修正的三项LS共轭梯度法，该方法不依赖任何线搜索，具有充分下降性，并且在Armijo－type线搜索下证明了该方法的全局收敛性．

参考文献:

［1］ANDREI N．A Dai-Yuan Conjugate Gradient Algorithm with Sufficient Descent and Conjugacy Conditions for Unconstrained Optimization［J］．Applied Mathematics Letters，2008，21( 2) : 165-171

［2］LIU Y，STOREY C．Efficient Generalized Conjugate Gradient Algorithms，Part 1: Theory［J］．Journal of Optimization Theory and Applications，1991，69( 1) : 129-137

［3］GILBERT J C，NOCEDAL J．Global Convergence Properties of Conjugate Gradient Methods for Optimization［J］．SIAM Journal on Optimization，1992，2( 1) : 21-42

［4］YU G，GUAN L，LI G．Global Convergence of Modified Polak-Ribiere-Polyak Conjugate Gradient Methods with Sufficient Descent Property［J］．Journal of Industrialand Management Optimization，2008( 4) : 565-579

［5］ZHANG L，ZHOU W，LI D H．A Descent Modified Polak-Ribière-Polyak Conjugate Gradient Method and Its Global Convergence ［J］．IMA Journal of Numerical Analysis，2006，26( 4) : 629-640

［6］LI D H，FUKUSHIMA M．A Modified BFGS Method and Its Global Convergence in Nonconvex Minimization［J］．Journal of Computational and Applied Mathematics，2001( 1) : 15-35

［7］NARUSHINMA Y，YABE H，FIORD J A．A Three-term Conjugate Gradient Method with Sufficient Descent Property for Unconstrained Optimization［J］．SIAM Journal on Optimization，2011，21( 1) : 212-230

A Modified Three-term LS Conjugate Gradient mMethod

JIAO Jia-jia

( College of Mathematics Science，Chongqing Normal University，Chongqing 401331，China)

Abstract:Based on the existent ideas of the conjugate gradient method，this paper proposes a three-term LS conjugate gradient method．The presented method can make the search direction with sufficient descent property without any line search．Under certain mild conditions，global convergence is obtained．

Key words:Three-term Conjugate Gradient Method; sufficient descent property; global convergence

作者简介:焦佳佳( 1988-)，女，陕西铜川人，硕士研究生，从事最优化方法及其应用研究．

收稿日期:2014－08－10;修回日期: 2014－10－08．

doi:10．16055/j．issn．1672－058X．2015．0005．004

中图分类号:O224

文献标识码:A

文章编号:1672－058X( 2015) 05－0013－04