一種基于模擬退火思想的錐模型信賴(lài)域方法

楊月婷，王宏博，周?chē)?，?蓉，曹名圓

(北華大學(xué)數學(xué)與統計學(xué)院，吉林 吉林 132013)

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

(1)

其中f(x)：n→是連續可微函數.信賴(lài)域方法是求解問(wèn)題(1)的有效方法之一[1-3]，其基本思想為在信賴(lài)域內求解近似子問(wèn)題的極小點(diǎn)，以便尋找使得函數值下降的新迭代點(diǎn).該過(guò)程一般借助二次函數構造信賴(lài)域子問(wèn)題，但是，在目標函數具有高度非二次性或曲率變化劇烈時(shí)，其逼近效果較差[4].因此，許多學(xué)者致力于研究基于錐模型的信賴(lài)域方法[5-7].

ZHAO等[5]充分利用前一次迭代點(diǎn)和當前迭代點(diǎn)的信息，采用新的自適應策略調整信賴(lài)域半徑，提出基于簡(jiǎn)化錐模型的非單調自適應信賴(lài)域方法.該算法具有局部的超線(xiàn)性收斂速度，且更適用于大規模問(wèn)題.LI等[6]提出新的非單調信賴(lài)域Barzilai-Borwein(BB)方法.該方法利用標量矩陣近似信賴(lài)域子問(wèn)題中目標函數的Hessian陣，其中標量矩陣的系數為BB方法步長(cháng)的倒數，基于改進(jìn)的Metropolis準則更新迭代點(diǎn).該方法可以顯著(zhù)減少迭代次數并提高算法的收斂速度.

受文獻[5-6]啟發(fā)，本文利用牛頓插值多項式構造簡(jiǎn)化錐模型，基于模擬退火思想改進(jìn)的Metropolis準則更新迭代點(diǎn)，提出基于模擬退火的錐模型信賴(lài)域方法.證明了新算法的全局收斂性，并給出數值結果驗證算法的有效性.

考慮錐模型信賴(lài)域子問(wèn)題

(2)

其中fk=f(xk)，gk=g(xk)，Bk∈n×n是函數f(x)在當前迭代點(diǎn)xk處的Hessian陣或Hessian陣的近似，s是試探步，Δk>0是信賴(lài)域半徑，bk∈n是水平向量.水平向量的取法很多，本文采用較經(jīng)典的取法[8]，即

(3)

我們用γkI(γk>0)近似Bk，得到式(2)的簡(jiǎn)化錐模型信賴(lài)域子問(wèn)題

(4)

為了確定參數γk，利用插值條件

ψ(k)(xk-1)=fk-1， ?ψ(k)(xk-1)=gk-1.

(5)

令sk-1=xk-xk-1，由式(5)得

(6)

(7)

以確保γkI的正定性.

經(jīng)典信賴(lài)域方法通過(guò)實(shí)際下降量與預測下降量的比值

(8)

來(lái)決定是否接受試探步以及如何調整信賴(lài)域半徑.為了接受更多的試探步，提高算法的效率，本文引入帶有溫度的Metropolis準則[6]

(9)

來(lái)決定是否接受試探步，其中Tk是第k次迭代時(shí)的溫度，0<τ<1是足夠小的實(shí)數.通過(guò)冷卻技術(shù)，當k→∞時(shí)，溫度Tk下降到0.將Metropolis準則嵌入到信賴(lài)域準則，使用pk與rk相結合，判斷算法是否進(jìn)行迭代.與經(jīng)典信賴(lài)域算法不同的是，當rk≤τ時(shí)，使用Metropolis準則以一定的概率接受更多的迭代，從而減少計算量，提高算法的收斂速度.

基于以上分析，我們給出基于模擬退火的錐模型信賴(lài)域算法(Conic model trust region method based on idea of simulated annealing，SACTR).

SACTR算法

步1 給定x0∈n，ε>0，Δ0>0，T0>0，v>1，0<β<1，00，γ0=1，b0∈n.令k0.

步3 求解信賴(lài)域子問(wèn)題(4)，得到試探步sk.

步4 通過(guò)式(8)和式(9)分別計算rk和pk.令

(10)

步5 更新信賴(lài)域半徑

(11)

步6 由式(6)或式(7)計算γk+1.如果γk+1≤κ或γk+1≥1/κ，則γk+1=θ.

(12)

為證明SACTR算法的全局收斂性，給出如下假設條件：

(H2)函數f：n→在水平集L(x)上連續可微，且?f(x)滿(mǎn)足Lipschitz連續條件，則存在正常數MH，使得

(H3)假設存在兩個(gè)正常數Δmax和Mb，使得

.

(13)

(14)

(15)

(16)

(17)

(18)

且sk是子問(wèn)題(4)的解，所以有

因此

證畢.

引理2假設(H3)成立，序列{xk}由SACTR算法生成，則存在一個(gè)充分大的N>0，當?k>N時(shí)，有

證明：由SACTR算法步4可知，如果rk≥τ>0，則pk=1>lk.由引理1得

(19)

(20)

綜上，引理得證.證畢.

引理3假設(H2)成立，序列{xk}由SACTR算法生成.如果xk不是問(wèn)題的解，即g(xk)≠0，則pk≤lk的迭代必為有限次.

(21)

由Δk+1=η1Δk，得

和

結合SACTR算法步6，可得序列{γk}是一致有界的，即

(22)

(23)

根據二階泰勒展開(kāi)以及式(22)和式(23)，可得

|[f(xk)-f(xk+sk)]-[ψ(k)(xk)-ψ(k)(xk+sk)]|=

其中ζk∈(0，1).因為k充分大，從式(22)和引理1，有

(24)

取K=max{K1，K2}，當k>K時(shí)，式(21)和式(24)同時(shí)成立，矛盾.證畢.

定理1假設(H1)成立，序列{xk}由SACTR算法生成，則

(25)

證明：若SACTR算法在有限步終止，那么結論顯然成立.

考慮無(wú)限多次成功的迭代.根據假設(H1)可知f(xk)有界，即存在a∈，使得對?k，都有f(xk)≥a.由引理2得

(26)

對式(26)的k產(chǎn)生增量

(27)

注意到，對?K>0，有fN+K+1>a.對式(27)取K→∞的極限，得

即式(25)成立.證畢.

因為Metropolis準則以一定的概率接受更多的試探步，我們通過(guò)多次運行算法得到的平均迭代次數和平均CPU運行時(shí)間來(lái)表明算法效率.為了更清晰的展示算法的數值效果，采用Dolan等[9]性能圖對算法的迭代次數和CPU運行時(shí)間進(jìn)行評估.我們以CPU運行時(shí)間為例，在性能圖中橫坐標τ表示最佳比值因子，縱坐標ψ=ρν(τ)表示某算法在運行時(shí)間與所有算法中最少運行時(shí)間的比值不超過(guò)τ時(shí)所求解問(wèn)題個(gè)數占問(wèn)題總數的比率，它反映了所測算法在運行時(shí)間方面的性能.因此，本文對SACTR算法、SAQTR算法及SATRBB算法，以τ為橫坐標、ρν(τ)為縱坐標作圖，圖中曲線(xiàn)越高表明算法的數值性能越好.三個(gè)算法的性能評估結果如圖1所示.

圖1算法性能對比Fig.1Comparison of algorithm performance

從圖1 a中可以看出，在迭代次數方面，SACTR算法的性能曲線(xiàn)整體趨勢優(yōu)于SATRBB、SAQTR的曲線(xiàn)趨勢，表明SACTR算法在求解無(wú)約束優(yōu)化問(wèn)題時(shí)能夠使用更少的迭代次數，求解效率更高；
圖1 b表明SACTR算法在CPU時(shí)間上也優(yōu)于SATRBB和SAQTR算法.

本文提出了求解無(wú)約束優(yōu)化問(wèn)題的基于模擬退火的錐模型信賴(lài)域方法，在適當假設條件下，證明了算法的全局收斂性.數值結果表明，SACTR算法無(wú)論是在迭代次數，還是在CPU時(shí)間上都是有競爭力的，特別是對于非二次型的函數.