解無約束優(yōu)化的非單調(diào)自適應(yīng)信賴域算法

曾劉拴

(重慶大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶401331)

0 引言

本文考慮無約束最優(yōu)化問題:

其中，f(x):Rn→R二階連續(xù)可微且有下界。信賴域方法是一種迭代方法，在每次迭代中，試探步dk可通過求解下面的子問題得到:

其中 d=xk+1－xk，gk=?f(xk)，對(duì)稱陣 Bk∈Rn×n是?2f(xk)或其近似，Δk＞0 是信賴域半徑，‖.‖是向量范數(shù)或由它導(dǎo)出的矩陣范數(shù)。由式(2)求得的試探步d是否被接受，取決于兩個(gè)下降量的比值，即，其k中Aredk=f(xk)－f(xk+dk)表示實(shí)際下降量，Predk=φk(0)－φk(dk)表示預(yù)測下降量。

無約束信賴域方法的收斂結(jié)果是由Powell［1］首次得到的，后經(jīng)許多學(xué)者的研究，信賴域方法得到了很好地發(fā)展，已經(jīng)成為優(yōu)化算法兩大分支之一。2000年，Conn等人出版了關(guān)于信賴域方法的專著［2］。近年來，非單調(diào)線搜索技術(shù)得到廣泛應(yīng)用，此方法是Grippo等［3］首次提出的，因其具有較好的數(shù)值效果而得到了廣泛應(yīng)用。關(guān)于非單調(diào)技術(shù)的研究主要有文獻(xiàn)［4-6］等。2008年，Mo和Gu［7］提出了一種較為簡單的非單調(diào)技術(shù)，即:

并將此技術(shù)運(yùn)用到信賴域方法中，獲得了較好的數(shù)值效果。

自適應(yīng)方法是由Sartenear［8］首次提出的，此方法可以避免信賴域半徑更新的盲目性。自適應(yīng)方法進(jìn)一步研究的主要有文獻(xiàn)［9-10］等。2009年，Sang和Sun［11］充分利用當(dāng)前迭代點(diǎn)的信息提出了一種自適應(yīng)方法，即令:

濾子技術(shù)是由Fletcher和Leyffer［12］提出的，其最初的目的是為了克服使用價(jià)值函數(shù)時(shí)選取罰因子的困難。2005年，Gould等［13］將濾子技術(shù)應(yīng)用到一般的無約束優(yōu)化問題中，提出了一個(gè)濾子信賴域方法，證明了其收斂性，并得到較理想的數(shù)值效果。

本文基于簡單二次模型式(2)，結(jié)合 Mo等［7］的非單調(diào)技術(shù)、Sang和 Sun［11］的自適應(yīng)技術(shù)及 Gould等［13］的濾子技術(shù)提出一個(gè)非單調(diào)自適應(yīng)信賴域算法。當(dāng)試探步不被接受時(shí)，采用濾子技術(shù)，增加試探步被接受的可能性;如果試探步也不被濾子集接受，取dk=－，沿dk方向進(jìn)行非單調(diào)Armijo線搜索，得到步長αk，從而得新的迭代點(diǎn) xk+1=xk+αkdk。

1 基于二次模型的非單調(diào)濾子自適應(yīng)信賴域算法

1.1 算法1(FNTR)

步1:給定 x0∈Rn，0 ＜ ω1＜ ω2＜1，μ0=1，δ∈(0，0.5)，η∈(0，1)，λ∈(0，1)，ε ＞0。0 ＜ c2＜1 ＜ c1，0 ＜ c2＜1＜＞0，γg∈=E(單位陣)，初始濾子集 F0，k←0。

步 2:計(jì)算‖gk‖，若‖gk‖≤ε，則 x*=xk，停止計(jì)算，否則，轉(zhuǎn)步 3。

步3:計(jì)算f(xk)，Bk解信賴域子問題得試探步dk，令=xk+dk。

步5:若rk≥ω1，令xk+1=;否則，計(jì)算=g()，若被Fk接受，令xk+1=，并將加入到Fk，同時(shí)去除Fk中所有被支配的點(diǎn)，得到Fk+1;否則，令dk=－，求ik，使得ik是滿足

的最小的非負(fù)整數(shù)，令 αk=λik，xk+1=xk+αkdk。

步6:按式(5)、式(6)更新信賴域半徑，轉(zhuǎn)第2步。

說明:?i=1，2，…，n，算法1第3步中的實(shí)正定對(duì)角矩陣:

1.2 算法的收斂性

在此給出以下假設(shè):(M)f(x)在有界閉集H={x|f(x)≤f(x0)}上二階連續(xù)可微。為討論問題的方便，記 T={k|rk≥ω1}，S={k|加到濾子集中}，A={k|rk＜ω1}/S。

引理1［14］如果{B}是由算法1產(chǎn)生的，則對(duì)任意的k，Bk及都是正定對(duì)角陣，L≤‖B‖≤L，且存在 m1，m2＞0 使得 m1≤‖‖≤m2。

引理2［11］若dk是子問題(2)的解，則有:

即有Dk+1≤Dk，所以當(dāng)k∈T時(shí)結(jié)論成立。

第二種情況:k∈S

由濾子的定義知 fk+1≤fk。若 k －1∈T，則有 fk≤Dk≤Dk－1，從而有 Dk+1= ηDk+(1 － η)fk+1≤ηDk－1+(1 －η)fk=Dk，即 Dk+1≤Dk，又因 Dk+1－ fk+1=η(Dk－ fk+1)≥η(fk－ fk+1)≥0，即 fk+1≤Dk+1，所以有 fk+1≤Dk+1≤Dk。若 k －1∈S，令 M={i|1 ＜ i≤k，k －i∈T}。如果 M=Φ，則有 fk+1≤fk≤…≤f1≤f0=D0。

下面用數(shù)學(xué)歸納法證明Dk+1≤Dk。

因 D0=f0，所以 k=1 時(shí)有 D1=ηD0+(1 －η)f1≤ηf0+(1 － η)f0=f0=D0。假設(shè) k=n時(shí)，有 Dn+1≤Dn，下證 k=n+1 時(shí)有 Dn+2≤Dn+1。而 Dn+2=ηDn+1+(1 － η)fn+2≤ηDn+(1 － η)fn+1=Dn+1。所以 Dk+1≤Dk成立;再證 fk+1≤Dk+1，因 Dk+1－Dk=(η－1)Dk+(1－η)fk+1=(1－η)(fk+1－Dk)。

而由上面的證明可知 Dk+1≤Dk，又1 － η ＞0，所以有 fk+1－Dk≤0，即 fk+1≤Dk，從而有 Dk+1=ηDk+(1 －η)fk+1≥ηfk+1+(1 － η)fk+1=fk+1。如果 M≠Φ，設(shè) m=min{i|i∈M}，則有 fk+1≤fk≤…≤fk－m+1，因 k－ m∈T，由第一種情況可知 fk－m+1≤Dk－m+1≤Dk－m，而 Dk－m+2= ηDk－m+1+(1 － η)fk－m+2≤ηDk－m+(1 － η)fk－m+1=Dk－m+1。由歸納法可得 Dk+1≤Dk，從而同上可得 fk+1≤Dk+1。

綜上可得當(dāng) k∈S 時(shí)，有 fk+1≤Dk+1≤Dk。

第三種情況:k∈A

則有 Dk+1＜ Dk，所以有 fk+1≤Dk+1≤Dk。

綜合上面三種情況可知，對(duì)任意的k都有fk+1≤Dk+1≤Dk。

引理5［7］如果假設(shè)(M)成立，αk滿足式(7)，則對(duì)任意的k∈A都有:

反證，假設(shè)對(duì)充分大的k有‖gk‖≥ε0＞0。

證明:反證，假設(shè)當(dāng)k充分大時(shí)，有‖gk‖≥ε＞0。

由引理4知{Dk}單調(diào)下降，又{Dk}有界，故其收斂，再由引理3和引理5得:

2 數(shù)值試驗(yàn)

本節(jié)給出算法1(FNTR)的數(shù)值試驗(yàn)結(jié)果，并與基本信賴域算法(TR)(文獻(xiàn)［15］中算法3.6.1)做比較。算法用Matlab 7.01編寫程序。Fval表示最優(yōu)點(diǎn)處的函數(shù)值，Gnorm表示迭代終止時(shí)函數(shù)梯度的范數(shù)，K表示迭代次數(shù)，CPU代表運(yùn)行時(shí)間(單位為s)。設(shè)定精度‖gk‖≤10－3。檢驗(yàn)函數(shù)取自文獻(xiàn)［16］，初始點(diǎn)的選取與文獻(xiàn)［16］相同。如果計(jì)算不出結(jié)果或者時(shí)間超過200 s或者迭代次數(shù)超過1 000次，則用“—”表示。

算法1(FNTR)中，選擇的參數(shù):μ0=1，ω1=0.20，ω2=0.80，c1=1.5，c2=0.5，λ =0.5，δ=0.4，η =0.15，γg=min{0.003。檢驗(yàn)函數(shù)如表1，數(shù)值結(jié)果如表3。其中各個(gè)函數(shù)中和的選取見表2。

表1 檢驗(yàn)函數(shù)對(duì)應(yīng)編號(hào)

表2 和的值

表2 和的值

?

3 結(jié)束語

從表3的數(shù)據(jù)可以看出，對(duì)絕大多數(shù)測試函數(shù)，算法1(FNTR)具有迭代次數(shù)較少、運(yùn)行時(shí)間較短的優(yōu)勢，且對(duì)于測試函數(shù)中的rosex，singx，pen1，vardim，bv這些函數(shù)，在高維情況下基本信賴域算法失效，而算法1(FNTR)則可以很好地求解，因此算法1(FNTR)是比較有效的，而對(duì)于trig，ie這兩個(gè)函數(shù)算法1(FNTR)的優(yōu)勢不太明顯，有待進(jìn)一步研究。

表3 算法1(FNTR)和基本信賴域算法的數(shù)值結(jié)果

續(xù)表

［1］ POWELL M J D.Convergence properties of a class of minimization algorithm［C］//Nonlinear Programming II，New York，Academic Press，1975:1-27

［2］CONN A R，GOULD N I M，TOINT Ph L.Trust－ Region Methods［M］.SIAM Publications，2000

［3］GRIPPO L，LAMPARIELLO F，LUCIDI S.A nonmonotone line search technique for Newton’s method［J］.SIAM Journal on Numerical Analysis，1986，23(4):707-716

［4］DENG N，XIAO，ZHOU F J.Nonmonotone trust region algorithm［J］.Journal of Optimization Theory and Applications，1993，76(2):259-285

［5］ZHANG H，HAGER W.A nonmonotone line search technique and its application to unconstrained optimization［J］.SIAM Journal on Optimization，2004，14(4):1043-1056

［6］MO J，LIU C，YAN S.A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function values［J］.Journal of Computational and Applied Mathematics，2007，209(1):97-108

［7］GU Z，MO J.Incorporating nonmonotone strategies into the trust region method for unconstrained optimization［J］.Computers and Mathematics withApplications，2008，55(9):2158-2172

［8］SARTENAER A.Automatic determination of an initial trust-region in nonlinear programming［J］.SIAM Journal on Scientific Computing，1997，18(6):1788-1803

［9］FAN J，YUAN Y.A new trust region algorithm with trustregion radius converging to zero［C］//Proceedings of the 5th International Conference on Optimization:Techniquesand Applications，HongKong，Dec，2001

［10］ZHANG X，ZHANG J，LIAO L.An adaptive trust method and its convergence ［J］.Computers and Mathematics with Applications，2003，45(10-11):1469-1477

［11］SANG Z，SUN Q.A self-adaptive trust region method with line search based on a simple subproblem model［J］.Journal of Computational and Applied Mathematics，2009，232(2):514-522

［12］FLETCHER R，LEYFFER S.Nonlinear programming without a penalty function［J］.Mathematical Programming，2002，91(2):239-269

［13］GOULDN I，SAINVITUC，TOINTP.A filter-trust-region method for constrained optimization［J］.SIAM Journal on Optimization，2005，16(2):341-357

［14］馮琳，段復(fù)建，和文龍.基于簡單二次函數(shù)模型的濾子非單調(diào)信賴域方法［J］.山東大學(xué)學(xué)報(bào):理學(xué)版，2012(5):1-8

［15］袁亞湘，孫文瑜.最優(yōu)化理論與方法［M］.北京:科學(xué)出版社，1997

［16］MORE J，GARBOW B，HILLSTROM K.Testing uncontrained optimization software［J］.ACM Trans Math Softw，1981，7(1):136-140.