周新慧，李小偉

(西安電子科技大學(xué)理學(xué)院，陜西西安 710071)

考慮無約束優(yōu)化問題

其中，f(x)∶Rn→R1是二次連續(xù)可微函數(shù)，對于求解式(1)目前主要有線性搜索和信賴域兩類數(shù)值方法，信賴域因?yàn)槠鋸?qiáng)收斂性、強(qiáng)適性和穩(wěn)定性等優(yōu)點(diǎn)，受到最優(yōu)化研究者的高度重視。目前眾多學(xué)者對其進(jìn)行了深入研究，傳統(tǒng)的信賴域算法具有單調(diào)性，使得步長的選擇具有一定的局限性，因此Deng等人，將1986年Grippo及Lucidi提出的求解無約束問題的非單調(diào)線性搜索方法［1］中的非單調(diào)技術(shù)引入到信賴域算法當(dāng)中，構(gòu)造了無約束優(yōu)化信賴域算法，相應(yīng)的數(shù)值試驗(yàn)表明，該算法的有效性。2004年 Zhang和Hger［2］提出了新的非單調(diào)技術(shù)。但Gu和Mo發(fā)現(xiàn)每次更新ηk和Qk使得算法的變得更為復(fù)雜。因此在此基礎(chǔ)上Gu和Mo［3］提出了另外一種非單調(diào)技術(shù)。1980年，Davidon針對二次模型對于非二次性太強(qiáng)、曲率變化較為劇烈的函數(shù)，逼近效果差等缺陷提出了錐模型［4］。之后倪勤等提出了新錐模型的子問題，取消了對信賴域半徑和水平向量的限制，將新錐模型［5］與新的可行集分成3種情形，由此得到3種不同類型的錐模型信賴域子問題。

過濾技術(shù)是由Fletchh和Leyffer于2002年在開創(chuàng)性工作中提出的解非線性規(guī)劃的一個新的總體化技術(shù)，目前過濾技術(shù)已得到廣泛的應(yīng)用并取得了較好結(jié)果，而學(xué)者將多重過濾技術(shù)運(yùn)用于二次模型［6］及新錐模型［7］中的信賴域算法中也取得了良好的效果。

在上述基礎(chǔ)之上，本文提出了基于新錐模型的非單調(diào)信賴域過濾算法

1 算法

本文將Gu和Mo提出的非單調(diào)技術(shù)應(yīng)用到新錐模型信賴域算法中定義一種新的比率，考慮到錐模型求解量大，又將過濾技術(shù)加入其中，從而減少新錐模型的運(yùn)算次數(shù)。提出新錐模型的非單調(diào)多重濾子信賴域算法。

1.1 新錐模型的子問題

新錐模型信賴域的子問題［2］

1.2 非單調(diào)技術(shù)

Gu和Mo［3］提出了一種新的非單調(diào)技術(shù)

其中

η∈(0，1)。運(yùn)用非單調(diào)技術(shù)將比值γk的制轉(zhuǎn)換為(4)

1.3 過濾技術(shù)

定義 1［8，10］令 F=(g，…，g)T，其中 g=k，1k，nk∈lk，lgl(xk)是點(diǎn)xk處的梯度向量的第i個分量，I是一個指標(biāo)集。若任取 k，l∈I，都有對至少一個i∈(1，…，n)成立，稱F是由n維梯度向量組成的過濾集。

1.4 多重濾子非單調(diào)的新錐模型信賴域算法

Step1計算gk，若則停止，否則轉(zhuǎn)Step2。

Step2用折線法求出該子問題的近似解dk。

Step3計算γk。

Step4確定實(shí)驗(yàn)步驟的可接受行。

(1)若 γk≥ρ，則接受 sk令 xk+1=xk+sk轉(zhuǎn) Step5，否則轉(zhuǎn)(2)。

(2)令 j=0，βk，j=1。

(3)若 j＞M，則令 xk，j=xk轉(zhuǎn) Step5;否則轉(zhuǎn)(4)。

(4)令 xk，j=xk+ βk，jsk若點(diǎn) xk，t被當(dāng)前過濾集 F 接受，則轉(zhuǎn)(5)。否則令 βk，j= αβk，j，t=t+1 轉(zhuǎn)(3)。

(5)令 βk= βk，j，xk+1=xk+ βkdk。

Step5更新信賴域半徑。

若 γk≤ u，則令4Δk};若 γk≤u，令 p=p+1

Step6k=k+1，更新 bk，Bk，若 ρk≥u 轉(zhuǎn) Step1。

2 收斂性的證明

假設(shè):

H1序列{Bk}，{bk}一致有界，即存在M＞0，對

H2水平集有界且f(x)在水平集上二次連續(xù)可微且有下界。

H3g(x)在水平集上是Lipschitz連續(xù)的。

H4

引理1［9］算法產(chǎn)生的點(diǎn)列xk滿足

引理2［10］若假設(shè)成立算法產(chǎn)生的點(diǎn)列xk對于任意的k都滿足數(shù)列fk+1≤Dk+1≤Dk且數(shù)列Ck收斂。證明見文獻(xiàn)［10］引理3。

引理3［3］假設(shè)H1～H4成立，且存在常數(shù) δ＞0，使，對于任意的k存在m＞0，有

以下反證法證明定理的成立。假設(shè)存在充分大的k2＞k1，當(dāng) k≥k2時，存在常數(shù) δ＞0，使 gk≥δ，?k根據(jù)式(6)可得

令 λ =(ρηδ)min{m，δ}，則(7)式可變?yōu)?/p>

由Dk得定義和式(8)可知

結(jié)合式(9)可得由式(10)整理可得

在上式兩邊取最大值，有

根據(jù)引理2 可知 Dk+M+1≤max{Dk+1，Dk+2，…，Dk+M+1}，?k，從而有

對上式及序列{Zk，k=0，1，2，…}單調(diào)上升，可得

由式(14)兩邊取極限及引理4可得

這與假設(shè)H2矛盾。

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

為說明算法的有效性，用Matlab編寫程序?qū)Ρ疚乃惴ㄟM(jìn)行數(shù)值測試，其中Nf，Ng分別表示函數(shù)值和梯度值的迭代次數(shù);n表示問題的維數(shù)。參數(shù)選擇如下:ρ=0.1，Δ0=1.0，u=0.75，ε0=0.01，B0=I，ε =10－6。測試函數(shù)1 Extended Rosenbrock funtion:f(x)=。測試結(jié)果如表1所示。

表1 測試結(jié)果

由測試結(jié)果可以看出本文所提出算法的的有效性和可行性

4 結(jié)束語

本文在求解無約束優(yōu)化問題的新錐模型信賴域算法中加入了非單調(diào)技術(shù)和多重過濾技術(shù)，目的是減少運(yùn)算次數(shù)及加大試驗(yàn)點(diǎn)被接受的幾率，數(shù)值試驗(yàn)表明，新算法對解決問題的有效性及可行性，并在一定條件下證明了算法的全局收斂性。

［1］GRIPPO L，LAMPARIELLO F，LUCIDI S.A nonmonotone line search technique for Newton's method ［J］.SIAM Journal on Numer.Anal，1986，23(4):707 －716.

［2］ZHANG H C，HAGER WW.A nenmonotone line search technique and its application to unconstrained oiptimization［J］.SIAM Journal on Optimization，2004，14(4):1043 －1056.

［3］GU N Z，MO J T.Incorporating nonmonotone strategies into the trust region method for unconstrained optimization ［J］.Applly Mathmatic Computer，2008(55):2158 －2172.

［4］DAVIDON W C.Conic approximation and collinear scaling for optimizers［J］.SIAM Journal on Number.Anal，1980，17(2):268－281.

［5］NI Q.Optimality conditions for trust－ region subproblems involving a conic model［J］.SIAM Journal on Optimization，2005，15(3):826 －837.

［6］GOULD N I M，PH L，TOINT C S.A filter－ trust－ region method for unconstrained optimization［J］.SIAM Journal on Optimization，2006，16(2):341 －357.

［7］MIAO Weihua，SUN Wenyun.A filter trust－ region mothod for unconstrained optimization［J］.SIAM Journal on Optimization，2007，17(8):561 －568.

［8］繆衛(wèi)華，孫文瑜.一個解無約束優(yōu)化問題的過濾依賴域方法［J］.高等學(xué)校計算數(shù)學(xué)學(xué)報，2007，29(1):88 －96.

［9］王慶.新錐模型信賴域算法［D］.太原:太原科技大學(xué)，2009.

［10］趙絢.新錐模型信賴域算法［D］.太原:太原科技大學(xué)，2010.