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

王英慧，王希云

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

?

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

王英慧，王希云

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

摘要：針對(duì)最優(yōu)曲線(xiàn)的微分方程模型，在Hessian矩陣正定的前提下，采用Adams顯式二步公式構(gòu)造一條折線(xiàn)，稱(chēng)為Adams折線(xiàn)，用其代替最優(yōu)曲線(xiàn)，提出求解子問(wèn)題的新算法——Adams算法。通過(guò)數(shù)值試驗(yàn)，表明Adams二步算法比切線(xiàn)單折線(xiàn)法具有明顯的優(yōu)勢(shì)。

關(guān)鍵詞：微分方程模型；信賴(lài)域子問(wèn)題；Adams算法

信賴(lài)域方法實(shí)現(xiàn)的關(guān)鍵是每步迭代時(shí)要求解一個(gè)二次模型信賴(lài)域子問(wèn)題，其形式如下：

s.t.‖δ‖2≤△

(1)

(1)中的各個(gè)參數(shù)表示的含義分別是：g∈Rn：目標(biāo)函數(shù)在當(dāng)前點(diǎn)的梯度(graidient)，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ì)于子問(wèn)題(1)的求解，目前提出的方法主要有單折線(xiàn)法、雙折線(xiàn)法、切線(xiàn)單折線(xiàn)法以及基于最優(yōu)曲線(xiàn)微分方程模型的歐拉算法。本文主要討論在微分方程模型基礎(chǔ)上的解決子問(wèn)題(1)的算法。針對(duì)最優(yōu)曲線(xiàn)的參數(shù)方程，在Hessian矩陣正定的前提下，文獻(xiàn)[1]中提出了一種微分方程模型，形式如下：

(2)

利用這個(gè)微分方程模型，文獻(xiàn)[2-4]分別提出了求解二次模型信賴(lài)域子問(wèn)題的歐拉算法和休恩算法，并取得了較好的實(shí)驗(yàn)結(jié)果。

1Adams折線(xiàn)法的思想及其構(gòu)造

根據(jù)微分方程模型(2)，采用Adams顯式二步公式[5]構(gòu)造折線(xiàn)Γ，用Γ代替最優(yōu)曲線(xiàn)來(lái)求解信賴(lài)域子問(wèn)題(1)，提出求解子問(wèn)題的新算法——Adams算法。在理論上給予了該算法的證明，并且通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性。

Adams顯式二步公式如下：

(3)

其中：fn=-(B+μnI)-1δn，fn-1=-(B+μn-1I)-1δn-1，μn=nh.

(4)

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

(5)

2折線(xiàn)性質(zhì)分析

定理1設(shè)B對(duì)稱(chēng)正定，且有：n=1,2,3,L,N-1時(shí)，下式成立。

(6)

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

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

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

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

則:

因?yàn)橛墒?5)可得:

所以：

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

對(duì)?τ∈(μi,μi+1)，即(τ-μi)∈(0,h),i=1,2,3,…,N-1時(shí):

則:

因?yàn)橛墒?5)可得:

所以：

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

(2)當(dāng)τ∈[μ0,μ1]，即τ∈[0,h]時(shí):

則:

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

對(duì)?τ∈(μi,μi+1)，即(τ-μi)∈(0,h),i=1,2,3,…,N-1時(shí)：

[(3fi-fi-1)TB(3fi-fi-1)]

則:

由式(6)，得：

(q[δ(τ)])≥0,τ∈(μi,μi+1)

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

3算法描述

步1：已知目標(biāo)函數(shù)在當(dāng)前迭代點(diǎn)的梯度是g，正定矩陣是B和信賴(lài)域半徑△.

步2：令δ0=-B-1g，若△≥‖δ0‖2,則終止計(jì)算，得子問(wèn)題的解δ*=δ0，否則，轉(zhuǎn)步3.

4數(shù)值試驗(yàn)

對(duì)于附錄中給定的的測(cè)試函數(shù)Funtion1和Funtion2對(duì)應(yīng)的子問(wèn)題(1)，取固定步長(zhǎng)h=0.5，選取不同的信賴(lài)域半徑△，利用MATLAB對(duì)Adams算法進(jìn)行了數(shù)值實(shí)驗(yàn)，并將此實(shí)驗(yàn)結(jié)果與文獻(xiàn)[7-8]中提出的切線(xiàn)單折線(xiàn)法的實(shí)驗(yàn)結(jié)果做了比較，結(jié)果見(jiàn)表1和表2.

通過(guò)觀(guān)察表1和表2，發(fā)現(xiàn)：對(duì)于不同的信賴(lài)域半徑，不管對(duì)Funtion1還是對(duì)Funtion2，都有q1-q2≤0，即：在靠近最優(yōu)曲線(xiàn)的程度上，Adams折線(xiàn)表現(xiàn)的更好。對(duì)于Funtion1，當(dāng)信賴(lài)域半徑△落在‖δzp‖2附近時(shí)，Adams算法求得的近似最優(yōu)解比切線(xiàn)單折線(xiàn)法明顯要好；對(duì)于Funtion2，Adams算法求得的近似最優(yōu)解也比切線(xiàn)單折線(xiàn)法要好，特別地，當(dāng)信賴(lài)域半徑△落在‖δzp‖2附近時(shí)，Adams算法求得的近似最優(yōu)解比切線(xiàn)單折線(xiàn)法明顯要好。當(dāng)信賴(lài)域半徑△≥‖B-1g‖2時(shí)，兩種算法的實(shí)驗(yàn)結(jié)果一樣。因此，本論文所構(gòu)造的Adams算法也是一種有效的求解二次模型信賴(lài)域子問(wèn)題(1)的折線(xiàn)法。對(duì)于測(cè)試函數(shù)1，‖δzp‖2=2.99，‖B-1g‖2=15.34.對(duì)于測(cè)試函數(shù)2，‖δzp‖2=3.64，‖B-1g‖2=11.00.

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

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

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

Funtion1:

Funtion2:

參考文獻(xiàn)：

[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.

[7]趙英良，徐成賢.解決信賴(lài)域子問(wèn)題的切線(xiàn)單折線(xiàn)法[J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，2000，21(1)：77-80.

[8]任玉杰.數(shù)值分析及其MATLAB實(shí)現(xiàn)[M].北京：高等教育出版社，2007.

Adams′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)

Abstract：In the premise of Hessian matrix as a positive definite matrix，a broken line was constructed by Adams′method according to differential equation model in literature.Meanwhile，an Adams′algorithm for solving trust-region subproblems with quadratic model was presented by using the broken line instead of the optimal curve.Through comparison with tangent single dogleg method，the results of numerical experiments indicate that the new algorithm has obvious advantage over the tangent single dogleg method.

Key words：differential equation model，trust-region subproblems，Adams method

中圖分類(lèi)號(hào)：O221

文獻(xiàn)標(biāo)志碼：A

doi：10.3969/j.issn.1673-2057.2016.01.016

文章編號(hào)：1673-2057(2016)01-072-05

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

基金項(xiàng)目：山西省自然科學(xué)基金(2008011013)；山西省 ‘131’領(lǐng)軍人才工程項(xiàng)目

收稿日期：2015-04-02