共轭梯度法和最速下降法的混合算法

1、 收稿日期:1998-10-15第一作者:男,1970年生,硕士,讲师共轭梯度法和最速下降法的混合算法欧志英严克明王柏岩(甘肃工业大学基础科学系,兰州730050摘要将共轭梯度法与最速下降法有机地结合起来,构造了一种共轭梯度法和最速下降法的混合算法,并证明了该算法的全局收敛.混合算法既提高了共轭梯度算法的收敛速度,又解决了目标函数“性态不优”时,最速下降法难以求解的问题.同时也可以看到共轭梯度法与最速下降法仅仅是混合算法的特例.关键词混合算法共轭梯度法最速下降法全局收敛分类号O224FR 算法是Fletcher 和Reev s 共同提出的一种共轭梯度算法1.由于FR 算法具有二次终止性,内存需

2、要量小,主要存储四个n 维向量(x k ,g k ,g k -1,p k -1,程序简单,具有较快的收敛速度,因此它是解决无约束优化问题,特别是大规模问题的一个重要方法.但是FR 算法的计算效果总不如人意,当 f (x k 较小时,FR 算法收敛较慢.最速下降法具有较高的局部收敛速度,但在有的情况下全局收敛速度不高,如目标函数“性态不优”时,其收敛速度就较慢.本文给出一种将共轭梯度法与最速下降法有机地结合起来的新算法混合算法,在保证相同的计算量前提下,它将进一步提高FR 算法的计算效果.1算法混合算法的步骤如下:1取初始点x 0R n ,T >0,U >0,置k =1;2计算g k

3、 =g (x k = f (x k ;3若g k =0,则停止计算,否则置:p k =-g k +U k -1p k -1其中,U k -1=0(k =1g k 2g k -12(k >1;4若 f (x k 较大,取U 12,1;否则,取U 0,12;5若d 1(d 为目标函数f (x 的Hessian 阵的条件数,取T 0,12;否则,取T 12,1;6p k =-T g k +U p k ;第25卷第1期7一维搜索,求k ,使得f (x k +k p k =min f (x k +p k |>0;8置x k +1=x k +k p k ,k =k +1,返回步骤2.对于上述算

4、法,给出以下几点注释:1p 1,p 2,p k ,是共轭方向.从文1中已知FR 算法得到的p 1,p 2,p k ,是共轭方向,满足:(p i ,p j G =0(j i 因而可得知:(p i ,p j G =0(j i 即p 1,p 2,p k ,是共轭方向.2p 1,p 2,p k ,是目标函数的下降方向.(-g k ,p k =(-g k ,-T g k +U p k =(-g k ,T g k +(-g k ,U p k =T g k 2+U (-g k ,-g k +k -1j =1U jp j =g k 2>02混合算法的全局收敛引理1设函数f (x 二阶连续可微, f (x

5、 满足Lipschitz 条件,且k =1cos 2d k ,-g k <+,其中d k 为搜索方向.则利用共轭梯度法和精确线性搜索所得到的点列x k 必有限终止,或者下面两极限必有一为真2:lim k f (x k =-lim k inf f (x k =0由引理1可知,只要夹角d k ,-g k 不为2,则共轭梯度算法在满足引理1的条件下是全局收敛的.定理1混合算法在满足引理1的条件下是全局收敛的.证明由于(-g k ,p k g k 2,因此,co s -g k ,p k 0,则-g k ,p k 不为2.从引理1知定理1成立.3混合算法的计算效果分析从算法中可知,混合算法和FR

6、算法的计算量大致相同,但计算效果却有不小的差异.一般来说前者优于后者,为说明这个问题,举例如下3:考虑min x R 2f (x ,其中在圆域D 内f (x =12(x 21+x 22,在D 的边界是连续可微函数,在D 的边界上是光滑联接的.设想从D 的边界外某一点出发,经过若干次迭代后达到D 内某点x k ,并且已经确定了共轭方向p k ,现从x k 出发,分别用FR 算法和混合算法进行计算,并对它们的进展情况作出比较.p k g k co s k =(p k ,-g k =g k 2sec k =p k g k ·90·甘肃工业大学学报第25卷g k p k co s

7、k =(p k ,-g k =(T +U g k 2sec k =-T g k +U p k (T +U g k 1g k <p k g k =sec k 因此,k >k ,并且可以证明k =k +1.这说明了对于FR 算法来说,即使对于性态很好的目标函数,倘若某次搜索方向很不理想,仍会使得以后的每次迭代都只能取得很小的进展.但是对于混合算法则不一样,它具有朝最速下降方向靠拢的性质.由此可见,混合算法要比FR 算法的计算效果优.同时还可看到:T =0时,混合算法就是FR 算法;U =0时,混合算法就是最速下降法.4结论1最速下降法和FR 算法仅是混合算法的特例.2混合算法的搜索方向

8、是关于目标函数f (x 的Hessian 阵共轭.3混合算法的计算效果要比FR 算法的计算效果优,且全局收敛;但是否具有比FR 算法更高的Q 收敛速度,还需要进一步探讨.参考文献A mixed method of conjugate gradient methodand steepest descent methodOu Zhiying ,Yan Keming ,Wang Baiyan(Dept.o f Basic Sciences,Ga nsu U niv.of T ech.,Lanzh ou 730050Abstract The co njugate g radient method an

9、d the steepest descent method a re combined ,and a mix ed method o f conjug ate g radient m ethod and steepest descent is created ,and its g lobal conv ergence is prov ed.The mixed m ethod raise the co nv erg ent rate o f the co njugate g radient method,and solve the problem which the steepest descent method can no t solv e in the conditio n with badly cha racteristics for the o bjectiv e function .In the m eantime ,it can be seen that the co njuga te g radient m ethod o r steepest descent metho d is a special case o f t