一個基于非單調(diào)技術(shù)的超記憶梯度法

林海嬋,李靖雅,歐宜貴

( 海南大學(xué)理學(xué)院,海南 海口570228)

1.引言

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

其中f:Rn→R是連續(xù)可微的函數(shù).求解問題(1.1)的方法通常采用迭代法[1],其具體的迭代形式如下：

這里αk和dk分別是第k步迭代時的步長因子和搜索方向.為了方便起見,在迭代點xk處,本文用fk表示函數(shù)值f(xk),用表示gk梯度?f(xk),用||·||表示Rn上的2-范數(shù).

共軛梯度法是介于最速下降法和牛頓法之間的一種無約束優(yōu)化方法.由于共軛梯度法不需要矩陣存儲,結(jié)構(gòu)簡單,容易編程實現(xiàn),且具有較快的收斂速度和二次終止性等優(yōu)點,因此,對該方法的研究已受到人們的廣泛重視,目前已成為解決大規(guī)模無約束優(yōu)化問題的有效方法[2?3].記憶梯度方法和超記憶梯度是共軛梯度法的推廣[4?5],因此它們也具備共軛梯度法的上述特點.然而,與共軛梯度法相比,這類方法有一個顯著的特點,即記憶梯度法和超記憶梯度法在每一次迭代過程中都能夠充分利用之前多步的迭代信息去構(gòu)造新的迭代點,這一特點有助于我們設(shè)計出更高效的新算法[6?9].

迄今為止,求解無約束優(yōu)化問題的共軛梯度法和記憶梯度法絕大多數(shù)是采用單調(diào)線搜索技術(shù)來求步長因子.然而,對那些目標(biāo)函數(shù)出現(xiàn)窄長的彎曲“峽谷”形狀時,若此時仍強(qiáng)制要求目標(biāo)函數(shù)在每一步迭代時都嚴(yán)格單調(diào)下降,則通常會減緩算法的收斂速率[10],因此,非單調(diào)策略應(yīng)運而生.

最早的非單調(diào)線搜索技術(shù)是由Grippo等人提出的,它要求步長因子滿足如下條件:

其中σ ∈(0,1),m(0)=0,0≤m(k)≤min {m(k?1)+1,M},而M是事先給定的非負(fù)整數(shù).大量的數(shù)值實驗表明:非單調(diào)線搜索技術(shù)(1.3)及其變形不但可以提高找到全局最優(yōu)點的可能性,而且可以改善算法的計算效率.隨后,研究人員又將該非單調(diào)技術(shù)及其變形分別與共軛梯度法、記憶梯度法以及其它的優(yōu)化方法結(jié)合起來求解無約束優(yōu)化問題[11?14].盡管基于條件(1.3)的非單調(diào)技術(shù)已經(jīng)得到廣泛應(yīng)用,但該技術(shù)仍然存在著缺陷[15].為克服這一缺點,ZHANG和Hager[15]提出了一個新非單調(diào)線搜索技術(shù),它用函數(shù)的平均值去替換(1.3)式中函數(shù)的最大值隨后,GU和MO[16]又提出了如下的非單調(diào)策略(記為GM-LS):

其中

這里0≤θk ≤θmax<1及σ ∈(0,1).文[16]中的數(shù)值試驗結(jié)果表明:這一改進(jìn)的非單調(diào)策略實用且有效.

根據(jù)上述討論，并受上述文[6,12-13,16]的思想啟發(fā),我們在本文給出了一個新的非單調(diào)線搜索策略,并以此為基礎(chǔ)提出了一個解決無約束優(yōu)化問題(1.1)的超記憶梯度方法.該方法的主要特點是:它在每一次迭代中總是提供一個充分下降步.這一特性不依賴于目標(biāo)函數(shù)的凸性及其方法所采用的線搜索策略.在較弱的假設(shè)條件之下,該方法具有全局收斂性和局部R線性收斂性.數(shù)值實驗也表明了其有效性.

2.算法描述

本節(jié),我們將給出一個求解問題(1.1)的超記憶梯度算法.為此,我們先定義如下搜索方向:

其中,m是記憶先前的迭代步數(shù),βki(i=1,2,··· ,m)由下式定義:

其中,t ≥1是一常數(shù),rk是一個尺度參數(shù),它的選取按下列方式定義[17]:

顯然,尺度參數(shù)rk滿足下式:

為了定義我們的算法,我們引進(jìn)如下的非單調(diào)線搜索策略.

修正的非單調(diào)線搜索:給定σ ∈(0,1),β ∈(0,1),以及嚴(yán)格單調(diào)遞減的非負(fù)序列 {εk}.令并從 {τk,τkβ,τkβ2,···} 中選取αk使其為滿足下列不等式的最大α：

這里0≤θk ≤θmax<1,L為大于0的Lipschitz常數(shù)(詳情參見后文假設(shè)(A2)).

注1顯然,當(dāng)εk ≡0時,(2.5)式就變?yōu)槲腫16]中的非單調(diào)策略GM-LS;當(dāng)εk ≡0且θk ≡0時,(2.5)式就變?yōu)榻?jīng)典的Armijo線搜索策略[1].因此,本文提出的非單調(diào)線搜索(2.5)可以看做是經(jīng)典的Armijo 線搜索策略和線性搜索策略GM-LS[16]的推廣.同時,由于fk ≤Dk,?k(參看文[16]引理3.1),故有

從而本文提出的線搜索策略(2.5)更易滿足而使得我們可能找到較大的步長因子αk,從而減少了目標(biāo)函數(shù)和梯度函數(shù)的調(diào)用次數(shù),降低了計算量.下面我們給出本文具體的算法.

算法I

步0 賦初值x0,ε ≥0,D0=f(x0),εk ≥0,r0=1,t ≥1及m ≥0,令k:=0;

步1 計算gk,若||gk||≤ε,停止迭代;

步2 構(gòu)造滿足(2.1)式的搜索方向dk;

步3 由修正的非單調(diào)線搜索策略(2.5)計算αk,并令xk+1=xk+αkdk;

步4 令k=k+1,轉(zhuǎn)步1.

注2由文[19]中的引理3.3的結(jié)論可知:步3中的非單調(diào)線搜索策略(2.5)是適定的,從而算法I是適定的.此外,在算法I中,若選擇不同的尺度參數(shù)rk,我們就可得到不同的超記憶梯度法.

注3在非單調(diào)線搜索(2.5)中,由于Lipschitz常數(shù)L事先未知,故在每一次迭代時需要找到一個Lk去估計它.最近,研究人員已經(jīng)提出一些估計Lipschitz常數(shù)L的好方法(見文[18]),在本文的數(shù)值試驗中,我們使用去估計它,其中L0>0是事先給定的一個較小的正常數(shù).

引理1若dk是由(2.1)-(2.3)定義,則存在正常數(shù)c1和c2,使得對所有的k,有

和

證該引理的證明類似于文[12]中的引理1和引理2的證明方法.為保持其完整性，我們?nèi)越o出其證明。若k=0,則由定義(2.1)可知,不等式(2.7)和(2.8)成立.

若0

和

由引理1的結(jié)論(2.7)和(2.8),我們即可推出下列結(jié)論.

引理2若dk是由(2.1)-(2.3)定義,則存在一個正常數(shù)c,使得下式成立:

3.算法的收斂性分析

本節(jié)我們將分析算法I的收斂性,為此,我們需要如下假設(shè):

(A1)函數(shù)f在包含水平集的鄰域?內(nèi)下有界;

(A2)梯度函數(shù)g(x)在?內(nèi)是Lipschitz連續(xù)的,即存在Lipschitz常數(shù)L>0,使得

引理3算法I產(chǎn)生的序列 {xk}滿足

證由(2.6)式可推出:

我們可用歸納法來證明結(jié)論(3.1).當(dāng)k=0時,結(jié)論(3.1)顯然成立.假設(shè)(3.1)式對于k ≥1成立,則由(3.2)式可知,若能驗證下列不等式:

則可得到fk+1≤Dk+1,這表明(3.1)式對于k+1也成立,從而原命題成立.

下面我們將驗證(3.3)式的正確性.為此,我們只需驗證:存在>0,當(dāng)α ∈(0,)時,必有

事實上,由歸納法的假設(shè)及(2.7)式,我們可推得:

從引理3的證明過程,我們可以推出下列結(jié)論.

引理4非單調(diào)線搜索準(zhǔn)則(2.5)是適定的,即它在有限步內(nèi)必能找到一個αk,使得該αk滿足(2.5)式.

引理5設(shè) {xk}和 {Dk}是由算法I產(chǎn)生的序列,則

且對?k,有xk ∈L0.

證詳見文[19]中引理3.4的證明.證畢.

引理6若假設(shè)(A1)和(A2)成立,則存在一個常數(shù)η >0,使得

證定義下列兩個集合:

為了證明該結(jié)論,我們考慮下列兩種情形:

情形I 若k ∈K1,則由線搜索(2.5),(2.9)式及我們有

情形II 若k ∈K2,由αk <τk,我們可得令則由線搜索策略(2.5)選取αk的方式可知:不滿足(2.5)式,即

利用(3.1)式,我們即可得到

利用微分中值定理,則由(3.8)式我們可推得,存在λk ∈[0,1),使得

即

于是,根據(jù)假設(shè)(A2)、Cauchy-Schwarz不等式及(3.9)式,我們可推出:

進(jìn)而有

再由線搜索策略(2.5)、(2.9)及(3.11)式，即可得到

因此,若令η=我們即可由(3.7)和(3.12)式推得不等式(3.6)式成立,證畢.

定理1設(shè) {xk}是由算法I產(chǎn)生的序列.若假設(shè)(A1)和(A2)成立,則若非gk=0,必有

證只需證明當(dāng)gk≠0時,必有(3.13)式成立.用反證法,若結(jié)論(3.13)式不成立,則存在一個常數(shù)δ >0,使得

由(2.6)及(3.6)式，我們有

即

注意到fk ≤Dk,?k,從而由假設(shè)(A1)可知Dk下有界,再結(jié)合及(3.15)式，我們即可推出

顯然,上式與(3.14)式矛盾.因此,結(jié)論(3.13)成立,證畢.

為分析本文算法I的收斂速度,我們需做如下進(jìn)一步的假設(shè).

(A3)函數(shù)f:Rn→R是一個連續(xù)可微的強(qiáng)凸函數(shù),即存在一個常數(shù)ω >0,使得

引理7[15]若假設(shè)(A3)滿足,則f存在唯一最小點x?,而且下列結(jié)論均成立

定理2若假設(shè)(A1)、(A2)和(A3)都成立,則由算法I產(chǎn)生的無限序列 {xk}收斂于f的唯一最小點x?.更進(jìn)一步,若εk=o(||gk||2),則該序列 {xk}至少R-線性收斂于x?.

證該定理的證明思路源于文[15]中的定理3.1的證法.由定理1及(3.19)式,我們可以直接得到xk→x?,及g(x?)=0.下證此定理的第二部分.由(2.7)式及Cauchy-Schwarz不等式,我們有

即

注意到αk ≤τk,?k,從而結(jié)合(3.21)式和Cauchy-Schwarz不等式,有

利用(3.22)式,再結(jié)合(2.8)式,我們可推出

因此,由假設(shè)(A2)及(3.23)式可推出:存在常數(shù)b=使得

利用上面的討論,我們可以驗證下列結(jié)論:存在正整數(shù)k0和θ ∈(0,1)使得

這表明算法I所產(chǎn)生的序列 {xk}至少是R-線性收斂于x?的.

現(xiàn)證明不等式(3.25)的正確性,分以下兩種情形考慮.

情形I當(dāng)||gk||2≥b1(Dk?f(x?))時,由(2.6)及(3.6)式,我們有

又因為εk=o(||gk||2),故存在正整數(shù)k0,當(dāng)k ≥k0時,

結(jié)合(3.26)及(3.27)式,我們可得到

此不等式意味著(3.25)式在情形I下成立.

情形II當(dāng)||gk||2

結(jié)合(2.6),(3.27)及(3.28)式,并利用ωb2b1=1?ηb1,我們可推出

上式表明不等式(3.25)在情形II也成立,證畢.

4.數(shù)值實驗

本節(jié),我們將給出算法I的數(shù)值結(jié)果.為此,我們選取了文[20]中專門用于測試無約束優(yōu)化問題的10個大規(guī)模問題作為測試函數(shù),它們分別是文[20]中第14、21、22、23、24、26、27、30、31、32 個函數(shù).數(shù)值實驗過程中所用參數(shù)分別選為:σ=0.1,β=0.38,θ0=0.1,L0=10?5,r0=1,m=5,t=1,rmin=10?15,rmax=1015,εk=此外,參數(shù)θk是按下列遞歸式來動態(tài)地選取:

為檢驗算法I的有效性,我們還將它與帶非單調(diào)線搜索的記憶梯度法-Yasushi算法[13]和Ou等人的算法[12]進(jìn)行了比較.對Yasushi算法,其相關(guān)參數(shù)選為:m=5,σ=0.1,r0=1=9,σk ≡0.5,v=?0.8,β=0.38; 對算法Ou,其相關(guān)參數(shù)選為:m=5,σ=0.01,β=0.5,r=0.9,ρ=0.001,L0=10?5,η0=0.5.同時對于算法Ou中參數(shù)Ck,由下式定義[15]:

其中 {

所有測試函數(shù)的初始點見文[18],而3個算法的終止條件均選為||gk||≤10?5.算法程序都在Matlab7.0環(huán)境下運行.詳細(xì)的測試結(jié)果見表1,其中,”Function”表示測試函數(shù),”n”表示測試函數(shù)的維數(shù).測試結(jié)果是以”k/kf/cpu” 順序呈現(xiàn),其中:k代表迭代次數(shù);kf代表函數(shù)的調(diào)用次數(shù); cpu代表CPU運行時間.同時規(guī)定:若算法對測試函數(shù)的迭代次數(shù)超過10000,或者算法的CPU運行時間超過300秒還未停止,我們就認(rèn)為該算法運行失敗,簡記為”F”.

表1 三算法數(shù)值實驗結(jié)果

為更清晰的反映上表的實驗結(jié)果,我們參閱文[21]提出的有關(guān)性能線的定義,分別為表1中的k、kf及cpu三種數(shù)據(jù)做出性能線描述圖,詳情見圖1、圖2、圖3.

圖1 三算法的k性能線描述圖

圖2 三算法的kf性能線描述圖

圖3 三算法的cpu性能線描述圖

從以上性能線描述圖1、2和3,我們可觀察到事實:1)對于迭代次數(shù)而言,算法I的執(zhí)行效率略優(yōu)于算法Yasushi,但它們都好于算法Ou; 2)對于函數(shù)值的調(diào)用次數(shù),算法Yasushi和算法Ou執(zhí)行效率大致相當(dāng),但它們稍劣于算法I; 3)對于運行時間,算法I的執(zhí)行效率要優(yōu)于其它2個算法.因此,綜合以上三方面的事實,我們認(rèn)為:算法I是可以同其它兩個算法相媲美.

當(dāng)然,我們還不能從上述有限的數(shù)值測試結(jié)果得出一般性的結(jié)論.對基于非單調(diào)技術(shù)的優(yōu)化方法的研究,尤其是對大規(guī)模問題的超記憶梯度方法的深入探討將是我們今后的任務(wù).