帶回溯線搜索的新錐模型信賴域算法

郎立勤，王希云

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原030024)

基于無(wú)約束優(yōu)化問(wèn)題:

信賴域算法無(wú)疑是一種非常成功的算法，其中f:Rn→R為二階連續(xù)可微函數(shù)，目前有眾多學(xué)者對(duì)其進(jìn)行了深入的研究。傳統(tǒng)的信賴域算法主要是利用二次模型來(lái)逼近目標(biāo)函數(shù)，即構(gòu)造二次模型對(duì)問(wèn)題(1)進(jìn)行求解，然而對(duì)于非二次性態(tài)強(qiáng)、曲率變化較為劇烈的函數(shù)，逼近的效果往往不是很好。針對(duì)這一缺陷，1980年Davidon[1]提出了錐模型，使模型更加一般化，之后倪勤[2]等提出了新的錐模型信賴域子問(wèn)題，取消了對(duì)信賴域半徑和水平向量的限制，克服錐函數(shù)的可能無(wú)界性，為進(jìn)一步研究錐模型方法開(kāi)拓了一片廣闊的發(fā)展空間。

新錐模型信賴域子問(wèn)題:

其中Bk是f(x)在xk點(diǎn)的海森陣或海森陣近似，gk=-▽f(xk)，并且

求解信賴域子問(wèn)題時(shí)，當(dāng)試探步dk不能作為成功的迭代點(diǎn)時(shí)，也就是說(shuō)當(dāng)新求得的dk會(huì)使得目標(biāo)函數(shù)值上升的時(shí)候，總可以沿著dk方向進(jìn)行回溯的線搜索，以致找到使目標(biāo)函數(shù)下降的點(diǎn)。這里說(shuō)的回溯線搜索實(shí)際上就是充分利用當(dāng)前迭代點(diǎn)的信息構(gòu)造一個(gè)αk，找到一個(gè)滿足:

的最小的整數(shù)i.其中 αk∈(0，1)，并且 αi+1kdk∈[a1，a2]αi

kdk，0 ＜a1＜a2＜1.唐明筠[3]利用高階的插值得到的如下形式的αk:

由于當(dāng)?shù)r(shí)重解子問(wèn)題付出的代價(jià)會(huì)很高，這里將回溯線搜索應(yīng)用到新錐模型信賴域方法上構(gòu)造了一類(lèi)新的帶線搜索的算法，減少了計(jì)算量，提高了計(jì)算效率。其中自適應(yīng)信賴域半徑的調(diào)節(jié)是參考文獻(xiàn)[4]中的確定，c∈(0，1)，p是非負(fù)整數(shù)。

1 算法

實(shí)際下降量和預(yù)測(cè)下降量的比值:

下面給出帶回溯線搜索的自適應(yīng)新錐模型信賴域算法的具體步驟:

步0 給定x0∈Rn，對(duì)稱(chēng)矩陣B0∈Rm×n，△0＞0，τ ＞0，0≤μ1≤μ≤1，β∈(0，1)，α∈(0，1)，0 ＜c＜1，ε ＞0，p=0，k:=0，M=0.

步1 計(jì)算‖gk‖，若‖gk‖≤ε，則停止;否則轉(zhuǎn)步2.

步2 用折線法求解該子問(wèn)題的近似解dk.

步 3 計(jì)算 ρk，若 ρk≥μ，則令xk+1=xk+dk;否則利用式(4)計(jì)算αk，進(jìn)行回溯線搜索尋求滿足的最小的正整數(shù)i，令xk+1=

步4 若 ρk≥ μ，令

若 ρk≤μ1，令‖gk+1‖;否則，令△k+1= △k.

注:本文中Bk，bk的更新采用錐模型擬牛頓法，同文獻(xiàn)[5]。

2 算法的收斂性

I={k:ρk≥μ}，J={0，1，…}I

H1:水平集L(x0)={x|f(x)≤f(x0)}是有界的，而且xk∈L(x0);

H2:數(shù)列{fk}有下界;

H3:存在正的常數(shù)σ，使得‖Bk‖≤σ，‖bk‖≤σ，?k;

引理1[3]算法產(chǎn)生的點(diǎn)列{xk}滿足:

總體而言，目前對(duì)于馬克思哲學(xué)終極關(guān)懷內(nèi)容的研究正在蓬勃興起，但尚未形成較為成熟的體系與規(guī)模。馬克思哲學(xué)終極關(guān)懷思想作為其超越維度的核心核心內(nèi)容之一，彰顯了馬克思以人為終極目的的真切關(guān)注和對(duì)人意義世界的開(kāi)創(chuàng)性探索，因此對(duì)于這一問(wèn)題的厘清和解決勢(shì)必將會(huì)對(duì)馬克思哲學(xué)超越維度的整體性呈現(xiàn)奠定重要的理論基礎(chǔ)。

引理2[6]若H2成立，則數(shù)列{fl(k)}非增并且收斂。

引理3[7]若H1-H3成立，且由本文算法產(chǎn)生的點(diǎn)列為{xk}滿足‖gk‖≠0，那么存在，當(dāng)≥△k時(shí)就有△k+1≥△k.

基于上述的引理，可以得到以下的全局收斂性結(jié)論。

定理1 如果H1-H3均成立，那么由算法產(chǎn)生的點(diǎn)列{xk}會(huì)滿足

證明 (用反證法)假設(shè)之上結(jié)論是不成立的，則必然存在常數(shù)ε＞0和正常數(shù)K，使‖gk‖≥ε，?k≥K.由引理1和本文的算法可以知道，對(duì)于任意的成功的迭代步dk總有

以此類(lèi)推下去，有:

根據(jù){fl(k)}的定義容易得到:

由引理2可知{fl(k)}收斂，所以可得:.這與引理3矛盾，即結(jié)論得證。證畢。

定理2 若H1-H3均成立，而且由本文算法產(chǎn)生的點(diǎn)列{xk}滿足‖g*‖=0，▽2f(x)在x*附近連續(xù)并且▽2f(x*)正定，如果，則可以得到{xk}Q-二階收斂于x*.

證 明 用 反 證 法 證 明。令 κ=，下面證明κ中只有有限個(gè)元素。

這里假設(shè)κ中有無(wú)窮個(gè)元素，那么結(jié)合假設(shè)條件可以知道:

當(dāng)k充分大時(shí)，就有

于是，

即有rk→1.由本文的算法可以知道，對(duì)于充分大的k有rk＞μ成立，于是就有△k+1≥△k，這與產(chǎn)生矛盾，所以κ中只有有限個(gè)元素。因此對(duì)充分大的k有，于是，dk=，此時(shí)算法采用的是牛頓下降步，所以{xk}Q-二階收斂于x*.證畢。

表1 數(shù)值測(cè)試結(jié)果Tab.1 Numerical results

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

從數(shù)值結(jié)果可以看出:無(wú)論從迭代次數(shù)上還是計(jì)算結(jié)果上都可以看出帶回溯線搜索的自適應(yīng)信賴域算法比帶Armijo線搜索的錐模型信賴域算法計(jì)算效率要高，而且從運(yùn)算需要的時(shí)間上可以看出，本文的算法確實(shí)更加經(jīng)濟(jì)省時(shí)，在數(shù)值試驗(yàn)上基于新錐模型的算法也是可行的，穩(wěn)定的。但是在解決一些大規(guī)模問(wèn)題上還有待深入研究。

[1]DAVIDON D C.Conic approximations and collinear scaling for optimizers[J].SIAM J Numer Anal，1980，17(2):268-281.

[2]吳海平，倪勤.一個(gè)新錐模型信賴域算法[J].高等學(xué)校計(jì)算機(jī)數(shù)學(xué)學(xué)報(bào)，2008，30(1):57-67.

[3]唐明筠.帶回溯線搜索步的雙子問(wèn)題信賴域算法[J].工程數(shù)學(xué)學(xué)報(bào)，2010，27(4):626-636.

[4]ZHANG X S，ZHANG J L，LIAO L Z.An adaptive trust region method and its convergence[J].Science in China:series A，2002，45:619-631.

[5]趙絢，王希云.一類(lèi)新的帶線搜索的自適應(yīng)非單調(diào)信賴域算法[J].太原科技大學(xué)學(xué)報(bào)，2010，32(1):67-71.

[6]李紅，焦寶聰.一類(lèi)帶線搜索的自適應(yīng)信賴域算法[J].運(yùn)籌學(xué)學(xué)報(bào)，2008，12(2):97-104.

[7]王希云，王慶.一種新錐模型非單調(diào)信賴域算法[C]//中國(guó)運(yùn)籌會(huì)第九屆交流會(huì)論文集.北京:中國(guó)運(yùn)籌學(xué)會(huì)，2008:110-116.