解信賴域子問題的多折線算法

申理精 ，郭棟棟，王希云

(1.太原科技大學(xué) 應(yīng)科學(xué)院，太原 030024；2.山西應(yīng)用科技學(xué)院，太原 030024)

求解無約束優(yōu)化問題

(1)

的信賴域方法的基本思想是在當(dāng)前迭代點(diǎn)x(k)的附近用一個(gè)二次函數(shù)逼近目標(biāo)函數(shù)f，用該二次函數(shù)在x(k)的領(lǐng)域內(nèi)的極小值點(diǎn)作為下一個(gè)迭代點(diǎn)[1-4]，該二次函數(shù)為：

s.t.‖δ‖≤Δk

(2)

稱為信賴域子問題，其中δ=x-x(k)，Bk∈Rn×n是f在x(k)的Hessian陣或其近似，參數(shù)Δk>0，則

x(k+1)=x(k)+δ(k)

隨著參數(shù)Δ的變化，問題(2)的解δ*在空間留下一條曲線稱為最優(yōu)曲線[5-6]，Δ稱為信賴域半徑。

在Hessian陣正定的條件下，關(guān)于子問題(2)的求解，文獻(xiàn)[7-13]給出了不同的折線算法，文獻(xiàn)[14]構(gòu)造了雙割線折線算法，本文基于雙割線折線法構(gòu)造了多折線算法，通過幾何圖形，得到多折線算法比割線法求解子問題時(shí)更精確，分析了多折線算法的收斂性，通過數(shù)值試驗(yàn)與雙割線折線法[12]進(jìn)行比較知新算法更好。

1 折線的構(gòu)造

B正定時(shí)，最優(yōu)曲線方程為：

δk=-(B+μI)-1g，其中μ≥0

(3)

點(diǎn)δap的切線方向與δnp方向平行[14]，因點(diǎn)δap的切線方向δnp=-B-1g平行，

因此由

d/dμ[-(B+μI)-1g]=B-1g，

即

(B+μI)-1(B+μI)-1g=B-1g，

有Ig=(B+μI)2B-1g，兩邊左乘B，

δrp=

(4)

λi是B的特征值。

連接初始點(diǎn)θ，δrp，δap，δnp形成一條多折線路徑，在圖1中可見，新路徑記為Γ3=[θ，δrp，δap，δnp].

圖1 折線路徑圖

其中Γ1=[θ，δzp，δnp]是切線單折線[12]，Γ2=[θ，δap，δnp]是雙割線折線[14]，Γ3=[θ，δrp，δap，δnp]為本文算法路徑，從圖1可看出，本文所得的多折線法路徑更接近最優(yōu)曲線。

2 算法

步1：給定梯度g，正定陣B，Δ；

步3：計(jì)算δnp：δnp=-B-1g；

步4：Γ3=[θ，δrp，δap，δnp]；

步5：確定子問題(2)的解

當(dāng)‖δrp‖2≤Δ≤‖δap‖2，則

δk=δrp+η(δap-δrp)，其中η滿足‖δk‖2=Δ；

當(dāng)‖δap‖2≤Δ≤‖δnp‖2，則δk=δap+η(δnp-δap)，其中η滿足‖δk‖2=Δ；

當(dāng)Δ≥‖δnp‖2，則δk=δnp.

3 收斂性分析

定理1解子問題(2)時(shí)，多折線路徑滿足：

點(diǎn)x從點(diǎn)xk出發(fā)沿多折線路徑向前行進(jìn)時(shí)，

I：‖x-xk‖=‖δ(τ)‖2單調(diào)增；

II：函數(shù)值qk(δ(τ))嚴(yán)格單調(diào)減。

記多折線為δ(τ)，則：

(5)

要求δ(τ)滿足I和II.

證明：0≤τ≤1時(shí)，

II：記φ2(α)=qk(δ(α))，α∈(0，1)

當(dāng)‖B‖2<1時(shí)，

對(duì)B做譜分解：B=UΤΛU，令g=Uy，z=U2y，則：

當(dāng)‖B‖2≥1時(shí)，

1≤τ≤2時(shí)， I：記：

當(dāng)‖B‖2<1時(shí)，

對(duì)B做譜分解：B=UΤΛU，令g=Uy，

當(dāng)‖B‖2≥1時(shí)，

對(duì)B做譜分解：B=UΤΛU，令g=Uy，z=U2y，則：

II：記h2(α)=qk(δ(1+α))，α∈(0，1)

h2(α)=qk(δrp+α(δap-δrp))=

α(δap-δrp)ΤB(δap-δrp)≤

(δap-δrp)Τ(g+Bδrp)+(δap-δrp)ΤB(δap-δrp)=

當(dāng)‖B‖2<1時(shí)，

當(dāng)‖B‖2≥1時(shí)，

所以1≤τ≤2時(shí)，滿足I、II；

2≤τ≤3時(shí)，

當(dāng)‖B‖2<1時(shí)，

對(duì)B做譜分解：B=UΤΛU，令g=Uy，z=U2y，則：

當(dāng)‖B‖2≥1時(shí)，

對(duì)B做譜分解：B=UΤΛU，令g=Uy，z=U2y，則：

再證II：記h2(α)=qk(δ(2+α))，α∈(1，2)

h2(α)=qk(δap+α(δnp-δap))=

gΤδap+αgΤ(δnp-δap)+

α(δnp-δap)ΤB(δnp-δap)≤

(δnp-δap)Τ(g+Bδap)+

(δnp-δap)ΤB(δnp-δap)=

當(dāng)‖B‖2<1時(shí)，

=0

當(dāng)‖B‖2≥1時(shí)，

=0

所以當(dāng)2≤τ≤3時(shí)，滿足I、II；

綜上所述τ[0,3],δ(τ)滿足I、II，證畢。

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

采用測(cè)試函數(shù)1與測(cè)試函數(shù)2對(duì)多折線算法進(jìn)行數(shù)值試驗(yàn)[15-16]，同時(shí)與DSD算法[14]的數(shù)值結(jié)果進(jìn)行比較見表1與表2，表中的Δ為信賴域半徑，表中的qDSD-q本文算法指本文的多折線算法與DSD算法的最優(yōu)值差。

表1 測(cè)試函數(shù)1數(shù)值結(jié)果比較表

表2 測(cè)試函數(shù)2數(shù)值結(jié)果比較表

測(cè)試函數(shù)1：

s.t.‖δ‖2≤Δ

測(cè)試函數(shù)2：

s.t.‖δ‖2≤Δ

由表1與表2的數(shù)值結(jié)果比較可得出：本文構(gòu)造的多折線算法無論對(duì)測(cè)試函數(shù)1還是測(cè)試函數(shù)2當(dāng)信賴域半徑的取值小于10.2時(shí)其數(shù)值表現(xiàn)都優(yōu)于算法的數(shù)值表現(xiàn)，當(dāng)信賴域半徑取10.2與11時(shí)多折線算法與算法表現(xiàn)相當(dāng)。

因此針對(duì)信賴域子問題的求解，本文用多折線來逼近最優(yōu)曲線，無論是從幾何上分析還是從數(shù)值試驗(yàn)的表現(xiàn)上都說明本文算法是有效的。