王英慧，王希云

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

?

一種求解二次模型信賴(lài)域子問(wèn)題的Admas4隱式算法

王英慧，王希云

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

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

微分方程模型；信賴(lài)域子問(wèn)題；Adams4隱式算法

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

(1)

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

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

(2)

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

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

Admas4隱式公式如下：

(n=2,3,4,…)

(3)

其中：

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

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

(4)

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

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

則：

(5)

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

(6)

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

2 對(duì)步長(zhǎng)h的限定

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

(7)

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

定理1 設(shè)B對(duì)稱(chēng)正定，且當(dāng)n=0,1時(shí)有:

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

(8)

n=2,3,…時(shí)，有：

(9)

則δ(τ)滿(mǎn)足：

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

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

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

則：

由式(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)當(dāng)τ∈[μ0,μ1]，即τ∈[0,h0]時(shí):

則：

由已知條件式(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ù)。

對(duì)?τ∈[μi,μi+1]，即:

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

由已知條件(9)：

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

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

4 算法描述

通過(guò)上面的討論，下面給出Admas4隱式折線(xiàn)算法的具體步驟：

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

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

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

步3 選取適當(dāng)步長(zhǎng)，令:

其中μ0=0.令:

如果△≥‖δ1‖2，則?。?/p>

步4 令:

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

步5 根據(jù)公式:

根據(jù)公式：

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

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

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

5 Admas4隱式折線(xiàn)算法的適定性

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

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

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

6 數(shù)值實(shí)驗(yàn)

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

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

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

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

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

Function1：

s.t.‖δ‖2≤△.

Function2：

s.t.‖δ‖2≤△

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

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

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

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

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

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

[6] 李董輝，童曉嬌，萬(wàn)中.數(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

山西省高校‘131’項(xiàng)目基金

王英慧(1987-)女，碩士研究生，主要研究方向?yàn)樽顑?yōu)化理論與應(yīng)用。

1673-2057(2016)05-0406-06

O221

A

10.3969/j.issn.1673-2057.2016.04.014