謝亞君 ,姚 潔 ,馬昌鳳
(1.福州外語外貿(mào)學(xué)院理工學(xué)院,福建福州 350202;2.福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院,福建福州 350007)
基于Neculai[1]的工作,本文提出一種求解如下無約束優(yōu)化問題
的Aitken加速方法,其中f ∈Rn→R為連續(xù)可微的函數(shù).
至今為止,無約束優(yōu)化問題的求解已獲得廣泛關(guān)注,并取得豐碩的研究成果(見[2-6]),其中,包括共軛梯度法(見[7]),牛頓法與擬牛頓法等(見[8-12]).雖然牛頓法具有二階收斂速度的優(yōu)勢,但是需要計算二階導(dǎo)數(shù).因此在求解大規(guī)模問題時,該方法往往因為計算代價過高而變得不再適用.同時當Hessian陣非正定時,無法保證所產(chǎn)生的方向是目標函數(shù)的下降方向.尤其是當Hessian陣奇異時,算法無法繼續(xù)循環(huán)迭代.修正牛頓法可在一定程度上克服此缺陷,然而修正參數(shù)的選取較難把握,對收斂速度亦有較大影響.眾所周知,擬牛頓法可以避免這些缺點,在迭代過程中不需要計算目標函數(shù)的Hessian陣,卻在某種意義下具有Hessian陣的作用,因此該方法在相關(guān)領(lǐng)域得到廣泛的應(yīng)用.例如,均衡問題,神經(jīng)網(wǎng)絡(luò),激光檢測,非線性方程組等(見[13-16]).
假設(shè)x0為某個初值點.求解問題(1)的迭代格式有如下表達式
其中αk是由某種線搜索,例如Wolfe或Armijo線搜索獲得的步長,dk表示搜索方向.通常對問題(1)的迭代求解格式有兩個主要切入點,一個是針對步長因子αk進行合理設(shè)計,另一個是考慮有效地選取較優(yōu)的搜索方向dk.詳細可參看文獻[17-20].
牛頓法是通過求解如下方程得到牛頓搜索方向dk,
其中Gk,gk分別表示函數(shù)f在點xk處的Hessian矩陣和梯度值.鑒于Hessian陣Gk高昂的計算代價,可尋求一個矩陣Bk+1作為Hessian陣Gk+1的一種近似替代.將函數(shù)f在點xk+1處利用二次Taylor展開得到近似方程
進而構(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]).
在文獻[1]中,Neculai證明了一個簡單而有效的對角擬牛頓更新公式來求解
針對問題(6),基于對角擬牛頓更新迭代法(DNRTR)(見[1]),提出一個修正的Aitken加速迭代格式來求解無約束優(yōu)化問題(1),該方法在與前者對比的過程中顯示了非常良好且具有明顯優(yōu)勢的收斂性能.
本文剩余部分組織如下:§2提出求解無約束優(yōu)化問題(1)的修正Aitken加速迭代方法,同時證明了其具有良好的高階收斂性能.數(shù)值實驗和結(jié)論分別安排在§3和§4.
本節(jié)考慮改善對角擬牛頓更新方法(DNRTR)(見[1]),進而引入一個修正Aitken加速迭代格式來求解優(yōu)化問題(1).最后提供重要的理論證明和收斂性結(jié)果.首先注意到問題(6)亦可轉(zhuǎn)化為如下形式
問題(7)的Lagrangian函數(shù)為
其中λ表示其Lagrangian乘子.由最優(yōu)性條件可得
將(10)式代入(7)式,即可得Lagrangian乘子
算法1(基于擬牛頓更新的Aitken加速算法(AADQN))
步1 給定初始點x0∈Rn,參數(shù)0<β <1,0<σ <0.5,m=0及充分小的正數(shù)ε1,ε2>0.計算向量g0=?f(x0).令d0=?g0,k=0.
步2 若‖g(xk)‖2<ε1停算;否則,轉(zhuǎn)到步3.
步3 計算滿足線搜索的步長αk,若不等式
成立,令mk=m,αk=βmk;否則,m:=m+1,然后循環(huán)(14).再計算
步4 利用公式(12)更新對角矩陣Bk+1.
步5 令
其中i=1,···,n,.置xk=.
步6 更新搜索方向
步7 置k:=k+1,返回步2.
注記1顯然經(jīng)過計算可知(19)所確定的搜索方向是下降的,即g(xk+1)Tdk+1<0.事實上有
由上式可得,若‖g(xk+1)‖≠0,則有g(shù)(xk+1)Tdk+1<0.
當k→∞,若xk→x?且‖g?‖→0,則由算法步5定義的格式x=φ(x)即為不動點迭代.關(guān)于‖g?‖→0的事實將在后面收斂性分析給出詳細證明.
下面先給出算法的適定性證明.
引理1序列{Δk},{Bk}由更新格式(12)產(chǎn)生.此外,若‖sk‖≠0,且存在(i=1,2,···,n),其中為對角矩陣B0的第i個對角元素,則對所有的正整數(shù)k,序列{Δk},{Bk}有界.
證當k=0,y0=?2f(?0)s0,其中x00 注意到‖s0‖2≤n()2且由已知條件 即B1也是有界的.從而由歸納法可得引理結(jié)論. 文獻[24]中給出了所謂界退化性質(zhì) 其中Bk+1是前一步迭代矩陣Bk的更新,νk=max{‖xk+1?x?‖,‖xk ?x?‖},κ為某個常數(shù).該文描述了Hessian矩陣與其近似矩陣Bk+1可由前一步迭代中二者的差值來控制的事實,既滿足界退化性質(zhì),同時也給出了滿足此性質(zhì)的算法至少具有q-線性收斂的結(jié)果(詳見[24]).下面證明更新公式(12)滿足界退化性質(zhì). 引理2若‖sk‖≠0,則更新公式(12)滿足界退化性質(zhì). 證由更新公式(12)可得 由于‖sk‖≠0,因此必存在ρ>0,使得‖sk‖>ρ,同時有且 其中?sk為向量sk的最大值分量.注意到 綜合以上引理1-2 可得下面結(jié)論. 定理1若存在兩個正的常數(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的余弦值大于某個常數(shù)λ ∈(0,1); (b){xk}的任意聚點x?都滿足?f(x?)=0. 證(a) 由(19)式中步長dk的選取可知,若‖gk‖≠0,當(Bk)ii ≥ε2>0(i=1,2,···),則 否則當(Bk)ii ≤0,由算法可知取步長dk=?gk,從而cosθk=1. 綜上可知cosθk >λ >0,其中λ ∈(0,1). (b) 用反證法,設(shè)x?是{xk}的聚點且?f(x?)≠0.由條件可知f(xk)→f(x?)且f(xk)?f(xk+1)→0.又由(14)式可得 其中sk=βmkdk.若gk?0,則由(30)式可知,‖sk‖→0.又由(14)可得,對于,不等式 由于‖pk‖=1,因此{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?.由文獻[1]可知算法DNRTR至少為q-線性收斂的.下面證明算法AADQN所產(chǎn)生的序列{xk}收斂階高于算法DNRTR. 由算法AADQN可知 進一步,由極限的性質(zhì)可得 為了方便,記算法AADQN 步5 中的k=.由(38)以及(17)則有 本節(jié)給出一些數(shù)值例子來驗證§2提出的算法1(AADQN)在求解無約束優(yōu)化問題(1)時的高效性.通過與文獻[1]中的算法DNRTR 在更方面性能指標進行詳細對比.這些指標包括迭代次數(shù)(記為“IT”),消耗的CPU時間(記為“CPU”),梯度范數(shù)(記為“GN”)以及函數(shù)值(記為“VAL”).終止準則為GN=‖g(xk)‖2<10?6或迭代次數(shù)超過kmax=500,其中xk表示第k步迭代點.數(shù)值實驗的機器環(huán)境為Intel(R)Core(TM) i7-2670QM,CPU 2.20GHZ,內(nèi)存8GB的Windows10操作系統(tǒng). 為了全面比較兩個算法的綜合性能,選擇了無約束優(yōu)化問題的10個不同測試函數(shù),這些測試函數(shù)源于文獻[25],其中10個不同的測試函數(shù)也充分地展現(xiàn)了其多樣性和非線性程度.將這些測試函數(shù)的具體形式列在表1中,同時給出不同的初始點信息. 表1 測試函數(shù) 所有的數(shù)值測試結(jié)果在表2-4以及圖1-2中展示. 表2-4中列出兩種算法的收斂性對比結(jié)果.事實上,可以給出更多不同參數(shù)下的收斂性狀況.本節(jié)給出當參數(shù)α=2,β=1,γ=1,δ=2,c=100的情形.從相關(guān)收斂性指標中,注意到VAL未必都會趨向于零,原因是有些測試函數(shù)并非在零處取得其最小值.在圖1-圖2中,顯示了在不用維數(shù)下算法AADQN的迭代序列{xk}的梯度范數(shù)(GN)下降速度非常迅速,且明顯優(yōu)于算法DNRTR,特別是針對Pertured Quadratic函數(shù)維數(shù)較高(n=10000)情形,算法AADQN的迭代次數(shù)均小于30次,而算法DNRTR都超過了500次.這種高階收斂的理論依據(jù)在定理3中已給出具體證明.同時在表2-表4中也注意到對于大部分測試函數(shù),在計算成本方面,算法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ù),亦或者是GN與VAL,都明顯說明了算法AADQN優(yōu)于算法DNRTR.這也意味著算法AADQN 在求解無約束優(yōu)化問題(1)時是可行且有效的. 本文基于對角擬牛頓更新,提出一個求解無約束優(yōu)化問題的修正Aitken加速迭代算法.這種新思想的獲得是源于在搜索方向更新時借助了對角矩陣,從而具有互相獨立的“ 點對點”更新特性,因此易于考慮引入一些有效的加速技巧.算法的高階收斂性優(yōu)點在理論上得到驗證.數(shù)值實驗結(jié)果也進一步說明了,所提出的算法在求解無約束優(yōu)化問題時是很有意義且非常高效的.§3 數(shù)值實驗
§4 結(jié)論