賈新輝，王希云

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

其中，gk=!f(xk)，Bk∈Rn×n是目標(biāo)函數(shù)在當(dāng)前迭代點x(k)的海塞矩陣!2f(xk)的近似，Δk是信賴域半徑，s∈Rn是待求變量.Δk取不同的值時，信賴域子問題(1)的解s*構(gòu)成了空間最優(yōu)曲線［1］。

對于海塞矩陣正定的情形，運用折線法求解子問題(1)較為普遍.常用的折線法有單折線法［2］、雙折線法［3］、切線單折線法［4］、混合折線法［5-6］、不定折線法［7-8］、雙割線折線法［9］等.2014 年王希云、李亮根據(jù)信賴域子問題解的最優(yōu)曲線的參數(shù)方程建立了微分方程模型［10］，并針對該模型提出一

討論如下二次模型的信賴域子問題的求解:種求解子問題(1)的平均歐拉切線算法［11］。

平均歐拉切線算法的思想是在微分方程模型［10］的基礎(chǔ)上，采用梯形公式［12］構(gòu)造一條折線，來近似代替最優(yōu)曲線求解子問題.數(shù)值結(jié)果表明該算法比切線單折線法更有效，但缺點是步長形式復(fù)雜，計算時間相對較長，且文［11］中定理5.1的條件可進(jìn)一步改善。

文［11］運用定理5.1的假設(shè)條件可證明構(gòu)造的折線滿足引理 6.4.1［13］，但前提又要利用引理5.1的結(jié)論2［11］.為了證明該結(jié)論，構(gòu)造了較為繁瑣的步長，導(dǎo)致迭代次數(shù)多，計算時間較長.本文為簡化步長形式，將文［11］的假設(shè)條件修正為:

并在該條件下證明了算法的適定性，也不需利用結(jié)論2［11］.且步長可簡化為:

其中n=0，1，2，…，ω為限制每次迭代所能達(dá)到的最大步長值.從而提出了求解子問題(1)的改進(jìn)的平均歐拉切線法.文章最后將本文算法和平均歐拉切線法進(jìn)行了比較，數(shù)值實驗表明新算法較平均歐拉切線法具有迭代次數(shù)少、運算時間短等優(yōu)點。

1 改進(jìn)的平均歐拉切線路徑的性質(zhì)分析

求解微分方程的梯形公式為:

改進(jìn)的平均歐拉切線記為:

其中 φ0=0，φi+1= φi+hi，i=0，1，2，3，…，N－1.

定理2.1 若B 對稱正定，則當(dāng)n=0，1，2，…，N－1時，滿足:

證明:當(dāng) n=0，1，2，…，N － 1 時，有:

由(3)得:

定理2.2 若 B 對稱正定，當(dāng) n=0，1，2，…，N－1時(4)式成立.則s(τ)滿足:

(1)‖s(τ)‖2關(guān)于τ為連續(xù)單調(diào)遞減函數(shù);

(2)qks(τ[])關(guān)于τ為連續(xù)單調(diào)遞增函數(shù).

由(4)式得:

故對 τ∈［φi，φi+1］，i=0，1，2，3，…，N － 1時，‖s(τ)‖2關(guān)于τ為單調(diào)遞減函數(shù).

求導(dǎo)得:

故對 τ∈［φi，φi+1］，i=0，1，2，3，…，N － 1時，qks(τ[])關(guān)于τ為單調(diào)遞增函數(shù).證畢。

2 算法過程

下面給出本文算法的具體步驟:

Step 1給出梯度 g，正定矩陣 B，信賴域半徑Δ.

Step 2計算牛頓步s0=－B－1g.

Step 3若‖s0‖2≤ Δ，則取s*=s0，算法終止.否則，轉(zhuǎn)Step 4.

c= ‖sn‖22－ Δ2，算法終止.否則，令n:=n+1，轉(zhuǎn) Step 5.

3 數(shù)值實驗

對于信賴域子問題(1)，本文采用給定的測試函數(shù)1和測試函數(shù)2，針對不同的信賴域半徑Δ，選取限制步長ω=2，運用MATLAB將本文中改進(jìn)的平均歐拉切線算法進(jìn)行數(shù)值實驗.并與文［11］中提出的平均歐拉切線法進(jìn)行數(shù)值結(jié)果的比較，結(jié)果分別列在如下四個表格中.

表1 Function 1最優(yōu)解的數(shù)值結(jié)果Tab.1 The numerical results of the optimal solution of Function 1

表2 Function1的運行時間及迭代次數(shù)結(jié)果Tab.2 The running time and number of iterations of Function 1

表3 Function 2最優(yōu)解的數(shù)值結(jié)果Tab.3 The numerical results of the optimal solution of Function 2

表4 Function 2的運行時間及迭代次數(shù)結(jié)果Tab.4 The running time and number of iterations of Function 2

表1中，Δ表示信賴域半徑，q表示最優(yōu)解的函數(shù)值，t表示求解子問題所用的時間，n表示迭代次數(shù)，MET表示平均歐拉切線法，IMET表示改進(jìn)的平均歐拉切線法，tMET表示平均歐拉切線法所用的時間，tIMET表示改進(jìn)的平均歐拉切線法所用的時間，nMET表示平均歐拉切線法的迭代次數(shù)，nIMET表示改進(jìn)的平均歐拉切線法的迭代次數(shù)，qMET表示平均歐拉切線法求得的最優(yōu)解的函數(shù)值，qIMET表示改進(jìn)的平均歐拉切線法求得的最優(yōu)解的函數(shù)值，測試函數(shù)見附錄。

由上述實驗結(jié)果可以得出，在信賴域半徑較小時，本文提出的改進(jìn)的平均歐拉切線法明顯要比平均歐拉切線法的計算速度高，迭代次數(shù)少，且在計算結(jié)果的精確度上與之相近.對于Function 1，當(dāng)信賴域半徑2.5≤Δ≤7.4時，改進(jìn)的平均歐拉切線法求得的信賴域子問題(1)的最優(yōu)值要比平均歐拉切線法的好，當(dāng)信賴域半徑1.3≤Δ≤及8≤Δ≤10時，本文算法不如平均歐拉切線法的結(jié)果好;對于Function 2，當(dāng)Δ為2≤Δ≤7.6時，本文算法比平均歐拉切線法的結(jié)果好，當(dāng)Δ為0.3≤Δ≤1.3及8≤Δ≤10時，平均歐拉切線法的結(jié)果較好.而當(dāng)信賴域半徑Δ=‖B－1g‖2時，兩種方法求得的結(jié)果一樣。

總體來看，本文提出的改進(jìn)的平均歐拉切線法要比平均歐拉切線法的計算效率高，迭代次數(shù)少，該算法可以很好地近似最優(yōu)曲線，是有效可行的。對 于 Function 1，‖B－1g‖2= 10.308.對 于Function 2，‖B－1g‖2=10.05 .

附錄:測試函數(shù)

參考文獻(xiàn):

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

［2］ POWELL M J D.A Hybrid Method for Nonlinear Equations［C］.//Numerical Methods for Nolinear Algebraic Equ-ations，Rabinowtiz P.ed.London:Gordon and Breach，1970.

［3］ DENNIS J E，MEI H H W.Two New Unconstrained Optimization Algorithms Which Use Function and Gradient Values［J］.Journal of Optimization Theory and Applications，1979，28(4):453-482.

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

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

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

［7］ CHEN J，SUN W Y.Nonmonotone Adaptive Trust Region Algorithms With Indefinite Dogleg Path for Unconstrained Minimization［J］.Northeast Math Journal，2008，24(1):19-30.

［8］ ZHANG J Z，XU C X.A Class of Indefinite Dogleg Path Methods for Unconstrained Minimization［J］.SIAM Journal on Optimization，1999，9(3):646-667.

［9］ 王希云，邵安.一種雙割線折線法求解信賴域子問題［J］.應(yīng)用數(shù)學(xué)，2012，25(2):419-424.

［10］ 李亮，王希云，張雅琦，等.一種求解二次模型信賴域子問題的休恩算法［J］.太原科技大學(xué)學(xué)報，2014，35(2):151-155.

［11］ 李亮.一類求解信賴域子問題的歐拉算法［D］.太原:太原科技大學(xué)，2014.

［12］ 顏慶津.數(shù)值分析［M］.北京:北京航空航天大學(xué)出版社，2006.

［13］ 李董輝，童小嬌，萬中.數(shù)值最優(yōu)化算法與理論［M］.北京:科學(xué)出版社，2010.