一種近似BFGS的自適應雙參數共軛梯度法

李向利 ,莫元健 ,梅建平

(1.桂林電子科技大學數學與計算科學學院,廣西 桂林 541004;2.廣西高校數據分析與計算重點實驗室,廣西 桂林 541004;3.廣西應用數學中心,廣西 桂林 541004)

1.引言

常見無約束優化問題：

其中x ∈Rn表示可行域,f(x)為可行域內的連續可微函數,g(x)為f(x)的梯度其計算表達式為g(x)=?f(x).

最早求解問題(1.1)的方法有牛頓法,擬牛頓法等.但是這些方法并不適用在大規模問題上,因為它們需要計算和存儲Hessian矩陣或其近似值,這使得計算成本非常昂貴.共軛梯度法因其低存儲、易計算和具有良好收斂性等特點進而被廣泛應用在求解大規模無約束優化問題當中.

針對問題(1.1),共軛梯度法的近似解序列{xk}迭代格式如下:

其中αk、dk分別表示步長和搜索方向.步長αk通常由Wolfe[1]線搜索可得

其中ρ和σ滿足關系0<ρ≤σ<1.搜索方向dk可根據以下公式計算:

目前研究者們提出了一系列新的共軛梯度法,這些共軛梯度法的推廣研究主要集中在共軛參數和搜索方向的選取上.其中一些經典的共軛參數βk如下: Fetcher-Reeves(FR)[2],Polak-Ribière-Polyak(PRP)[3-4],Hestenes-Stiefel(HS)[5],共軛下降(CD)[6],Liu-Storey(LS)[7],和Dai-Yuan(DY)[8].對應的βk公式分別為

其中∥.∥表示歐幾里得范數,yk=gk+1-gk.

擬牛頓法[9]也常用于求解大規模無約束優化問題.由Broyden[10]、Fletcher[11]、Goldfard[12]、Shanno[13]四位學者提出的BFGS方法是最有效的擬牛頓方法之一.為了更有效的求解大規模無約束優化問題,進一步減少計算和儲存空間成本,將共軛梯度法和擬牛頓法相結合的研究已成熱門趨勢,眾多學者對這兩種方法的優化和改進仍在繼續.

在共軛梯度法中,標準的共軛條件可以讓其獲得良好的數值結果和收斂性,但標準的共軛條件在非精確線搜索中不能保證充分下降性,為了解決這一缺陷,DAI和LIAO[14]把擬牛頓法的思想用到共軛梯度法中,則有DAI-LIAO共軛條件:

其中τ是DAI-LIAO參數,此時共軛梯度參數迭代更新公式為

其中τ≥0,當τ=0時,上式退化為許多學者對(1.7)中的參數τ進行研究,學者Hager和ZHANG[15]基于HS法提出著名的CGDESCENT共軛梯度法,其搜索方向滿足充分下降性和共軛條件,CGDESCENT法可看作DL共軛梯度法的一種特殊形式,搜索方向為

DAI和KOU[16]結合最佳逼近思想,使得共軛梯度法的搜索方向逼近Perry和Shanno[17]的自適應無記憶BFGS方法的搜索方向,提出一類新的共軛梯度法.LI[18]受文[16]的啟發提出一個三項PRP 共軛梯度方法,其搜索方向接近無記憶BFGS擬牛頓方法的方向,在強Wolfe條件下,搜索方向滿足充分下降性,搜索方向為

Jitsupa[19]受文[18]的啟發提出了一種新的混合共軛梯度算法來求解問題(1.1).該混合共軛梯度算法的方向是由共軛參數CD和DY組合而成并且接近無記憶BFGS擬牛頓算法的方向.在Wolfe條件和其他適當的假設下,該算法的充分下降性和全局收斂得到證明,其搜索方向為

受以上文獻設計搜索方向參數思路的啟發,為了更加有效的求解大規模無約束優化問題,本文考慮讓搜索方向接近文[20-21]中無記憶BFGS方法的方向,并構造一個新的自適應雙參數共軛梯度法.

本文的其余部分框架如下.第2節,設計一個有效的自適應雙參數共軛梯度算法.第3節,在一般假設條件下,給出算法在標準Wolfe線搜索下的全局收斂性證明.第4節,對算法的數值實驗結果進行分析.第5節,對全文進行總結.

2.TTNEWCG算法

求解問題(1.1) 的三項共軛梯度方法一般計算搜索方向如下:

其中βk-1和rk為參數,參數的選取不同所對應的共軛梯度算法也不同.當(2.1)中的rk=0 時,此時的三項共軛梯度法變為經典共軛梯度法.文[20-21]提出的無記憶BFGS方法的該搜索方向如下:

其中,I是單位矩陣.公式(2.2)中搜索方向可以寫成如下形式:

公式(2.4)中設計的自適應參數tk通過搜索方向接近無記憶BFGS搜索方向獲得,再通過單變量最小化問題計算tk表達式如下:

搜索方向下降性對收斂性分析有著重要作用,為保證算法生成的搜索方向滿足充分下降性,因此,本文通過定理2.1說明公式(2.7)的搜索方向滿足充分下降性.

證結合(2.7)計算易得

下面對自適應雙參數tk和mk的取值范圍進行討論.

為提高算法效率來得到更好的數值結果,本文采用加速算法來替代公式(1.2)的最小點,并記為

本文提出一種有效的自適應雙參數三項共軛梯度算法,該方法能更有效的求解大規模無約束優化問題,新算法的具體步驟如下:

算法2(TTNEWCG)

3.收斂性分析

在本節,我們證明TTNEWCG算法的全局收斂性.證明過程需做出如下合理假設:

假設3.1

1) 水平集?={x ∈Rn|f(x)≤f(x0)}是有界的;

2) 在?的某個鄰域N內,函數的梯度f(x)在水平集?上滿足Lipschitz連續,即存在一個常數L>0,使得

上面假設1)2)可等價于存在非負常數γ1和B滿足

又由式(3.3)易得

除了上述假設外,為了更好的證明TTNEWCG算法的理論性質,下面給出引理3.1來說明新設計的搜索方向滿足充分下降性.

引理3.1若搜索方向dk+1由算法TTNEWCG生成,則搜索方向dk+1具有充分下降性,即存在一個常數c>0使得

根據公式(2.7)-(2.10)可知該搜索方向滿足充分下降性.因此,TTNEWCG方法定義良好.

Zoutendijk條件[23]對證明共軛梯度法的全局收斂性起重要作用,在標準的wolfe線搜索條件下,Zoutendijk條件由下面引理3.2給出.

引理3.2[23]若假設3.1成立,近似序列解{xk}由TTNEWCG算法生成,且搜索方向{dk}滿足充分下降性,步長αk通過wolfe線搜索得到,那么有

下面利用引理3.1-3.2對新算法TTNEWCG進行全局收斂性證明.

定理3.1若假設3.1成立,搜索方向{dk}是由TTNEWCG 算法生成,步長αk通過wolfe 線搜索得到,那么有

證利用反證法,若公式(3.7)不成立,則存在一個常數μ>0有

根據公式(3.1)和(3.4)易知

根據wolfe準則易得

再根據公式(1.4)可得

對式(3.11)進行移項可得

結合式(3.12)和(3.13)有

再根據引理3.1和引理3.2及公式(3.8)可以得到

又由假設3.1和公式(2.7)易得

式(3.16)通過三角不等式可得

將式公式(3.2),(3.4),(3.14)代入式(3.17)可得

由引理3.2知這與式(3.15)矛盾,所以式(3.8)不成立,故得證.

4.數值實驗

在本節,將展示利用TTNEWCG算法計算測試問題的數值結果來驗證新算法的有效性,在操作系統Win10,PC(CPU 2.40GHz 16.0GB)環境下,利用MatlabR2020a編譯代碼進行實驗.從文[24]中挑選46個測試函數來解決138個測試問題.

對比的測試算法和新算法的搜索方向具有相似結構,本文用TTNEWCG方法和文[19]中的TTCDDY方法、文[8]中的DY方法、文[15]中的CGDESCENT方法、文[18]中的TPRP方法進行比較,所有算法都在標準Wolfe非精確線搜索下進行,參數設置為:ρ=0.001,σ=0.8,t=1,λ=2.01.算法的終止準則為: Iter>2000或∥gk∥≤10-5(1+|fk|).

表2顯示在1000,5000,10000維度條件下五個對比算法的數值結果,N代表函數名稱,dim代表維度,Iter,Fno,Gno,Time分別代表算法迭代次數,目標函數迭代次數,目標梯度迭代次數和CPU運行時間.表格中的“NAN”代表該方法存在數值溢出或者未能達到算法的收斂條件.表1為測試函數的序號及名稱.

表1 測試函數

表2 算法數值結果

通過表2中138個測試問題的結果可知,算法TTNEWCG能夠全部求解所有測試問題,由此可知算法TTNEWCG是有效的.

除了通過表格驗證新算法的有效性和可行性外,本文將采用Dolan和Mor′e[25]性能圖來更加直觀的對比分析四個算法數值效果.下面是性能圖原理的簡單介紹.在實驗環境相同情況下,四種算法求解同一個測試問題,這里有P代表由單個測試問題p組成的問題集合,S表示由單個算法s組成的集合.tp,s表示使用算法s求解測試問題p的耗費時間,性能比rp,s的數值越小表明算法s對于問題p的求解性能越好.rp,s計算表達式為:

ρs(τ)定義為性能分布函數,ρs(τ)的曲線越高,其對應方法的數值性能就越好計算,它的計算公式如下:

圖1-4展示對比算法多維度解決138個測試問題的數值性能,其中最大維度達到10000.類似表2性能圖中的Iter,Fno,Gno,Time分別代表算法迭代次數,目標函數迭代次數,目標梯度迭代次數和CPU運行時間.

圖1 算法迭代次數性能圖

圖2 目標函數迭代次數性能圖

圖3 梯度函數迭代次數性能圖

圖4 CPU運行時間性能圖

從性能圖的特征可以知道,曲線越高,相應的方法越好.通過對比圖1-4可知TTNEWCG算法在迭代次數、目標函數迭代次數、梯度函數迭代次數、CPU運行時間上的性能效果優于對比算法TTCDDY[19]、CGDESCENT[15]、TPRP[18]、DY[8].

對以上實驗結果進行分析,TTNEWCG的良好效果主要取決于共軛參數的選擇和搜索方向的改進.大多數方法中的共軛參數都是定值,而TTNEWCG新算法中的共軛參數是自適應的,計算參數上相比其他算法減少了計算量和存儲,并且搜索方向接近BFGS方向,因此,TTNEWCG相比其他方法是有優勢的.

5.結束語

為了更加有效的求解大規模無約束優化問題,本文基于自調比無記憶BFGS擬牛頓法,提出一個關于共軛參數DY的自適應雙參數共軛梯度法,設計的搜索方向滿足充分下降性,在一般假設和標準Wolfe線搜索準則下具有充分下降性和全局收斂性,數值實驗結果證明新算法是有效可行的.