董建新，李琳俊，王希云

1.長(zhǎng)治學(xué)院數(shù)學(xué)系，山西長(zhǎng)治046011

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

解不定信賴域子問(wèn)題的Heun三階算法

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

1.長(zhǎng)治學(xué)院數(shù)學(xué)系，山西長(zhǎng)治046011

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

1 引言

無(wú)約束優(yōu)化問(wèn)題為：

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

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

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

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

對(duì)式（3）兩邊求導(dǎo)，可確定微分方程模型：

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

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

2 Heun三階折線的構(gòu)造

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

步長(zhǎng)h0見(jiàn)式（6）。

且：

3 算法描述

下面給出Heun三階算法的具體步驟，其中的步長(zhǎng)選取見(jiàn)步驟后的注。

算法步驟：

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

步驟1將不定矩陣B進(jìn)行Bunch-Parlett分解，有B=LDLT成立，結(jié)合矩陣D的特征值情況構(gòu)造對(duì)稱且正定的矩陣G，并取B=G-1。

步驟2令δ0=δnp=-B-1g，若，則取：δ*=δ0，停止計(jì)算。否則轉(zhuǎn)步驟3。

步驟3令：

且μ0=0，步長(zhǎng)見(jiàn)式（5），轉(zhuǎn)步驟4。

步驟4令：

停止計(jì)算。否則令：n:=1，轉(zhuǎn)步驟5。

步驟5令：

步驟6令：

步長(zhǎng)hn見(jiàn)式（8）。

步驟7輸出解δ*。

注：算法中步長(zhǎng)選取策略如下：

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

4 Heun三階折線路徑性質(zhì)分析

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

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

證明用第二類數(shù)學(xué)歸納法來(lái)證明。

（1）當(dāng)n=1時(shí)：

由式（8）知：

（2）假設(shè)1＜n≤k時(shí)，結(jié)論成立；當(dāng)n=k+1時(shí)，有：

①當(dāng)

時(shí)，有：

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

②當(dāng)

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

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

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

證明（1）①當(dāng)即τ∈[]0,h0時(shí)，有：

則

由式（6）：

根據(jù)式（8）：

由①、②得：結(jié)論（1）成立。

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

5 算法的適定性

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

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

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

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

用以下兩個(gè)信賴子問(wèn)題的測(cè)試函數(shù)[16]，運(yùn)用Matlab2012b進(jìn)行數(shù)值實(shí)驗(yàn)，得到相應(yīng)的結(jié)果，并進(jìn)行簡(jiǎn)要分析。

測(cè)試函數(shù)1：

測(cè)試函數(shù)2：

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

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

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

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

7 結(jié)論

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

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

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

[3] 徐成賢，陳志平，李乃成.近代優(yōu)化方法[M].北京：科學(xué)出版社，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] 李亮.一類求解信賴域子問(wèn)題的歐拉算法[D].太原：太原科技大學(xué)，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] 趙英良，徐成賢.解信賴域子問(wèn)題的切線單折線法[J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，2000，21（1）：77-80.

[11] 王希云，邵安.一種雙割線折線法求解信賴域子問(wèn)題[J].應(yīng)用數(shù)學(xué)，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] 邵安，王希云.一種求解不定信賴域子問(wèn)題的雙割線折線法[J].太原科技大學(xué)學(xué)報(bào)，2011，32（6）：483-497.

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

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

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

[18] 李亮，王希云，張雅琦，等.一種求解二次模型信賴域子問(wèn)題的休恩算法[J].太原科技大學(xué)學(xué)報(bào)，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

針對(duì)信賴域子問(wèn)題，當(dāng)Hessian矩陣不正定時(shí)，利用Bunch-Parlett法對(duì)矩陣進(jìn)行修正，構(gòu)造了對(duì)稱正定的矩陣，將不定子問(wèn)題轉(zhuǎn)化為正定子問(wèn)題，用新的折線來(lái)逼近最優(yōu)解曲線，給出了求解的Heun三階算法。通過(guò)對(duì)Heun三階折線路徑性質(zhì)的分析，理論上證明了算法的適定性。利用兩個(gè)測(cè)試函數(shù)進(jìn)行了數(shù)值實(shí)驗(yàn)，結(jié)果表明該算法有效。

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

2017-07-28

2017-10-27

1002-8331（2018）06-0055-07

A

O221

10.3778/j.issn.1002-8331.1707-0457

國(guó)家自然科學(xué)基金青年項(xiàng)目（No.61602061）；山西省“131”領(lǐng)軍人才工程項(xiàng)目；長(zhǎng)治學(xué)院校級(jí)科研項(xiàng)目（No.201607）。

董建新（1978—），男，講師，研究領(lǐng)域?yàn)檫\(yùn)籌優(yōu)化與數(shù)值計(jì)算，E-mail：jianxindong@163.com；李琳俊（1991—），女，碩士，研究領(lǐng)域?yàn)樽顑?yōu)化理論及應(yīng)用；王希云（1963—），女，教授，研究領(lǐng)域?yàn)樽顑?yōu)化理論及應(yīng)用。

◎網(wǎng)絡(luò)、通信與安全◎