趙 絢,朱 帥

(1.運(yùn)城師范高等?？茖W(xué)校 數(shù)學(xué)與計(jì)算機(jī)系,山西 運(yùn)城 044000;2.山西大同大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,山西 大同 037009)

考慮無(wú)約束優(yōu)化問(wèn)題

(1)

其中，f:Rn→R二次連續(xù)可微.

求解此問(wèn)題的大部分新算法是采用二次模型逼近f(x),但是對(duì)于一些非二次形態(tài)較強(qiáng)、曲率變化劇烈的函數(shù),效果不是很理想.為此,Dnvidon[1]于1980年提出了錐模型,錐模型是二次模型的推廣.Di和Sun[2]給出了錐模型信賴域子問(wèn)題的最優(yōu)性條件.文獻(xiàn)[3]和[4]提出了基于錐模型的擬牛頓信賴域算法.

為了克服原目標(biāo)函數(shù)在1-bTd>0的附近可能無(wú)界的情況,Ni[5]取消了對(duì)水平向量b的限制,對(duì)錐模型信賴域的子問(wèn)題考慮了更為一般的情況,提出了一種新錐模型信賴域子問(wèn)題

(2)

文獻(xiàn)[6]中定義了關(guān)于ρk的R-函數(shù)以變化的速率來(lái)調(diào)節(jié)信賴域半徑的大小,充分利用了ρk的信息,使信賴域半徑的調(diào)節(jié)取決于問(wèn)題本身,更具客觀性.本文將R-函數(shù)以變化的速率來(lái)調(diào)節(jié)信賴域半徑的大小的自適應(yīng)和非單調(diào)技術(shù)[7-8]相結(jié)合,提出了一種基于錐模型的非單調(diào)自適應(yīng)信賴域算法.

1 算法

定義1[6]Rμ(t)定義在(-∞,+∞)上,參數(shù)μ∈(0,1),Rμ(t)是一個(gè)R-函數(shù),當(dāng)且僅當(dāng)它滿足

(i)Rμ(t)在(-∞,+∞)上非減;

(iii)Rμ(t)≤1-γ1,(?t<μ,γ1∈(0,1-ω)是一個(gè)常數(shù));

(iv)Rμ(μ)=1+γ2,(γ2∈(0,+∞)是一個(gè)常數(shù));

對(duì)于自動(dòng)調(diào)節(jié)信賴域半徑的R-函數(shù),本文定義為[6]

算法1

step0 給定x0∈Rn,對(duì)稱陣

step2 用折線法[9]求解子問(wèn)題(2)得近似解dk.

step4 若ρk≥μ,令xk+1=xk+dk;否則取λk為

(3)

令xk+1=xk+λkdk.

step6 令k∶=k+1,更新bk[3]和Bk[3]

若ρk≥μ,令Mk+1=M;若μ<ρk<1,Mk+1=M+1.轉(zhuǎn)step1.

2 算法的收斂性

2.1 本文假設(shè)

H1 水平集L(x0)={x|f(x)≤f(x0),x∈Rn}有界,且{xk}∈L(x0);

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

H3 ?f(x)在Rn上一致連續(xù)；

2.2 全局收斂性

引理1[8]若假設(shè)H2成立，則數(shù)列{fl(k)}非增且收斂.

(4)

(5)

取ε=τδ(1-μ)/2,其中0<μ<1,τ>0,則

(6)

令

m=min{Δ1,Z1,ε0δ,ωδ,ωδZ1,τδω(1-μ)/2},

下面分兩種情況證明(4)式.

(7)

(8)

(9)

f(xk+dk)-fl(k)>-μpredk.

(10)

由(6)式知

(11)

(12)

從而有

由(10)、(11)和(12)式有

(13)

而由引理2有

即

(14)

將(14)兩邊乘以(1-μ)加到(13),得到

(15)

根據(jù)m的取法

定理1 若假設(shè)H1-H5均成立，則由算法1產(chǎn)生的點(diǎn)列滿足

(16)

(17)

當(dāng)k∈J時(shí),

(18)

由(17)和(18)式知,存在常數(shù)ξ>0,對(duì)?k,有fl(k)-fk+1≥ξ/Zk,從而

在上面不等式兩邊取最大值,有

fl(k)≥max{fk+1,fk+2,…fk+M+1}+ω/Zk+M+1,?k,

又fl(k+M+1)≤max{fk+1,fk+2,…fk+M+1},?k,從而有

fl(k)-fl(k+M+1)≥ω/Zk+M+1,?k.

(19)

由引理1及(19)式得到

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

這與假設(shè)H4矛盾.證畢.

3 數(shù)值結(jié)果

本節(jié)數(shù)值試驗(yàn)選用三個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)如下

E1 Penalty-I function

這里α=10-5.

E2 Freudenstein-Rothfunction

f(x)=(-13+x1+((5-x2)x2-2)x2)2+(-29+x1+((x2+1)x2-14)x2)2.

E3 Rosenbrock function

在Matlab7.0環(huán)境下編制程序,參數(shù)設(shè)置如下

Δ0=1.5,μ=0.75,M=4,α=0.1,λ0=0.5,β=0.25,ε0=0.01,

B0=I,γ1=γ2=0.01,ω=0.1.

表1 算法1數(shù)值實(shí)驗(yàn)結(jié)果

數(shù)值結(jié)果表明,參數(shù)γ1和γ2的選取對(duì)算法1影響不大,從迭代次數(shù)和計(jì)算結(jié)果來(lái)看,該算法的計(jì)算效率比較高.表2的數(shù)值結(jié)果分析,在相同的終止條件下,采用相同的自適應(yīng)調(diào)節(jié)方法,針對(duì)非二次形態(tài)較強(qiáng)的函數(shù)，文獻(xiàn)[10]采用二次模型逼近原函數(shù)，結(jié)果顯示算法1的迭代次數(shù)要遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[10]算法的迭代次數(shù),計(jì)算結(jié)果也較為精確,大大減少了計(jì)算量.表3的數(shù)值結(jié)果分析，文獻(xiàn)[11]采用錐模型逼近原函數(shù),自適應(yīng)技術(shù)僅利用函數(shù)的梯度信息進(jìn)行調(diào)節(jié),相比較本文算法1的自適應(yīng)調(diào)節(jié)技術(shù)信息較少,數(shù)據(jù)顯示算法1在迭代次數(shù)上要小于文獻(xiàn)[11],說(shuō)明新算法是穩(wěn)定有效的.

表2 算法1和文獻(xiàn)[10]數(shù)值實(shí)驗(yàn)結(jié)果比較

表3 算法1和文獻(xiàn)[11]數(shù)值實(shí)驗(yàn)結(jié)果比較