解不定信賴域子問題的Heun三階算法

董建新，李琳俊，王希云

1.長治學院數(shù)學系，山西長治046011

2.太原科技大學應用科學學院，太原030024

解不定信賴域子問題的Heun三階算法

董建新1，李琳俊2，王希云2

1.長治學院數(shù)學系，山西長治046011

2.太原科技大學應用科學學院，太原030024

1 引言

無約束優(yōu)化問題為：

其中f:Rn→R為二次連續(xù)可微函數(shù)。

求解無約束優(yōu)化問題時，通常先選擇二次函數(shù)作為目標函數(shù)的近似，然后用信賴域方法[1-2]求解該子問題，即：

式中，gk∈Rn為當前迭代點x()k處目標函數(shù)的梯度，是f(x)在的Hessian矩陣或者是此矩陣的近似形式。

隨著信賴域半徑Δk的連續(xù)變化，子問題的解δ*就形成空間中的一條曲線，即為最優(yōu)曲線。最優(yōu)解曲線的參數(shù)方程[3]為：

對式（3）兩邊求導，可確定微分方程模型：

對微分方程模型，可以用求解方程的相關方法構造各種合理的折線近似最優(yōu)曲線，從而求出子問題的解。這種思想結合了微分方程現(xiàn)有的求解方法和子問題的實際情況，提出了很多有效算法[4-7]，得到很好的應用。當子問題中的Hessian矩陣正定時，有各種效果更好的折線算法，比如常用單折線法[8]、雙折線法[9]，不定折線法[10-12]，隱式分段折線法[13]、歐拉切線法[14]等；然而對

Hessian矩陣不定時的求解方法討論較少。本文參考文獻[15-16]，結合Heun三階方法[17-18]，利用Bunch-Parlett法[3]，對B為不定矩陣的情況進行修正，構造了對稱正定矩陣，將不定子問題轉化為正定子問題，用新的折線來逼近最優(yōu)解曲線，從而給出了求解不定信賴域子問題的Heun三階算法。

2 Heun三階折線的構造

根據(jù)Heun三階公式，依次計算P0(μ0,δ0),P1(μ1,δ1),…,PN(μN,δN)，連接后便可以得到Heun三階折線：T=記Heun三階折線為具體形式如下：

步長h0見式（6）。

且：

3 算法描述

下面給出Heun三階算法的具體步驟，其中的步長選取見步驟后的注。

算法步驟：

輸入?yún)?shù)梯度g，不定矩陣B，信賴域半徑Δ。?。簄:=0。

步驟1將不定矩陣B進行Bunch-Parlett分解，有B=LDLT成立，結合矩陣D的特征值情況構造對稱且正定的矩陣G，并取B=G-1。

步驟2令δ0=δnp=-B-1g，若，則?。害?=δ0，停止計算。否則轉步驟3。

步驟3令：

且μ0=0，步長見式（5），轉步驟4。

步驟4令：

停止計算。否則令：n:=1，轉步驟5。

步驟5令：

步驟6令：

步長hn見式（8）。

步驟7輸出解δ*。

注：算法中步長選取策略如下：

其中：δ0=-B-1g，ε為限制步長，即每一次搜索時可以取到的最大步長為ε，ε越小，求得的最優(yōu)解δ*越精確。

4 Heun三階折線路徑性質分析

類似歐拉切線路徑性質分析[7]，下面給出Heun三階折線路徑的性質分析。

引理1對任意不定矩陣B，在n=1,2,3,…,N-1時，有：成立。

證明用第二類數(shù)學歸納法來證明。

（1）當n=1時：

由式（8）知：

（2）假設1＜n≤k時，結論成立；當n=k+1時，有：

①當

時，有：

根據(jù)式（8）可得：

②當

時，根據(jù)式（8）可以得到：

由（1）、（2）得，引理1成立。證畢。

定理1假設B為不定矩陣，且有下式成立：

證明（1）①當即τ∈[]0,h0時，有：

則

由式（6）：

根據(jù)式（8）：

由①、②得：結論（1）成立。

綜上，由①、②得，結論（2）成立。證畢。

5 算法的適定性

定理1中的結論（1）說明折線上的近似解是惟一的，結論（2）說明所求出的近似解滿足下降條件，由此可保證信賴域算法的全局收斂性，從而得到下面結論。

定理2假設Hessian陣B為不定矩陣，用Heun三階算法來求解，對于任意信賴域半徑Δ，一定可以找到自然數(shù)N，使得滿足

結合定理1和定理2可以知道：對于任意信賴域半徑Δ，Heun三階折線δ(τ)上確定的近似解存在且唯一；沿著折線δ(τ)可以尋求子問題（2）的最優(yōu)解δ*，且該點在信賴域邊界上取得。

6 數(shù)值實驗

用以下兩個信賴子問題的測試函數(shù)[16]，運用Matlab2012b進行數(shù)值實驗，得到相應的結果，并進行簡要分析。

測試函數(shù)1：

測試函數(shù)2：

實驗中，選取不同的信賴域半徑Δ，分別用Heun三階算法和混合折線法來計算不定子問題最優(yōu)解，并與精確解進行比較。qHD-qHeun表示兩種方法所求的最優(yōu)解的差值。具體結果見表1和表2。

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

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

從實驗數(shù)據(jù)可以看出，Heun三階算法有效可行；且當信賴域半徑在一定范圍內時，Heun三階算法與混合折線法的差值越來越大，說明在一定約束條件下，Heun三階算法效果非常好。

7 結論

針對Hessian矩陣不正定的信賴域子問題，構造了對稱正定的矩陣，用新的折線來逼近最優(yōu)解曲線，構造出Heun三階算法；通過對算法路徑性質的分析，理論上證明了算法的適定性；又通過數(shù)值實驗證明了算法可行并且在一定條件下收斂效果非常好。然而，當信賴域半徑接近擬牛頓步長時，新算法優(yōu)勢不再明顯，需要以后繼續(xù)研究。

[1] 袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京：科學出版社，2010.

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

[3] 徐成賢，陳志平，李乃成.近代優(yōu)化方法[M].北京：科學出版社，2002.

[4] Zhou Qunyan，Zhang Chun.A new nonmonotone adaptivetrustregionmethodbasedonsimplequadratic models[J].Journal of Applied Mathematics and Computing，2012，40（1/2）：111-123.

[5] Toint P L，Tomanos D.A multilevel algorithm for solving the trust-region subproblem[J].Optimization Methods and Software，2009，24（2）：299-311.

[6] Zhu X T，Xi M，Sun W Y，et al.A new nonmonotone BB-TR method based on simple conic model for large scale unconstrained optimization[J].Numerical Mathematics A Journal of Chinese Universities，2016，38（2）：172-192.

[7] 李亮.一類求解信賴域子問題的歐拉算法[D].太原：太原科技大學，2014.

[8] Powell M J D.A hybrid method for nonlinear equations[C]//NumericalMethodsforNonlinearAlgebraic Equations.Rabinowtiz Ped，London：Gordon and Breach，1970：87-114.

[9] Dennis J E，Mei H H W.Two new unconstrained optimizationalgorithmswhichusefunctionandgradient values[J].Journal of Optimization Theory and Applications，1979，28（4）：453-482.

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

[11] 王希云，邵安.一種雙割線折線法求解信賴域子問題[J].應用數(shù)學，2012，25（2）：419-424.

[12] Zhang Jianzhong，Xu Chenxian.A class of indefinite dogleg path methods for unconstrained minimization[J].SIAM Journal on Optimization，1999，9（3）：646-667.

[13] Chen Jun，Sun Wenyu.Nonmonotone adaptive trust region algorithms with indefinite dogleg path methods for unconstrained minimization[J].Northeast Math Journal，2008，24（1）：19-30.

[14] 邵安，王希云.一種求解不定信賴域子問題的雙割線折線法[J].太原科技大學學報，2011，32（6）：483-497.

[15] 趙丹.解信賴域子問題的混合折線法[J].徐州師范大學學報：自然科學版，2009，27（3）：38-41.

[16] 王希云，賈新輝，王子豪.一種改進的隱式Euler切線法[J].應用數(shù)學與力學，2017，38（3）：347-354.

[17] 顏慶津.數(shù)值分析[M].北京：北京航空航天大學出版社，2006.

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

DONG Jianxin,LI Linjun,WANG Xiyun.Heun third-order algorithm for solving indefinite trust region subproblems.Computer Engineering andApplications,2018,54（6）：55-61.

DONG Jianxin1,LI Linjun2,WANG Xiyun2

1.Department of Mathematics,Changzhi University,Changzhi,Shanxi 046011,China
2.School ofApplied Science,Taiyuan University of Science and Technology,Taiyuan 030024,China

For the trust region subproblems,it is modified by Bunch-Parlett method when the Hessian matrix is indefinite.In addition,symmetric positive-definite matrix is also constructed,and the stator problem is transformed into a positivedefinite subproblem.The Heun third-order algorithm is given by using a new polygonal line to approximate the solution curve.Then,the feasibility of this algorithm is theoretically proved by analyzing the properties of path of Heun thirdorder polyline.Finally,the numerical experiments of two test-function show that the algorithm is effective.

trust region subproblems;differential equation model;indefinite matrix;Heun third-order algorithm

針對信賴域子問題，當Hessian矩陣不正定時，利用Bunch-Parlett法對矩陣進行修正，構造了對稱正定的矩陣，將不定子問題轉化為正定子問題，用新的折線來逼近最優(yōu)解曲線，給出了求解的Heun三階算法。通過對Heun三階折線路徑性質的分析，理論上證明了算法的適定性。利用兩個測試函數(shù)進行了數(shù)值實驗，結果表明該算法有效。

信賴域子問題；微分方程模型；不定矩陣；Heun三階算法

2017-07-28

2017-10-27

1002-8331（2018）06-0055-07

A

O221

10.3778/j.issn.1002-8331.1707-0457

國家自然科學基金青年項目（No.61602061）；山西省“131”領軍人才工程項目；長治學院校級科研項目（No.201607）。

董建新（1978—），男，講師，研究領域為運籌優(yōu)化與數(shù)值計算，E-mail：jianxindong@163.com；李琳?。?991—），女，碩士，研究領域為最優(yōu)化理論及應用；王希云（1963—），女，教授，研究領域為最優(yōu)化理論及應用。

◎網絡、通信與安全◎