一種近似BFGS的自適應(yīng)雙參數(shù)共軛梯度法

李向利 ,莫元健 ,梅建平

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

1.引言

常見無約束優(yōu)化問題：

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

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

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

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

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

目前研究者們提出了一系列新的共軛梯度法,這些共軛梯度法的推廣研究主要集中在共軛參數(shù)和搜索方向的選取上.其中一些經(jīng)典的共軛參數(shù)β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].對應(yīng)的βk公式分別為

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

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

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

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

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

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

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

受以上文獻(xiàn)設(shè)計搜索方向參數(shù)思路的啟發(fā),為了更加有效的求解大規(guī)模無約束優(yōu)化問題,本文考慮讓搜索方向接近文[20-21]中無記憶BFGS方法的方向,并構(gòu)造一個新的自適應(yīng)雙參數(shù)共軛梯度法.

本文的其余部分框架如下.第2節(jié),設(shè)計一個有效的自適應(yīng)雙參數(shù)共軛梯度算法.第3節(jié),在一般假設(shè)條件下,給出算法在標(biāo)準(zhǔn)Wolfe線搜索下的全局收斂性證明.第4節(jié),對算法的數(shù)值實驗結(jié)果進(jìn)行分析.第5節(jié),對全文進(jìn)行總結(jié).

2.TTNEWCG算法

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

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

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

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

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

證結(jié)合(2.7)計算易得

下面對自適應(yīng)雙參數(shù)tk和mk的取值范圍進(jìn)行討論.

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

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

算法2(TTNEWCG)

3.收斂性分析

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

假設(shè)3.1

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

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

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

又由式(3.3)易得

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

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

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

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

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

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

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

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

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

根據(jù)wolfe準(zhǔn)則易得

再根據(jù)公式(1.4)可得

對式(3.11)進(jìn)行移項可得

結(jié)合式(3.12)和(3.13)有

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

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

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

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

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

4.數(shù)值實驗

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

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

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

表1 測試函數(shù)

表2 算法數(shù)值結(jié)果

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

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

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

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

圖1 算法迭代次數(shù)性能圖

圖2 目標(biāo)函數(shù)迭代次數(shù)性能圖

圖3 梯度函數(shù)迭代次數(shù)性能圖

圖4 CPU運行時間性能圖

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

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

5.結(jié)束語

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