李向利 ,莫元健 ,梅建平

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

1.引言

常見無(wú)約束優(yōu)化問(wèn)題：

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

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

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

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

其中ρ和σ滿足關(guān)系0<ρ≤σ<1.搜索方向dk可根據(jù)以下公式計(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].對(duì)應(yīng)的βk公式分別為

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

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

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

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

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

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

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

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

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

2.TTNEWCG算法

求解問(wèn)題(1.1) 的三項(xiàng)共軛梯度方法一般計(jì)算搜索方向如下:

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

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

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

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

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

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

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

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

算法2(TTNEWCG)

3.收斂性分析

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

假設(shè)3.1

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

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

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

又由式(3.3)易得

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

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

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

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

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

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

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

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

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

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

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

對(duì)式(3.11)進(jìn)行移項(xiàng)可得

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

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

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

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

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

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

4.數(shù)值實(shí)驗(yàn)

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

對(duì)比的測(cè)試算法和新算法的搜索方向具有相似結(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維度條件下五個(gè)對(duì)比算法的數(shù)值結(jié)果,N代表函數(shù)名稱,dim代表維度,Iter,Fno,Gno,Time分別代表算法迭代次數(shù),目標(biāo)函數(shù)迭代次數(shù),目標(biāo)梯度迭代次數(shù)和CPU運(yùn)行時(shí)間.表格中的“NAN”代表該方法存在數(shù)值溢出或者未能達(dá)到算法的收斂條件.表1為測(cè)試函數(shù)的序號(hào)及名稱.

表1 測(cè)試函數(shù)

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

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

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

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

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

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

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

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

圖4 CPU運(yùn)行時(shí)間性能圖

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

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

5.結(jié)束語(yǔ)

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