一类保证充分下降性的YT型共轭梯度算法

程万友, 叶剑豪, 张嘉昊

（东莞理工学院 计算机科学与技术学院，广东 东莞 523808）

考虑如下无约束优化问题：

其中f连续可微。共轭梯度算法由于要求内存小且收敛速度快，是求解大规模问题(0.1)的有效方法之一。共轭梯度算法满足如下迭代形式：

并证明了当使用Armijo 型线搜索或广义Wolfe 线搜索时，算法全局收敛。数值结果表明该方法是有效的。更多的下降性共轭梯度算法可以参考文献[2-4,15,18]。

Yabe 和Takano[17]利用目标函数的二阶信息和DL 共轭条件[6]，给出如下YT 方法：

称为YT 型共轭条件。本文将基于施密特正交化方法以及YT 型共轭条件给出一类新的YT 型共轭梯度算法。新算法的一个重要特性是产生的方向总是满足充分下降条件，且不依赖于任何线搜索。当使用精确线搜索时和合适的参数下，新算法退化为标准的HS 方法。在一定条件下，我们证明算法在标准Wolfe 线搜索条件下对于一致凸函数与一般函数具有全局收敛性。

1 新算法的动机

在本节，我们将给出新算法。注意(0.4)产生的充分下降性与共轭参数的选取无关，我们将其写成如下形式：

利用(0.5)得到

联立(1.1)与(1.2)得

由(1.3)计算得：

其中

其中

2 收敛性分析

本节将给出新算法在一致凸函数与一般函数下的全局收敛性证明。假定目标函数满足下面假设。

假设1

从而有如下Zoutendijk 定理，该定理对建立算法的全局收敛性非常重要，但证明与文献[20]中提出的略有不同，我们给出详细过程。

引理2.1考虑满足(0.2)和(1.1)任意共轭梯度算法，如果搜索方向满足下降方向(1.6)，步长由标准Wolfe 准则(1.7)获得，则

证明:由(2.2)得：

另一方面，结合(1.6)(1.7)得：

于是由(2.4)(2.5)得可知：

由(1.7)第一个不等式可知：

将上式两边求和，即有引理2.1 成立。

在接下来的分析中，总假设

结合(2.9)和(2.10)，有：

2.1 一致凸函数下的收敛性分析

本小节我们将证明在目标函数一致凸假设下,新算法的全局收敛性。目标函数一致凸，即存在常数使得：

上式等价于:

由(2.12)和(2.13)可知：

定理2.1若假设1 成立，目标函数一致凸，满足(2.9)，步长由标准Wolfe 准则(1.7)给出。如果，则对于一切，由(0.2)，(1.1)，(1.4)确定的新算法满足。如果则当时，新算法满足

证明：由(2.14)和可知：

此时:

此时

由(2.19)和(2.20)可知，总有

2.2 一般函数下的收敛性分析

本节将证明一般函数下新算法的全局收敛性。为保证新算法的全局收敛性以及进一步提升算法性能，将取做如下形式：

下面的引理指出，在一定条件下，算法的搜索方向将缓慢且渐进变化。

引理2.2若假设1 成立，对于使用(1.1)，(0.2)和(2.23)的新算法，若(2.9)成立，步长由标准Wolfe准则(1.7)给出。当时，总有且

证明：由(1.6)可知，否则算法将终止。

令：

再令：

于是：

另一方面，由(1.7)和(1.6)得：

因此

情况1：由(2.28)和(1.5)，此时显然有

情况2：由(1.5)和(2.20)可知

下面估计 的上界。

情况1：由(2.26)，(1.5)，(2.29)，(2.1)和(2.3)得

情况2：由(2.26)，(1.5)，(2.30)，(2.1)和(2.3)得

由(2.31)和(2.32)得

由(2.33)，(2.27)和定理2.1 可知

从而(2.25)成立。

实际上，由(2.8)可知：

引理2.3若假设1 成立，对于使用(1.1)，(0.2)和(2.23)的新算法，(2.9)式成立，步长由标准Wolfe准则(1.7)给出。当时，存在常数使得

且有

证明：情况1：由(2.24)，(2.28)和(2.1)可知：

再令：

引理2.4对于新算法，若引理2.2 的条件成立，若(2.24)成立，则存在使得对于任意，及任意下标，总存在使得

证明：我们使用反证法。假设（2.40）不成立，即对于任意存在及下标，使得

另一方面，(1.1)可改写为：

从而：

立即有：

于是：

由(2.45)(2.43)可知：

这与(2.8)矛盾，从而(2.40)成立。

结合引理2.2，引理2.3，执行与[6]中定理2.6 相似的分析，我们可以证明以下全局收敛性定理。

定理2.2若假设1 成立，对于新算法(1.1)(0.2)(2.23)，若(2.9)成立，步长由标准Wolfe 准则(1.7)给出。

证明：我们使用反证法，即假设(2.24)成立，则引理2.2，引理2.4 也成立。令，任取两个指标使得，从而有如下关系式：

3 数值结果

本节将给出新算法的数值结果。所有测试均在Windows10 操 作 系 统（ 64 位）， Intel(R)Core(TM)i3-8145UCPU @2.10GHz 2.30GHz,4.00GB 下进行。我们的测试包含如下五种算法：（1）“新算法”代表(2.23)所确定的新算法；（2）CG_DESCENT(5.3)；（3）YT+[17]; （4）KNY：[14]中第五节(i)提出的新算法；（5）CGOPT[8]。

选取文献[1]中的84 个函数进行测试，维数分别选 取 1000 与 10000 。 新 算 法 的 参 数 为经典YT+算法与新算法中算法中，所有算法均使用标准Wolfe 准则确定步长，参数为

图1 迭代次数(NI)对比 (1 000dim)

图3 至图6 分别展示了5 种算法在CPU 时间，迭代次数，函数估计次数与梯度估计次数的性能指标，测试问题维度选取为1 000 维+10 000 维。新算法略优于CG_DESCENT 算法,与CGOPT 相近，且明显优于YT+算法与[14]中第五节提出的新算法，即图中的KNY算法，这充分说明我们的新算法是非常有效的。具体来说，在168 个测试问题中，新算法与CG_DESCENT都解决了94.6%的问题，就迭代次数而言，有120 个问题新算法的迭代次数小于等于CG_DESCENT。总体上讲，新算法为求解无约束优化问题提供了一种新的有效方法。同时，注意到算法对参数的选取十分敏感，且在10 000 维度下，相较于CG_DESCENT 使用更多的CPU 时间，这可能是因为参数的影响而导致，因此，更多对新算法参数的合适选取仍有待研究。

图3 CPU 使用时间对比(1 000+10 000dim)

图4 迭代次数对比(1 000+10 000dim)

4 总结

本文基于施密特正交化与YT 型共轭条件，给出一类修正的YT 型共轭梯度算法。新算法的一个重要特性是产生的方向总是满足充分下降条件，且不依赖于任何线搜索。当使用精确线搜索且在合适的参数下，新算法退化为标准的HS 方法。在一定条件下，我们证明算法在标准Wolfe 线搜索条件下对于一致凸函数与一般函数具有全局收敛性。数值结果表明新算法具有优良的数值性能。