一種求解二次模型信賴域子問題的Admas4隱式算法

王英慧，王希云

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

?

一種求解二次模型信賴域子問題的Admas4隱式算法

王英慧，王希云

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

基于信賴域子問題最優(yōu)曲線的微分方程模型，在Hessian矩陣正定及步長固定的前提下，采用求解微分方程的Admas4隱式公式構(gòu)造了一條折線，稱Admas4隱式折線，用其代替最優(yōu)曲線，提出求解子問題的新算法—Admas4隱式算法。數(shù)值結(jié)果表明Admas4隱式算法比R-K4算法效果好。

微分方程模型；信賴域子問題；Adams4隱式算法

在非線性優(yōu)化中，信賴域方法不僅具有很好的可靠性和強適性，而且具有較強的收斂性。因而，自其出現(xiàn)起就受到高度重視，成為熱點。信賴域方法實現(xiàn)的關(guān)鍵是每步迭代時要求解一個二次模型信賴域子問題，其形式如下：

(1)

(1)中的各個參數(shù)表示的含義分別是：g∈Rn：目標函數(shù)在當前點的梯度，B∈Rn×n：目標函數(shù)在當前點處的Hessian矩陣或者它的近似矩陣，△∈R：信賴域半徑，δ∈Rn：要求的變量。當△發(fā)生變化時，子問題(1)的解δ*在空間形成一條曲線——最優(yōu)曲線。

針對最優(yōu)曲線的參數(shù)方程，在Hessian矩陣正定的前提下，有如下微分方程模型[1]：

(2)

對于子問題(1)的求解，目前提出的方法主要有單折線法、雙折線法、切線單折線法。后來李亮提出最優(yōu)曲線的微分方程模型之后，基于此微分方程模型，先后提出了解決信賴域子問題的隱式分段折線法、分段切線法、平均歐拉算法及休恩算法[1-4]。后來又提出了解二次模型子問題的R-K4算法。該算法主要是利用解微分方程模型的R-K4公式，構(gòu)造一條R-K4折線，進而用此折線代替最優(yōu)曲線來求解子問題(1)的解。為進一步提高數(shù)值計算結(jié)果的精度，本文結(jié)合求解微分方程的較高階的Admas4隱式公式[5]，構(gòu)造了Admas4折線代替最優(yōu)曲線來求解子問題(1)，并將數(shù)值結(jié)果與R-K4方法做了比較。

1 Adams4隱式折線的構(gòu)造

Admas4隱式公式如下：

(n=2,3,4,…)

(3)

其中：

μn=μ0+nh.具體構(gòu)造如下：

第一步：從初始點P0(μ0,δ0)開始，其中μ0=0，δ0=-B-1g.選取步長，用公式:

(4)

第二步：由常用的四階龍格-庫塔公式:

若記：f01=-(B+μ0I)-1δ0,

則：

(5)

計算出δ1，得出下一個節(jié)點P1(μ1,δ1)，其中μ1=μ0+h.同理計算出δ2，得到節(jié)點P2(μ2,δ2).

(6)

其中μ0=0，μn=μn-1+h,n=1,2,3,…,N.

2 對步長h的限定

為了使構(gòu)造的折線滿足引理6.4.1[6]，則步長需要滿足下式:

(7)

3 Admas4隱式折線路徑的性質(zhì)定理

定理1 設(shè)B對稱正定，且當n=0,1時有:

gT[fn1+2fn2+2fn3+fn4]+

(8)

n=2,3,…時，有：

(9)

則δ(τ)滿足：

(1)‖δ(τ)‖2關(guān)于τ為單調(diào)減函數(shù)。

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

證明：(1)當τ∈[μ0,μ1]，即τ∈[0,h0]時:

則：

由式(7)得：

因此，‖δ(τ)‖2在區(qū)間[μ0,μ1]，[μ1,μ2]上為單調(diào)減函數(shù)。

則：

由式(7)得：

因此‖δ(τ)‖2在區(qū)間[μi,μi+1],i=1,2,3，…,N-1上為單調(diào)減函數(shù)。

(2)當τ∈[μ0,μ1]，即τ∈[0,h0]時:

則：

由已知條件式(8)：

gT[f01+2f02+2f03+f04]+

得：(q[δ(τ)])′≥0,τ∈[μ0,μ1].

同上，可以證明(q[δ(τ)])′≥0,τ∈[μ1,μ2].

所以q[δ(τ)]在區(qū)間[μ0,μ1]，[μ1,μ2]上關(guān)于τ為單調(diào)增函數(shù)。

對?τ∈[μi,μi+1]，即:

(τ-μi)∈(0,hi),i=1,2,3,…,N-1時：

由已知條件(9)：

可得：(q[δ(τ)])′≥0,τ∈[μi,μi+1].

所以：q[δ(τ)]在區(qū)間[μi,μi+1]，i=0,1,2,3,…,N-1上關(guān)于τ為單調(diào)增函數(shù)。(證畢)。

4 算法描述

通過上面的討論，下面給出Admas4隱式折線算法的具體步驟：

步0 給定梯度g，正定矩陣B，信賴域半徑△.令n∶=0.

步1 令δ0=-B-1g.

步2 如果△≥‖δ0‖2，則取δ*=δ0，停止計算。否則，令n∶=n+1，轉(zhuǎn)步3.

步3 選取適當步長，令:

其中μ0=0.令:

如果△≥‖δ1‖2，則取：

步4 令:

如果△≥‖δ2‖2，則取:

步5 根據(jù)公式:

根據(jù)公式：

計算δn+1，轉(zhuǎn)步6.

步6 如果△≥‖δn+1‖2，則取:

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

5 Admas4隱式折線算法的適定性

由定理1可知下列結(jié)論成立：

定理2 設(shè)B對稱正定，在Admas4隱式算法中，對任意給定的信賴域半徑△<‖B-1g‖2，則存在自然數(shù)N使得‖δN‖2≤△.

定理1和定理2說明對任意給定的信賴域半徑△，在Admas4隱式折線δ(τ)上的近似解存在且唯一。并且用Admas4隱式算法求信賴域子問題(2)的最優(yōu)解時，最優(yōu)解δ*在信賴域邊界上取得。

6 數(shù)值實驗

對于附錄中給定的測試函數(shù)1和測試函數(shù)2的信賴域子問題(1)，取h=0.1，選取不同的信賴域半徑△，然后將Admas4隱式算法利用MATLAB進行了數(shù)值實驗。并且用該算法求得的測試函數(shù)在近似最優(yōu)解的函數(shù)值與R-K4方法進行比較，數(shù)值結(jié)果分別列在表1和表2中。

表1 測試函數(shù)1的數(shù)值結(jié)果

從表1和表2的數(shù)值結(jié)果可以看出，本論文所提出的Admas4隱式算法是有效且可行的。對于測試函數(shù)1和測試函數(shù)2，當信賴域半徑△<‖B-1g‖2時，除了信賴域半徑在‖B-1g‖2附近的情況，Admas4隱式算法求得的測試函數(shù)在近似最優(yōu)解的函數(shù)值比R-K4效果要好；當信賴域半徑△≥‖B-1g‖2時，則Admas4隱式算法與R-K4算法所求得的測試函數(shù)在近似最優(yōu)解的函數(shù)值相同。因此，本論文所構(gòu)造的Admas4隱式算法比R-K4算法更好地近似了最優(yōu)曲線，而且Admas4隱式算法也是一個很好的求解信賴域子問題(1)的折線法。

對于測試函數(shù)1，‖B-1g‖2=15.34.對于測試函數(shù)2，‖B-1g‖2=10.01.

附錄：測試函數(shù)

Function1：

s.t.‖δ‖2≤△.

Function2：

s.t.‖δ‖2≤△

表2 測試函數(shù)2的數(shù)值結(jié)果

[1] 王希云，李亮，于海波.解決信賴域子問題的隱式分段折線算法[J].應(yīng)用數(shù)學(xué)和力學(xué)，2014，35(6)：610-619.

[2] 王希云，李亮，張雅琦，等.一種求解二次函數(shù)模型信賴域子問題的分段切線法[J].應(yīng)用數(shù)學(xué)，2015，28(1)：26-32.

[3] 朱帥，李亮，王希云.一種求解二次模型信賴域子問題的新算法[J].西南民族大學(xué)學(xué)報，2014，40(1)：91-96.

[4] 李亮，王希云，張雅琦，等.一種求解二次模型信賴域子問題的休恩算法[J].太原科技大學(xué)學(xué)報，2014，35(2)：151-155.

[5] 林成森.數(shù)值計算方法[M].北京：科學(xué)出版社，2005.

[6] 李董輝，童曉嬌，萬中.數(shù)值最優(yōu)化算法與理論[M].北京：科學(xué)出版社，2010.

An implied Adams4′s Algorithm for Solving Trust-region Subproblems with Quadratic Model

WANG Ying-hui，WANG Xi-yun

(School of Applied Science，Taiyuan University of Science and Technology，Taiyuan 030024，China)

In the premise of Hessian matrix as a positive definite matrix and fixed step，a broken line is constructed by implied Adams4′s method according to the differential equation model，which is defined as Admas4 implicit broken line instead of the optimal curve.Through the comparison with the R-K4 method，the results indicate that Adams4 implicit algorithm has obvious advantage over the R-K4 method.

differential equation model，trust-region subproblems，implied Adams4′s method

2015-09-23

山西省高?！?31’項目基金

王英慧(1987-)女，碩士研究生，主要研究方向為最優(yōu)化理論與應(yīng)用。

1673-2057(2016)05-0406-06

O221

A

10.3969/j.issn.1673-2057.2016.04.014