求解信賴域子問題的改進(jìn)變步長休恩算法

2019-11-18 03:41:24張春霞王希云

太原科技大學(xué)學(xué)報 2019年6期

關(guān)鍵詞：測試函數(shù)折線信賴

張春霞,王希云

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

無約束最優(yōu)化[1]問題如下:

minf(x),x∈Rn.

(1)

其中f(x):Rn→R是目標(biāo)函數(shù),x∈Rn是待求變量。

信賴域方法是在非線性優(yōu)化問題[2]中備受關(guān)注的一類算法。當(dāng)用信賴域方法求解無約束最優(yōu)化問題時,關(guān)鍵在于每步迭代時都需求解下面形式的二次模型[3]信賴域子問題:

(2)

當(dāng)Δ變化時,上述二次模型信賴域子問題的解δ*形成一條空間曲線,稱為最優(yōu)曲線[4]。

目前求解信賴域子問題的算法很多,當(dāng)Hessian正定時,折線法相對好些。常用的方法有單折線[5]、雙折線[6]、切線單折線[7]等。

2015年王希云、于海波提出了一類R-K類算法[8],一種變步長的休恩算法(CH)[9]。R-K類算法的基本思想是利用R-K類方法構(gòu)造一條折線進(jìn)而代替最優(yōu)曲線來求解信賴域子問題。2017年王希云、賈新輝提出了改進(jìn)的顯示歐拉、隱式歐拉、平均歐拉[10-11]求解信賴域子問題。本文在于海波和王希云提出的變步長休恩方法的基礎(chǔ)上,改進(jìn)了繁瑣的步長形式,提出了一種改進(jìn)的變步長休恩算法(ICH)。

本文為簡化步長形式,將文獻(xiàn)[9]的假設(shè)條件修正為:

(3)

算法步長簡化為:

(4)

hn=

(5)

其中n=0,1,2,l,N-1,δ0=-B-1g,ε稱為限制步長,即限制每步步長的最大值只能達(dá)到ε.限制步長ε越小。

數(shù)值實驗表明改進(jìn)后算法的迭代次數(shù)更少、計算時間更短。

1 算法

下面給出我們改進(jìn)的變步長休恩算法的具體步驟:

步1 給定梯度g,正定矩陣B,信賴域半徑Δ.

步2 令δ0=δnp-B-1g,如果‖δ2‖2≤Δ,則取δ*=δ0.停止計算,否則轉(zhuǎn)步3.

停止計算,否則令n:=n+1,轉(zhuǎn)步5.

2 改進(jìn)的變步長休恩折線路徑的性質(zhì)分析

① 當(dāng)n=0,1,2,…,N-1時,則:

② 當(dāng)n=0,1,2,…,N-1時,則:

證明①當(dāng)n=0,1,2,…,N-1時,

(B+μn+1I)-1δn

又由式(4)可得:

證明② 當(dāng)n=1時：

因為

假設(shè)1

則當(dāng)n=k+1時:

又由：

可得:

則：

且：

故由第二數(shù)學(xué)歸納法可知原命題成立。

定理設(shè)B對稱正定,且當(dāng)n=0,1,2,…,N-1時有下式成立,

則δ(τ)滿足如下要求:

①‖δ(τ)‖2關(guān)于τ為單調(diào)非增函數(shù);

②q[δ(τ)]關(guān)于τ為單調(diào)非減函數(shù)。

證明:① 當(dāng)τ∈[β0,β1],即τ∈[0,h0]時

則:

因為:

故‖δ(τ)‖2在區(qū)間τ∈[β0,β1]上為單調(diào)非增函數(shù)。對?τ∈[βi,βi-1],即:(τ-βi)∈(0,hi),n=0,1,2,…,N-1時:

則:

由式(5)可知：

所以

故‖δ(τ)‖2在區(qū)間(βi,βi+1),n=0,1,2,…,N-1上都為單調(diào)非增函數(shù)。

② 當(dāng)τ∈[β0,β1],即τ∈(0,h0)時：

則:

所以q[δ(τ)]在區(qū)間[β0,β1]上為單調(diào)非減函數(shù)。

對?τ∈[βi,βi-1],即(τ-βi)∈(0,hi),n=0,1,2,…,N-1時：

則:

故q[δ(τ)]在區(qū)間[βi,βi+1],n=0,1,2,…,N-1上都為單調(diào)非減函數(shù)。

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

改進(jìn)的變步長休恩算法與改進(jìn)前算法做對比,t表示求解子問題所用的時間,n表示迭代次數(shù),q表示測試函數(shù)的最優(yōu)解的函數(shù)值。

對于測試函數(shù)Function1,數(shù)值實驗結(jié)果[12]如表1和表2所示，當(dāng)信賴域半徑較小時,本文提出的改進(jìn)的休恩三階算法要比原算法的計算速度快,迭代次數(shù)少,且在計算結(jié)果的精度上與之相近。對于測試函數(shù)Function1,當(dāng)信賴域半徑0.5≤Δ≤10時,改進(jìn)的變步長休恩算法求得的信賴域子問題的最優(yōu)值要比原算法的好,當(dāng)Δ接近‖δnp‖2時,兩種方法求得的結(jié)果一樣。對于測試函數(shù)Function2,數(shù)值實驗結(jié)果[12]如表3和表4所示,當(dāng)信賴域半徑0.5≤Δ≤8時,改進(jìn)的變步長休恩算法求得的信賴域子問題的最優(yōu)值要比原算法的好,當(dāng)Δ接近‖δnp‖2時,兩種方法求得的結(jié)果一樣。因此本文提出的改進(jìn)的休恩三階算法可以很好的近似最優(yōu)曲線,且比原算法的迭代次數(shù)少,計算時間短,是有效可行的。