一個(gè)新的非單調(diào)信賴域算法*

趙 丹

(連云港師范高等?？茖W(xué)校 數(shù)學(xué)與信息工程學(xué)院,江蘇 連云港 222006)

0 引言

考慮無約束優(yōu)化問題minf(x),其中f:n→是二次連續(xù)可微函數(shù).信賴域方法是一種比較穩(wěn)定的迭代方法,其基本思路是在每次迭代求信賴域子問題的解δk,

(1)

其中g(shù)k=f(xk),Bk∈n×n是近似于海森矩陣2f(x)的對稱矩陣,Δk是信賴域半徑.

信賴域方法實(shí)現(xiàn)的關(guān)鍵是如何求得信賴域子問題.當(dāng)試探步δk不被接受時(shí),需要縮小信賴域半徑Δk,重新求解.為了避免子問題重新求解,減少計(jì)算量,優(yōu)化工作者創(chuàng)造性地將線搜索技術(shù)與信賴域方法相結(jié)合,提出一類新的求解方法.本文將非單調(diào)wolfe線搜索技術(shù)[1]應(yīng)用到自適應(yīng)信賴域方法中,每步都進(jìn)行非單調(diào)wolfe線搜索得到下一個(gè)迭代點(diǎn),同時(shí)利用自適應(yīng)方法確定下一步信賴域的半徑,并采用新擬牛頓方法[2]修正Bk,以保證海森矩陣的正定性及對目標(biāo)函數(shù)更高的逼近精度.在一定的假設(shè)條件下,分析討論了該算法的全局收斂性，并通過數(shù)值實(shí)驗(yàn)說明了該算法的可行性.

1 非單調(diào)線搜索技術(shù)以及BFGS校正公式

為了克服fl(k)作為參考函數(shù)值的不足,文獻(xiàn)[1]提出了一個(gè)非單調(diào)線搜索技術(shù).數(shù)值實(shí)驗(yàn)表明此技術(shù)非常有效,其非單調(diào)wolfe線搜索形式如下:

(2)

(3)

(4)

(5)

其中,ηk-1∈[0,1).

注當(dāng)ηk-1≡0時(shí),非單調(diào)wolfe線搜索準(zhǔn)則為一般的wolfe搜索準(zhǔn)則;當(dāng)ηk-1趨近于1時(shí),非單調(diào)性增強(qiáng).

應(yīng)用新的擬牛頓方程[2]來定義二次模型(1)中的矩陣Bk.新的擬牛頓方法同時(shí)采用了最新迭代點(diǎn)處的梯度與函數(shù)值信息以及Bk來定義Bk+1,因此對于海森矩陣的逼近程度較高且計(jì)算量小,并可以得到繼承對稱正定性質(zhì)的Bk.應(yīng)用最為著名的BFGS更新公式,即MBFGS方法:

(6)

其中,

yk=gk+1-gk,

θk=6(f(xk)-f(xk+1))+3(f(xk)+

f(xk+1))T(xk+1-xk),

2 非單調(diào)信賴域算法

本文提出的非單調(diào)信賴域算法的基本思想是:在當(dāng)前迭代點(diǎn)xk處非精確求解信賴域子問題(1)得到試探步δk,以此為下降方向進(jìn)行非單調(diào)wolfe線搜索得到下一個(gè)迭代點(diǎn),同時(shí)利用自適應(yīng)方法更新信賴域半徑,并采用BFGS公式修正Bk,以保證海森矩陣的正定性.

算法的具體步驟:

步1 給定x0∈n,B0∈n×n對稱,).

步2 如果||gk||≤ε,則停;否則非精確求解信賴域子問題(1),得到試探步δk.

如果ρk>c0,令p=0,計(jì)算c6=||δk||/||yk||,其中yk=gk+1-gk,更新Δk+1:

步4 取αk∈(0,1],使其滿足非單調(diào)wolfe線搜索(2)和(3).

步5 由BFGS校正公式(6)修正Bk+1,令k:=k+1,轉(zhuǎn)步2.

注步2—步5—步2稱為內(nèi)循環(huán).

3 算法的收斂性

本文所需假設(shè)H:

(1) 對任意的x0∈n,水平集L(x0)={x|f(x)≤f(x0)}有界,且函數(shù)f(x)在水平集L(x0)上二階連續(xù)可微;

(2) 矩陣序列{Bk}一致有界,即存在N>0,使得對?k,有||Bk||≤N;

(3) 存在m>0，使得tTBkt≥m||t||2,?t∈n;

(4) 梯度函數(shù)g(x)在水平集L(x0)上Lipschitz連續(xù),即存在L>0,使得對?x,y∈L(x0),||g(x)-g(y)||≤L||x-y||.

引理1序列{xk}由算法產(chǎn)生,則?k,有fk+1≤Ck+1≤Ck.

證明先證Ck≥fk.用數(shù)學(xué)歸納法證明如下.

當(dāng)k=0時(shí),C0=f0;假設(shè)當(dāng)n=k時(shí),Ck≥fk成立.

結(jié)合(2)，得

(7)

由(4)和(5)可知

(8)

再證Ck≥Ck+1.

由(4)和(5)可知

(9)

綜上,可證之.

證明由引理1知,fk+1≤Ck+1≤Ck≤C0=f0;而x0∈L(x0),故xk∈L(x0).

由假設(shè)H(1)知,{fk}有下界.同時(shí),由于{Ck}非增,Ck≥fk,故{Ck}收斂.

由(4)和(5)可知

Ck+1Qk+1=ηkQkCk+fk+1=

(Qk+1-1)Ck+fk+1.

即

fk+1=Qk+1(Ck+1-Ck)+Ck.

(10)

反復(fù)利用(5)，有

(11)

再利用(10)，知

(12)

即

(13)

引理3如果假設(shè)H成立,則算法是適定的,即算法不會(huì)在內(nèi)循環(huán)內(nèi)無限次循環(huán).

證明假設(shè)算法在迭代點(diǎn)xk處于步2至步5之間無限次循環(huán).記k(i)是當(dāng)前迭代點(diǎn)xk處的循環(huán)指標(biāo),則有ρk(i)≤c0,i=1,2,…,即

(14)

|ρk(i)-1|=

定理1若假設(shè)H成立,當(dāng)ε=0時(shí)算法有限步終止,或者產(chǎn)生一個(gè)無限序列{xk}滿足

(15)

證明不妨設(shè)算法不能有限終止.則當(dāng)式(15)不成立時(shí),存在一個(gè)正常數(shù)ε0,有||gk||≥ε0,?k.

(16)

(17)

利用假設(shè)H(3)得到

(18)

(19)

LΔk||δk||≥

L||xk+1-xk||·||δk||≥

||gk+1-gk||·||δk||≥

τ(1-λ2)||gk||min{Δk,||gk||/||Bk||}.

(20)

由引理2和假設(shè)H(2)知,當(dāng)k充分大時(shí),min{Δk,||gk||/||Bk||}=Δk.故

LΔk||δk||≥τ(1-λ2)||gk||Δk.

(21)

因此

(22)

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

本文選取了文獻(xiàn)[4]中關(guān)于無約束優(yōu)化的10個(gè)中小規(guī)模問題,其變量個(gè)數(shù)均不超過200.分別對文獻(xiàn)[5]中的自適應(yīng)信賴域算法與新的非單調(diào)信賴域算法進(jìn)行了數(shù)值實(shí)驗(yàn).所有算法均使用兩種終止準(zhǔn)則,一是算法收斂,即

||gk||<10-6(1+||g0||);

二是算法在500次迭代內(nèi)不收斂.

對于文獻(xiàn)[5]中的自適應(yīng)信賴域方法及本文所提出的新的非單調(diào)信賴域方法,盡量選取同樣的參數(shù),其中c1=0.5,c0=0.1,c=0.5.文獻(xiàn)[5]中的自適應(yīng)信賴域算法中Bk由BFGS修正公式得出,即

(23)

其中sk=δk,且

詳細(xì)的數(shù)值結(jié)果如表1所示.在表1中,No.表示測試函數(shù)的編號(hào),n表示測試函數(shù)的維數(shù),m表示子函數(shù)的個(gè)數(shù).從表1可知,本文所提出的新的非單調(diào)信賴域方法是有效的.

表1 數(shù)值結(jié)果

參考文獻(xiàn):

[1] ZHANG Hongchao, HAGER W W. A nonmonotone line search technique and its application to unconstrained optimization[J]. SIAM Journal on Optimization, 2004, 14(4): 1043-1056.

[2] 趙丹.一個(gè)新的擬牛頓信賴域方法[J].貴州師范大學(xué)學(xué)報(bào):自然科學(xué)版,2012,30(2):65-67.

[3] 徐成賢,陳志平,李乃成.近代優(yōu)化方法[M].北京:科學(xué)出版社,2002.

[4] MORE J J, GARBOW B S, HILLSTROM K E. Testing unconstrained optimization software[J]. ACM Transactions on Mathematical Software, 1981, 7(1/2): 17-41.

[5] HANG Xiangsun, ZHANG Juliang, LIAO Lizhi. An adaptive trust region method and its convergence[J]. Science in China Series A, 2002, 45: 620-631.

[6] 龐善民,陳蘭平.一類新的非單調(diào)信賴域算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2011,41(10):211-218.

[7] 陳宏欽.一類新的非單調(diào)信賴域算法[D].西安:西安電子科技大學(xué),2009.

[8] 趙丹.預(yù)處理混合割線法求解信賴域子問題[J].淮海工學(xué)院學(xué)報(bào):自然科學(xué)版,2013,22(3):8-10.