王英慧，王希云

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

?

一種求解二次模型信賴域子問題的Adams方法

王英慧，王希云

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

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

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

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

s.t.‖δ‖2≤△

(1)

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

對于子問題(1)的求解，目前提出的方法主要有單折線法、雙折線法、切線單折線法以及基于最優(yōu)曲線微分方程模型的歐拉算法。本文主要討論在微分方程模型基礎(chǔ)上的解決子問題(1)的算法。針對最優(yōu)曲線的參數(shù)方程，在Hessian矩陣正定的前提下，文獻[1]中提出了一種微分方程模型，形式如下：

(2)

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

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

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

Adams顯式二步公式如下：

(3)

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

(4)

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

(5)

2折線性質(zhì)分析

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

(6)

則δ(τ)滿足：

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

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

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

則:

因為由式(5)可得:

所以：

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

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

則:

因為由式(5)可得:

所以：

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

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

則:

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

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

[(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：已知目標函數(shù)在當前迭代點的梯度是g，正定矩陣是B和信賴域半徑△.

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

4數(shù)值試驗

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

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

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

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

附錄：測試函數(shù)

Funtion1:

Funtion2:

參考文獻：

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

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

[8]任玉杰.數(shù)值分析及其MATLAB實現(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

中圖分類號：O221

文獻標志碼：A

doi：10.3969/j.issn.1673-2057.2016.01.016

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

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

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

收稿日期：2015-04-02