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

朱帥, 李亮,, 王希云, 張雅琦, 于海波

(1.山西大同大學(xué)工學(xué)院, 山西 大同 037003; 2.太原科技大學(xué)應(yīng)用科學(xué)學(xué)院, 山西 太原 030024)

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

朱帥1, 李亮1,2, 王希云2, 張雅琦2, 于海波2

(1.山西大同大學(xué)工學(xué)院, 山西 大同 037003; 2.太原科技大學(xué)應(yīng)用科學(xué)學(xué)院, 山西 太原 030024)

在Hessian矩陣正定的前提下, 首先根據(jù)信賴域子問題精確求解方法的思想, 得到了最優(yōu)曲線的參數(shù)方程, 進而建立了一種最優(yōu)曲線的微分方程模型.針對此微分方程模型, 運用中點公式構(gòu)造了一條折線.從而用該折線代替最優(yōu)曲線, 提出了一種求解二次模型信賴域子問題的新算法.數(shù)值結(jié)果表明新算法比切線單折線法具有明顯的優(yōu)勢.

最優(yōu)曲線; 中點公式; 微分方程模型; 信賴域子問題

1 引言

在非線性優(yōu)化中, 信賴域方法是一種被廣泛應(yīng)用而且具有全局收斂性的方法.信賴域方法的優(yōu)點之一就是不要求目標函數(shù)是凸函數(shù).

無約束最優(yōu)化問題如下:

其中f (x):Rn→R 是目標函數(shù),x∈Rn是待求變量.

當用信賴域方法求解(1.1)時, 關(guān)鍵在于每步迭代時都需求解下面形式的二次模型信賴域子問題:

其中g(shù)∈Rn為目標函數(shù)在當前迭代點的梯度,B∈Rn×n為目標函數(shù)在當前迭代點的Hessian矩陣或其近似, Δ∈R 為信賴域半徑,δ∈Rn為待求變量.當Δ變化時, 上述二次模型信賴域子問題(1.2)的解δ*形成一條空間曲線, 稱為最優(yōu)曲線[1].

如何求解二次模型信賴域子問題(1.2), 目前已經(jīng)提出了很多方法[2-12].在 Hessian矩陣正定的情況下, 目前常用的折線法主要有單折線法、雙折線法和切線單折線法[13-15].文獻[15]的數(shù)值實驗表明, 切線單折線法比單折線法、雙折線法求解二次模型信賴域子問題(1.2)更有效.切線單折線法的思想: 連接點θ,δzp,δnp形成一條折線,稱為切線單折線, 然后用該切線單折線近似最優(yōu)曲線來求解二次模型信賴域子問題(1.2).其中θ是初始點, δnp=-B-1g,δzp是最優(yōu)曲線在點δnp處的切線與-g 方向的交點.與其它折線法相比, 切線單折線法中所構(gòu)造的折線則更近似最優(yōu)曲線, 但是當信賴域半徑小于時, 切線單折線法的數(shù)值結(jié)果是很不理想的.

折線法的基本思想就是尋找一條折線能夠很好的近似最優(yōu)曲線, 從而用該折線代替最優(yōu)曲線來求解二次模型信賴域子問題(1.2).本文根據(jù)最優(yōu)曲線的參數(shù)方程首先構(gòu)造出了一個微分方程模型, 從而采用中點公式[16]構(gòu)造一條折線X, 進而用折線X代替最優(yōu)曲線來求解(1.2).數(shù)值結(jié)果表明新算法較切線單折線法具有很好的效果,尤其是信賴域半徑小于時, 更顯示了其明顯的優(yōu)越性.

2 微分方程模型的構(gòu)造

定理2.1[17]δ*是子問題(1.2)的解, 當且僅當存在μ*≥0, 使得:

而且(B+μ*I)是半正定矩陣.

由定理2.1可知, 二次模型信賴域子問題的精確求解方法的思想即解下面的方程組:

當μ=0時, 二次模型信賴域子問題(1.2)的解δ*=-B-1g; 當μ＞0時, 則是通過求解一元非線性方程得到解μ*, 然后把μ*代入(2.1)的第一個方程, 則可以求出二次模型信賴域子問題(1.2)的解δ*=-(B+μ*I)-1g.

根據(jù)二次模型信賴域子問題的精確求解方法的思想, 則可以得到最優(yōu)曲線的參數(shù)方程如下:

對參數(shù)方程(2.2)求導(dǎo), 可得

對于微分方程(2.3), 借助求解微分方程的中點公式[16], 可構(gòu)造一條折線X, 從而用該折線代替最優(yōu)曲線來求解二次模型信賴域子問題(1.2).

3 構(gòu)造折線X

4 算法4.1

5 數(shù)值結(jié)果

對給定的測試函數(shù)1和測試函數(shù)2的信賴域子問題, 選取不同的信賴域半徑Δ, 取步長0.5h=, 然后將算法4.1利用MATLAB進行了實驗.并且用該算法求得的相關(guān)數(shù)據(jù)與切線單折線法求得的相關(guān)數(shù)據(jù)進行了比較.數(shù)值結(jié)果分別列在表1和表2中, 其中Δ表示信賴域半徑,q表示測試函數(shù)的最優(yōu)解的函數(shù)值,TDL表示切線單折線法,ZDL表示算法4.1,TDLZDLqq-表示使用切線單折線法與算法4.1所求得的測試函數(shù)的最優(yōu)解的函數(shù)值之差, 該值越大, 表明算法4.1越好.測試函數(shù)見附錄.

從表1和表2的數(shù)值結(jié)果可以看出, 對給定的不同的信賴域半徑Δ, 都有TDLZDL0 qq-≥.故本文構(gòu)造的折線X比切線單折線更好的近似了最優(yōu)曲線.當信賴域半徑(見文獻[15])時, 算法4.1求得的測試函數(shù)的最優(yōu)解比切線單折線法好很多; 當信賴域半徑時, 算法4.1也稍好于切線單折線法; 當信賴域半徑時, 算法4.1與切線單折線法所求得的測試函數(shù)的最優(yōu)解相同.因此, 算法4.1是一個比切線單折線法更好的求解信賴域子問題的折線法.對于測試函數(shù)對于測試函數(shù)

表1 測試函數(shù)1的數(shù)值結(jié)果Tab.1 The numerical results of test function 1

6.5 -152.164602343 -158.220691419 6.056089077 7.0 -157.009602821 -161.791121598 4.781518776 7.5 -161.145899926 -164.842575244 3.696675318 8.0 -164.658087449 -167.434494268 2.776406819 10.0 -173.378012798 -173.822748492 0.444735694 11.0 -174.888974452 -174.919571990 0.030597537Δ11.36≥ -175.000000000 -175.000000000 0

表2 測試函數(shù)2的數(shù)值結(jié)果Tab.2 The numerical results of test function 2

[1] 徐成賢,陳志平,李乃成. 近代優(yōu)化方法[M].北京:科學(xué)出版社,2002.

[2] 趙英良,徐成賢.信賴域子問題使用重現(xiàn)開始策略的共軛梯度法[J].高校應(yīng)用數(shù)學(xué)學(xué)報A輯, 2003,18(3):341-349.

[3] CHEN JUN, SUN WEN YU. Nonmonotone Adaptive Trust Region Algorithms with Indefinite Dogleg Path for Unconstrained Minimization[J]. Northeast Math J, 2008, 24(1): 19-30.

[4] 后劉生,孫文瑜.三項預(yù)處理共軛梯度法與信賴域子問題[J].南京師大學(xué)報: 自然科學(xué)版, 2001, 24(3): 1-6.

[5] WANG FU SHENG, WANG YAN PING. Nonmonotone Algorithm for Minimax. Optimization Problems[J]. Applied Mathematics and Computation, 2011, 217: 6296-6308.

[6] 趙丹.解信賴域子問題的混合折線法[J].徐州師范大學(xué)學(xué)報:自然科學(xué)版, 2009, 27(3): 38-41.

[7] ZHANG XIANG SUN, CHEN ZHONG WEN, ZHANG JU LIANG. A Self-adaptive Trust Region Method For Unconstrained Optimization[J]. Operation Research Transactions, 2001, 5(1): 53-62.

[8] 楊郁,王希云. 基于信賴域子問題的共軛梯度法[J]. 太原科技大學(xué)學(xué)報, 2010, 31(6): 481-484.

[9] 陳爭,馬昌風(fēng).求解信賴域子問題的一個光滑牛頓法[J]. 福建師范大學(xué)學(xué)報: 自然科學(xué)版, 2011, 27(4): 31-35.

[10] 呂立波. 解決大規(guī)模信賴域子問題的一種新算法[J]. 運籌與管理, 2007, 16 (5):48-52.

[11] PU DING GUO, HAN BO SHUN, YAO LIN, et al. A Class of Dogleg Trust Region Methods[J]. Operations Research Transactions, 2003, 7(1): 1-10.

[12] 張立, 唐志強. 解信賴域子問題的混合折線法[J]. 南京師大學(xué)報: 自然科學(xué)版, 2001, 24(1): 28-32.

[13] POWELL M J D. A Hybrid Method for Nonlinear Equations, Numerical Methods for Nolinear Algebraic Equations. P Rabinowtiz, Gordon and Breach, London, 1970.

[14] J E DENNIS JR, H H W MEI.Two New Unconstrained Optimization Algorithms Which Use Function and Gradient Values[J]. Journal of Optimization Theory and Applications, 1979, 28(4): 453-482.

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

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

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

A new algorithm for solving trust-region subproblems with quadratic model

ZHU Shuai1, LI Liang1,2, WANG Xi-yun2, ZHANG Ya-qi2, YU Hai-bo2(1. School of Technology, Shanxi Datong University, Datong 037003, P.R.C.;
2. School of Applied Science,Taiyuan University of Technology, Taiyuan 030024, P.R.C.)

On the premise that Hessian matrix is positive definite, first a parametric equation of the optimal curve is obtained according to the thought of the accurate method for solving trust-region subproblems. Then the paper establishes a differential equation model and constructs a broken line by midpoint formula. Meanwhile, a newt algorithm is presented by using the broken line instead of the optimal curve for solving trust-region subproblems. Numerical results indicate that the new algorithm has obvious advantage over the tangent single dogleg method.

optimal curve; midpoint formula; differential equation model; trust-region subproblem

O224

A

1003-4271(2014)01-0091-06

10.3969/j.issn.1003-4271.2014.01.19

2013-10-24

朱帥(1980-), 男, 講師, 碩士, 研究方向: 最優(yōu)化理論及其應(yīng)用.

山西省自然科學(xué)基金(2008011013).