求解無約束優(yōu)化問題的Aitken加速算法

謝亞君 ,姚 潔 ,馬昌鳳

(1.福州外語外貿(mào)學(xué)院理工學(xué)院,福建福州 350202;2.福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院,福建福州 350007)

§1 引言

基于Neculai[1]的工作,本文提出一種求解如下無約束優(yōu)化問題

的Aitken加速方法,其中f ∈Rn→R為連續(xù)可微的函數(shù).

至今為止,無約束優(yōu)化問題的求解已獲得廣泛關(guān)注,并取得豐碩的研究成果(見[2-6]),其中,包括共軛梯度法(見[7]),牛頓法與擬牛頓法等(見[8-12]).雖然牛頓法具有二階收斂速度的優(yōu)勢,但是需要計(jì)算二階導(dǎo)數(shù).因此在求解大規(guī)模問題時(shí),該方法往往因?yàn)橛?jì)算代價(jià)過高而變得不再適用.同時(shí)當(dāng)Hessian陣非正定時(shí),無法保證所產(chǎn)生的方向是目標(biāo)函數(shù)的下降方向.尤其是當(dāng)Hessian陣奇異時(shí),算法無法繼續(xù)循環(huán)迭代.修正牛頓法可在一定程度上克服此缺陷,然而修正參數(shù)的選取較難把握,對收斂速度亦有較大影響.眾所周知,擬牛頓法可以避免這些缺點(diǎn),在迭代過程中不需要計(jì)算目標(biāo)函數(shù)的Hessian陣,卻在某種意義下具有Hessian陣的作用,因此該方法在相關(guān)領(lǐng)域得到廣泛的應(yīng)用.例如,均衡問題,神經(jīng)網(wǎng)絡(luò),激光檢測,非線性方程組等(見[13-16]).

假設(shè)x0為某個(gè)初值點(diǎn).求解問題(1)的迭代格式有如下表達(dá)式

其中αk是由某種線搜索,例如Wolfe或Armijo線搜索獲得的步長,dk表示搜索方向.通常對問題(1)的迭代求解格式有兩個(gè)主要切入點(diǎn),一個(gè)是針對步長因子αk進(jìn)行合理設(shè)計(jì),另一個(gè)是考慮有效地選取較優(yōu)的搜索方向dk.詳細(xì)可參看文獻(xiàn)[17-20].

牛頓法是通過求解如下方程得到牛頓搜索方向dk,

其中Gk,gk分別表示函數(shù)f在點(diǎn)xk處的Hessian矩陣和梯度值.鑒于Hessian陣Gk高昂的計(jì)算代價(jià),可尋求一個(gè)矩陣Bk+1作為Hessian陣Gk+1的一種近似替代.將函數(shù)f在點(diǎn)xk+1處利用二次Taylor展開得到近似方程

進(jìn)而構(gòu)造所謂的割線方程

其中sk=xk+1?xk,yk=gk+1?gk,Bk+1=Bk+Δk,Δk可視為誤差校正矩陣.利用割線方程推導(dǎo)近似Hessian陣Bk+1,關(guān)于矩陣Bk+1的有效選取方面已有一系列較好的研究成果.例如,秩1校正公式或BFGS 算法等(見[21-23]).

在文獻(xiàn)[1]中,Neculai證明了一個(gè)簡單而有效的對角擬牛頓更新公式來求解

針對問題(6),基于對角擬牛頓更新迭代法(DNRTR)(見[1]),提出一個(gè)修正的Aitken加速迭代格式來求解無約束優(yōu)化問題(1),該方法在與前者對比的過程中顯示了非常良好且具有明顯優(yōu)勢的收斂性能.

本文剩余部分組織如下:§2提出求解無約束優(yōu)化問題(1)的修正Aitken加速迭代方法,同時(shí)證明了其具有良好的高階收斂性能.數(shù)值實(shí)驗(yàn)和結(jié)論分別安排在§3和§4.

§2 算法及收斂性

本節(jié)考慮改善對角擬牛頓更新方法(DNRTR)(見[1]),進(jìn)而引入一個(gè)修正Aitken加速迭代格式來求解優(yōu)化問題(1).最后提供重要的理論證明和收斂性結(jié)果.首先注意到問題(6)亦可轉(zhuǎn)化為如下形式

問題(7)的Lagrangian函數(shù)為

其中λ表示其Lagrangian乘子.由最優(yōu)性條件可得

將(10)式代入(7)式,即可得Lagrangian乘子

算法1(基于擬牛頓更新的Aitken加速算法(AADQN))

步1 給定初始點(diǎn)x0∈Rn,參數(shù)0<β <1,0<σ <0.5,m=0及充分小的正數(shù)ε1,ε2>0.計(jì)算向量g0=?f(x0).令d0=?g0,k=0.

步2 若‖g(xk)‖2<ε1停算;否則,轉(zhuǎn)到步3.

步3 計(jì)算滿足線搜索的步長αk,若不等式

成立,令mk=m,αk=βmk;否則,m:=m+1,然后循環(huán)(14).再計(jì)算

步4 利用公式(12)更新對角矩陣Bk+1.

步5 令

其中i=1,···,n,.置xk=.

步6 更新搜索方向

步7 置k:=k+1,返回步2.

注記1顯然經(jīng)過計(jì)算可知(19)所確定的搜索方向是下降的,即g(xk+1)Tdk+1<0.事實(shí)上有

由上式可得,若‖g(xk+1)‖≠0,則有g(shù)(xk+1)Tdk+1<0.

當(dāng)k→∞,若xk→x?且‖g?‖→0,則由算法步5定義的格式x=φ(x)即為不動(dòng)點(diǎn)迭代.關(guān)于‖g?‖→0的事實(shí)將在后面收斂性分析給出詳細(xì)證明.

下面先給出算法的適定性證明.

引理1序列{Δk},{Bk}由更新格式(12)產(chǎn)生.此外,若‖sk‖≠0,且存在(i=1,2,···,n),其中為對角矩陣B0的第i個(gè)對角元素,則對所有的正整數(shù)k,序列{Δk},{Bk}有界.

證當(dāng)k=0,y0=?2f(?0)s0,其中x0

注意到‖s0‖2≤n()2且由已知條件

即B1也是有界的.從而由歸納法可得引理結(jié)論.

文獻(xiàn)[24]中給出了所謂界退化性質(zhì)

其中Bk+1是前一步迭代矩陣Bk的更新,νk=max{‖xk+1?x?‖,‖xk ?x?‖},κ為某個(gè)常數(shù).該文描述了Hessian矩陣與其近似矩陣Bk+1可由前一步迭代中二者的差值來控制的事實(shí),既滿足界退化性質(zhì),同時(shí)也給出了滿足此性質(zhì)的算法至少具有q-線性收斂的結(jié)果(詳見[24]).下面證明更新公式(12)滿足界退化性質(zhì).

引理2若‖sk‖≠0,則更新公式(12)滿足界退化性質(zhì).

證由更新公式(12)可得

由于‖sk‖≠0,因此必存在ρ>0,使得‖sk‖>ρ,同時(shí)有且

其中?sk為向量sk的最大值分量.注意到

綜合以上引理1-2 可得下面結(jié)論.

定理1若存在兩個(gè)正的常數(shù)ε與δ滿足不等式‖x0?x?‖ <ε及‖B0??2f(x?)‖F(xiàn) <δ.那么由更新格式(12)產(chǎn)生的序列{xk}為適定的.

定理2設(shè){xk}是由算法1產(chǎn)生的序列,f(x)有下界且對任意的x0∈Rn,?f(x)在水平集

上存在且一致連續(xù).則

(a) 下降方向dk滿足與?gk的夾角θk的余弦值大于某個(gè)常數(shù)λ ∈(0,1);

(b){xk}的任意聚點(diǎn)x?都滿足?f(x?)=0.

證(a) 由(19)式中步長dk的選取可知,若‖gk‖≠0,當(dāng)(Bk)ii ≥ε2>0(i=1,2,···),則

否則當(dāng)(Bk)ii ≤0,由算法可知取步長dk=?gk,從而cosθk=1. 綜上可知cosθk >λ >0,其中λ ∈(0,1).

(b) 用反證法,設(shè)x?是{xk}的聚點(diǎn)且?f(x?)≠0.由條件可知f(xk)→f(x?)且f(xk)?f(xk+1)→0.又由(14)式可得

其中sk=βmkdk.若gk?0,則由(30)式可知,‖sk‖→0.又由(14)可得,對于,不等式

由于‖pk‖=1,因此{(lán)pk}有界,從而存在收斂子列.不失一般性,仍記為{pk}→p?(‖p?‖=1). 將(33)兩邊取極限得

對上式求極限可得

即?f(x?)Tp?<0,與(35)矛盾.因此有?f(x?)=0.

下面的定理將說明:在算法1中的步5,借助(20)式中的Aitken迭代格式,將對算法DNRTR[1]執(zhí)行了有益的改善和加速.

定理3假設(shè)算法1(即AADQN)滿足引理1-2以及定理2的條件,則由算法產(chǎn)生的序列{xk}收斂于優(yōu)化問題(1)的解x?且收斂階高于算法DNRTR.

證顯然由引理1-2以及定理2可知算法1產(chǎn)生的序列{xk}收斂于優(yōu)化問題(1)的解x?.由文獻(xiàn)[1]可知算法DNRTR至少為q-線性收斂的.下面證明算法AADQN所產(chǎn)生的序列{xk}收斂階高于算法DNRTR.

由算法AADQN可知

進(jìn)一步,由極限的性質(zhì)可得

為了方便,記算法AADQN 步5 中的k=.由(38)以及(17)則有

§3 數(shù)值實(shí)驗(yàn)

本節(jié)給出一些數(shù)值例子來驗(yàn)證§2提出的算法1(AADQN)在求解無約束優(yōu)化問題(1)時(shí)的高效性.通過與文獻(xiàn)[1]中的算法DNRTR 在更方面性能指標(biāo)進(jìn)行詳細(xì)對比.這些指標(biāo)包括迭代次數(shù)(記為“IT”),消耗的CPU時(shí)間(記為“CPU”),梯度范數(shù)(記為“GN”)以及函數(shù)值(記為“VAL”).終止準(zhǔn)則為GN=‖g(xk)‖2<10?6或迭代次數(shù)超過kmax=500,其中xk表示第k步迭代點(diǎn).數(shù)值實(shí)驗(yàn)的機(jī)器環(huán)境為Intel(R)Core(TM) i7-2670QM,CPU 2.20GHZ,內(nèi)存8GB的Windows10操作系統(tǒng).

為了全面比較兩個(gè)算法的綜合性能,選擇了無約束優(yōu)化問題的10個(gè)不同測試函數(shù),這些測試函數(shù)源于文獻(xiàn)[25],其中10個(gè)不同的測試函數(shù)也充分地展現(xiàn)了其多樣性和非線性程度.將這些測試函數(shù)的具體形式列在表1中,同時(shí)給出不同的初始點(diǎn)信息.

表1 測試函數(shù)

所有的數(shù)值測試結(jié)果在表2-4以及圖1-2中展示.

表2-4中列出兩種算法的收斂性對比結(jié)果.事實(shí)上,可以給出更多不同參數(shù)下的收斂性狀況.本節(jié)給出當(dāng)參數(shù)α=2,β=1,γ=1,δ=2,c=100的情形.從相關(guān)收斂性指標(biāo)中,注意到VAL未必都會(huì)趨向于零,原因是有些測試函數(shù)并非在零處取得其最小值.在圖1-圖2中,顯示了在不用維數(shù)下算法AADQN的迭代序列{xk}的梯度范數(shù)(GN)下降速度非常迅速,且明顯優(yōu)于算法DNRTR,特別是針對Pertured Quadratic函數(shù)維數(shù)較高(n=10000)情形,算法AADQN的迭代次數(shù)均小于30次,而算法DNRTR都超過了500次.這種高階收斂的理論依據(jù)在定理3中已給出具體證明.同時(shí)在表2-表4中也注意到對于大部分測試函數(shù),在計(jì)算成本方面,算法AADQN明顯小于算法DNRTR.

圖1 算法DNRTR 與AADQN 的收斂性軌跡, n=300,400

圖2 算法DNRTR 與AADQN 的收斂性軌跡, n=5000,10000

表2 數(shù)值結(jié)果n=300

表3 數(shù)值結(jié)果n=300

表4 Pertured Quadratic 函數(shù)在不同維數(shù)情形下的數(shù)值結(jié)果

總而言之,兩種方法均收斂到無約束優(yōu)化問題(1)的解x?.然而,無論從CPU時(shí)間與迭代次數(shù),亦或者是GN與VAL,都明顯說明了算法AADQN優(yōu)于算法DNRTR.這也意味著算法AADQN 在求解無約束優(yōu)化問題(1)時(shí)是可行且有效的.

§4 結(jié)論

本文基于對角擬牛頓更新,提出一個(gè)求解無約束優(yōu)化問題的修正Aitken加速迭代算法.這種新思想的獲得是源于在搜索方向更新時(shí)借助了對角矩陣,從而具有互相獨(dú)立的“ 點(diǎn)對點(diǎn)”更新特性,因此易于考慮引入一些有效的加速技巧.算法的高階收斂性優(yōu)點(diǎn)在理論上得到驗(yàn)證.數(shù)值實(shí)驗(yàn)結(jié)果也進(jìn)一步說明了,所提出的算法在求解無約束優(yōu)化問題時(shí)是很有意義且非常高效的.