程萬友, 葉劍豪, 張嘉昊
(東莞理工學院 計算機科學與技術學院,廣東 東莞 523808)
考慮如下無約束優化問題:
其中f連續可微。共軛梯度算法由于要求內存小且收斂速度快,是求解大規模問題(0.1)的有效方法之一。共軛梯度算法滿足如下迭代形式:
并證明了當使用Armijo 型線搜索或廣義Wolfe 線搜索時,算法全局收斂。數值結果表明該方法是有效的。更多的下降性共軛梯度算法可以參考文獻[2-4,15,18]。
Yabe 和Takano[17]利用目標函數的二階信息和DL 共軛條件[6],給出如下YT 方法:
稱為YT 型共軛條件。本文將基于施密特正交化方法以及YT 型共軛條件給出一類新的YT 型共軛梯度算法。新算法的一個重要特性是產生的方向總是滿足充分下降條件,且不依賴于任何線搜索。當使用精確線搜索時和合適的參數下,新算法退化為標準的HS 方法。在一定條件下,我們證明算法在標準Wolfe 線搜索條件下對于一致凸函數與一般函數具有全局收斂性。
在本節,我們將給出新算法。注意(0.4)產生的充分下降性與共軛參數的選取無關,我們將其寫成如下形式:
利用(0.5)得到
聯立(1.1)與(1.2)得
由(1.3)計算得:
其中
其中
本節將給出新算法在一致凸函數與一般函數下的全局收斂性證明。假定目標函數滿足下面假設。
假設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.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若假設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 也成立。令,任取兩個指標使得,從而有如下關系式:
本節將給出新算法的數值結果。所有測試均在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??傮w上講,新算法為求解無約束優化問題提供了一種新的有效方法。同時,注意到算法對參數的選取十分敏感,且在10 000 維度下,相較于CG_DESCENT 使用更多的CPU 時間,這可能是因為參數的影響而導致,因此,更多對新算法參數的合適選取仍有待研究。
圖3 CPU 使用時間對比(1 000+10 000dim)
圖4 迭代次數對比(1 000+10 000dim)
本文基于施密特正交化與YT 型共軛條件,給出一類修正的YT 型共軛梯度算法。新算法的一個重要特性是產生的方向總是滿足充分下降條件,且不依賴于任何線搜索。當使用精確線搜索且在合適的參數下,新算法退化為標準的HS 方法。在一定條件下,我們證明算法在標準Wolfe 線搜索條件下對于一致凸函數與一般函數具有全局收斂性。數值結果表明新算法具有優良的數值性能。