敖 卫 斌

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

一种修正的DY共轭梯度法的全局收敛性

敖 卫 斌

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

提出了一种新的非线性修正的DY共轭梯度算法(MDYCG),该算法得到的搜索方向为下降方向，它既不受线搜索规则的影响；也不受目标函数的凸性影响；在精确线搜索下，MDYCG算法化归为标准的DY共轭梯度算法；证明了该方法在Armijo型线搜索下的全局收敛性，给出了初步的数值结果。

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

0 引 言

考虑无约束优化问题：

minf(x),x∈Rn

(1)

其中f：Rn→R为连续可微函数，其梯度向量记为g(x)，简记为g。

共轭梯度法是求解大规模无约束优化问题的有效算法之一，它像最速下降法一样在每步迭代中不需要存储和计算矩阵，其迭代格式：

xk+1=xk+αkdk

(2)

(3)

其中，gk=f(xk)，dk为搜索方向，αk是通过一维线搜索获得的步长，βk为标量。不同的βk对应着不同的共轭梯度算法。1964年, Fletcher和Reeves首先提出非线性共轭梯度法参数βk，它定义为还有其他著名的βk，比如：

其中‖·‖为欧几里得范数,yk-1=gk-gk-1。FR方法、CD方法和DY方法具有较好的理论收敛性，然而PRP方法、HS方法和LS方法具有较好的数值计算结果。

在文献[9]的启发下，选取不同的βk，提出了一种修正的DY算法(MDYCG)并证明了该算法在Armijo型线搜索下的全局收敛性。所采用的Armijo型线搜索准则，取步αk：

αk=max{ρj,j=0,1,2,…}

(4)

(5)

其中ρ∈(0,1),δ1∈(0,1),δ2>0。

2 修正的DY新算法

本文给出的新算法迭代式(2)和式(6)：

(6)

(7)

下面给出新的算法步骤：

(1) 给出x1∈Rn，ρ∈(0,1),δ1∈(0,1),δ2∈(0,1),ε≥0，令k：=1,d1=-g1，若‖g1‖≤ε，立即停止；

(2) 找到αk>0满足Armijo型线搜索规则；

(3) 令xk+1=xk+αkdk, 且gk+1=g(xk+1)，若‖gk‖≤ε，立即停止；

(5) 令k=k+1，返回(2)。

本文做如下假设：

(A)f(x)在水平集Ω={x∈Rn|f(x)≤f(x1)}有下界，其中x1为初始点……