解信賴域子問(wèn)題的改進(jìn)的平均歐拉切線法

賈新輝，王希云

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由(3)得:

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

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

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

由(4)式得:

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

求導(dǎo)得:

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

2 算法過(guò)程

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

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

Step 2計(jì)算牛頓步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ù)值實(shí)驗(yàn)

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

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

表2 Function1的運(yùn)行時(shí)間及迭代次數(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的運(yùn)行時(shí)間及迭代次數(shù)結(jié)果Tab.4 The running time and number of iterations of Function 2

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

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

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

附錄:測(cè)試函數(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］ 趙英良，徐成賢.解信賴域子問(wèn)題的切線單折線法［J］.數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，2000，21(1):77-80.

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

［6］ 趙丹.解信賴域子問(wèn)題的混合折線法［J］.徐州師范大學(xué)學(xué)報(bào):自然科學(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］ 王希云，邵安.一種雙割線折線法求解信賴域子問(wèn)題［J］.應(yīng)用數(shù)學(xué)，2012，25(2):419-424.

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

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

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

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