一种改进的DY共轭梯度法及其全局收敛性

王安平 （长江大学工程技术学院基础教学部，湖北 荆州434020）

马 烁 （荆州理工职业学院基础课部，湖北 荆州434000）

考虑无约束优化问题：

式中，f：Rn→R连续可微。共轭梯度法是求解该问题的一类有效算法。一般的共轭梯度法迭代公式为：

式中，x1为初始点；dk为搜索方向；αk是由某种线性搜索或由特定公式计算出的步长因子；βk为标量；g（x）＝ ▽f（x），gk＝ ▽f（xk）。共轭梯度法的关键是选取αk和βk，不同的αk和βk决定了不同的共轭梯度算法。常用选取αk的线搜索是标准Wolfe线搜索，即选取αk＞0满足：

式中，δ和σ是满足0＜δ＜σ＜1的常数。而βk的选取公式常用的有：

对应的共轭梯度法依次为FR方法［1］、PRP方法［2］、HS方法［3］、CD方法［4］、LS方法［5］和 DY 方法［6］。

在众多共轭梯度法中，为了保证下降方向，许多学者都做了深入的研究。文献 ［7］提出了一种改进的DY共轭梯度法，参数βk的计算公式为：

受文献［7］的启发，笔者在MDY方法的基础上，给出了一个新的参数βk的取法，即：

1 改进的DY算法及其充分下降性

改进的DY算法如下：

步1 给定初始点x1∈Rn，ε＞0，d1＝－g1，令k＝1；

步2 若‖gk‖≤ε，则停止迭代；否则转入步3；

步3 由式（3）求得αk；

步4 计算xx＋1＝xk＋αkdk，若 ‖gk＋1‖ ≤ε，则算法停止，否则转步5；

步5 利用式（4）计算βk＋1。计算dk＋1＝－gk＋1＋βk＋1dk，置k＝k＋1，转步2。

定理1 设迭代方向由：

证明 当k＝0时，dT0g0＝－‖g0‖2，结论成立。

当k≥0时，dk＝－gk＋βNMDYkdk－1两边与gk做内积：

2 算法的全局收敛性

下面笔者将在一定的假设条件下证明NMDY算法的全局收敛性。假设条件（A）如下：

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

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

‖g（x）－g（y）‖ ≤L‖x－y‖ ∀x，y∈U引理1 设目标函数f（x）满足假设A，序列｛xk｝由式（2）产生，其中βk由（4）计算，αk满足式（3），则。此关系式称为Zoutendijk条件。

证明 由定理1及式（3），则有：

则式（6）说明了函数列｛fk｝有界。再由定理1及式（3）和假设条件（A）中的第2个条件，则有：

再联合式（3）可以得到：

又因为函数列｛fk｝有界，所以有：

定理2 设目标函数f（x）满足假设条件A，序列｛xk｝由式（2）产生，其中βk由式（4）计算，αk由式（3）确定。假设存在一个正数α＊，满足αk≥α＊，则有：

证明 由假设A中的（1），则存在一个常数M＞0使得：

由式（8）和αk≥α＊，可以得到：

由式（9）及引理1和定理1的结论，可以得到式（7），即定理2得证。