一類保證充分下降性的YT型共軛梯度算法

程萬友, 葉劍豪, 張嘉昊

（東莞理工學院 計算機科學與技術學院，廣東 東莞 523808）

考慮如下無約束優(yōu)化問題：

其中f連續(xù)可微。共軛梯度算法由于要求內(nèi)存小且收斂速度快，是求解大規(guī)模問題(0.1)的有效方法之一。共軛梯度算法滿足如下迭代形式：

并證明了當使用Armijo 型線搜索或廣義Wolfe 線搜索時，算法全局收斂。數(shù)值結果表明該方法是有效的。更多的下降性共軛梯度算法可以參考文獻[2-4,15,18]。

Yabe 和Takano[17]利用目標函數(shù)的二階信息和DL 共軛條件[6]，給出如下YT 方法：

稱為YT 型共軛條件。本文將基于施密特正交化方法以及YT 型共軛條件給出一類新的YT 型共軛梯度算法。新算法的一個重要特性是產(chǎn)生的方向總是滿足充分下降條件，且不依賴于任何線搜索。當使用精確線搜索時和合適的參數(shù)下，新算法退化為標準的HS 方法。在一定條件下，我們證明算法在標準Wolfe 線搜索條件下對于一致凸函數(shù)與一般函數(shù)具有全局收斂性。

1 新算法的動機

在本節(jié)，我們將給出新算法。注意(0.4)產(chǎn)生的充分下降性與共軛參數(shù)的選取無關，我們將其寫成如下形式：

利用(0.5)得到

聯(lián)立(1.1)與(1.2)得

由(1.3)計算得：

其中

其中

2 收斂性分析

本節(jié)將給出新算法在一致凸函數(shù)與一般函數(shù)下的全局收斂性證明。假定目標函數(shù)滿足下面假設。

假設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 一致凸函數(shù)下的收斂性分析

本小節(jié)我們將證明在目標函數(shù)一致凸假設下,新算法的全局收斂性。目標函數(shù)一致凸，即存在常數(shù)使得：

上式等價于:

由(2.12)和(2.13)可知：

定理2.1若假設1 成立，目標函數(shù)一致凸，滿足(2.9)，步長由標準Wolfe 準則(1.7)給出。如果，則對于一切，由(0.2)，(1.1)，(1.4)確定的新算法滿足。如果則當時，新算法滿足

證明：由(2.14)和可知：

此時:

此時

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

2.2 一般函數(shù)下的收斂性分析

本節(jié)將證明一般函數(shù)下新算法的全局收斂性。為保證新算法的全局收斂性以及進一步提升算法性能，將取做如下形式：

下面的引理指出，在一定條件下，算法的搜索方向將緩慢且漸進變化。

引理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)給出。當時，存在常數(shù)使得

且有

證明：情況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，執(zhí)行與[6]中定理2.6 相似的分析，我們可以證明以下全局收斂性定理。

定理2.2若假設1 成立，對于新算法(1.1)(0.2)(2.23)，若(2.9)成立，步長由標準Wolfe 準則(1.7)給出。

證明：我們使用反證法，即假設(2.24)成立，則引理2.2，引理2.4 也成立。令，任取兩個指標使得，從而有如下關系式：

3 數(shù)值結果

本節(jié)將給出新算法的數(shù)值結果。所有測試均在Windows10 操 作 系 統(tǒng)（ 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]中第五節(jié)(i)提出的新算法；（5）CGOPT[8]。

選取文獻[1]中的84 個函數(shù)進行測試，維數(shù)分別選 取 1000 與 10000 。 新 算 法 的 參 數(shù) 為經(jīng)典YT+算法與新算法中算法中，所有算法均使用標準Wolfe 準則確定步長，參數(shù)為

圖1 迭代次數(shù)(NI)對比 (1 000dim)

圖3 至圖6 分別展示了5 種算法在CPU 時間，迭代次數(shù)，函數(shù)估計次數(shù)與梯度估計次數(shù)的性能指標，測試問題維度選取為1 000 維+10 000 維。新算法略優(yōu)于CG_DESCENT 算法,與CGOPT 相近，且明顯優(yōu)于YT+算法與[14]中第五節(jié)提出的新算法，即圖中的KNY算法，這充分說明我們的新算法是非常有效的。具體來說，在168 個測試問題中，新算法與CG_DESCENT都解決了94.6%的問題，就迭代次數(shù)而言，有120 個問題新算法的迭代次數(shù)小于等于CG_DESCENT。總體上講，新算法為求解無約束優(yōu)化問題提供了一種新的有效方法。同時，注意到算法對參數(shù)的選取十分敏感，且在10 000 維度下，相較于CG_DESCENT 使用更多的CPU 時間，這可能是因為參數(shù)的影響而導致，因此，更多對新算法參數(shù)的合適選取仍有待研究。

圖3 CPU 使用時間對比(1 000+10 000dim)

圖4 迭代次數(shù)對比(1 000+10 000dim)

4 總結

本文基于施密特正交化與YT 型共軛條件，給出一類修正的YT 型共軛梯度算法。新算法的一個重要特性是產(chǎn)生的方向總是滿足充分下降條件，且不依賴于任何線搜索。當使用精確線搜索且在合適的參數(shù)下，新算法退化為標準的HS 方法。在一定條件下，我們證明算法在標準Wolfe 線搜索條件下對于一致凸函數(shù)與一般函數(shù)具有全局收斂性。數(shù)值結果表明新算法具有優(yōu)良的數(shù)值性能。