张小让,朱志斌,邢明燕

一种修正下降的非线性共轭梯度法

张小让,朱志斌,邢明燕

(桂林电子科技大学数学与计算科学学院,广西桂林 541004)

为求解无约束优化问题,基于MMHS方法和DY方法,提出了一种修正下降的非线性共轭梯度法。在Armijo线搜索下,该算法是全局收敛的。数值实验证明了该算法的有效性和可行性。

无约束优化;共轭梯度法;Armijo线搜索;全局收敛性

令f:Rn→R连续可微,并考虑如下无约束优化问题:

用共轭梯度法[1]求解问题(1),迭代步为:

其中:αk(αk≥0)为步长,由一定的线搜索决定;dk为搜索方向,满足(g(x))Tdk＜0。并定义:

其中βk为参数。MHS[2]方法和DY[3]方法是2个熟悉的共轭梯度法,其参数βk定义为:

其中:gk=g(xk);g(x)=▽f(x);yk-1=gk-gk-1;sk=xk+1-xk;‖•‖为欧几里得范数。另外,Armijo线搜索[4]是普遍采用的精确线搜索,给定δ∈(0, 1),ρ∈(0,1),并令

满足线搜索条件:

易知,若采用Armijo精确线搜索,可得到一个下降方向。为此,构建一个新的共轭梯度法,证明在Armijo线搜索下算法的全局收敛性。

1 修正的非线性共轭梯度法

文献[5]对MFR方法[6-8]和MPRP方法[6-10]进行处理,给出了一种由DY和MMHS[2]所构造的共轭梯度法,称为修正的非线性共轭梯度法(简称DYMMHS方法)。用此共轭梯度法解决问题(1),在DY方法和MMHS方法中,搜索方向dk分别为:

其中:

基于式(11),给出一种共轭梯度法,并称为DYMMHS方法。

算法1(DY-MMHS方法) 给定常数δ,λ∈(0,1),ρ∈(0,1),ε＞0,选择一个初始点x0∈Rn,并令k∶=0。

1)通过式(11)计算dk,当‖gk‖＜ε时,中止。

2)用Armijo精确线搜索计算步长αk。

3)令xk+1=xk+αkdk。

4)令k∶=k+1,并返回步骤1)。

DY-MMHS方法可产生目标函数的充分下降方向,此性质独立于线搜索,且算法具有二次终止性。

2 收敛性分析

通过分析算法的全局收敛性,做出如下基本假设[]。……