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

張春霞,王希云

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

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

minf(x),x∈Rn.

(1)

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

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

(2)

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

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

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

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

(3)

算法步長(zhǎng)簡(jiǎn)化為:

(4)

hn=

(5)

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

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

1 算法

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

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

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

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

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

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

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

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

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

又由式(4)可得:

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

因?yàn)?/p>

假設(shè)1

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

又由：

可得:

則：

且：

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

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

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

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

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

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

則:

因?yàn)?

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

則:

由式(5)可知：

所以

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

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

則:

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

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

則:

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

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

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

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

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

表2 Function 1的運(yùn)行結(jié)果Tab.2 The running of Function 1

表3 測(cè)試函數(shù)2的數(shù)值結(jié)果Tab.3 Numerical results of test Function 2

表4 Function 2的運(yùn)行結(jié)果Tab.4 The running of Function 2

ΔFunction 2tntCHtICHtCH-tICHnCHnICH80.071240.060700.0105402290.061130.059260.00187100100.061130.052670.00846000110.052530.038150.01438000

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

Function 1

s.t.‖δ‖2≤Δ.

Function 2

s.t.‖δ‖2≤Δ.