張 軍，王冠舒

（海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南?？?570228）

基于非單調(diào)技術(shù)的ODE型算法

張 軍，王冠舒

（海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南?？?570228）

將非單調(diào)技術(shù)與信賴域ODE算法相結(jié)合，提出了一種求解無約束優(yōu)化的新算法，從而減少了迭代次數(shù)以及信賴域子問題的計(jì)算次數(shù).并給出在一定條件下算法的整體收斂性，數(shù)值試驗(yàn)表明算法有效.

非單調(diào)技術(shù);信賴域ODE算法;整體收斂;無約束優(yōu)化

考慮無約束優(yōu)化問題

其中，f是Rn→R的連續(xù)可微函數(shù).

為了簡便起見，在迭代點(diǎn)xk處，用表示歐式空間的，fk，gk分別表示f（xk），f（xk），Bk為Δ2f（xk）或其對稱矩陣的一個(gè)逼近.

對于問題（1），文獻(xiàn)［1］給出了一種信賴域ODE方法.ODE方法是沿著一個(gè)常微分方程組初值問題的解曲線尋找光滑函f（x）（xR）的極值點(diǎn).其他介紹參見文獻(xiàn)［2－3］.

迄今為止，幾乎所有的ODE型信賴域算法都是單調(diào)算法.然而，對于許多函數(shù)要求目標(biāo)函數(shù)每一步嚴(yán)格單調(diào)下降會減緩收斂速率，尤其是當(dāng)目標(biāo)函數(shù)出現(xiàn)“鋸齒”形狀時(shí)候.文獻(xiàn)［4］的數(shù)值實(shí)驗(yàn)表明，非單調(diào)技術(shù)比單調(diào)技術(shù)更具明顯優(yōu)勢.

1987年，非單調(diào)線搜索方法是由GRIPPO L，LAMPARIELLO F和LUCIDI S［5］首次提出的.步長ak滿足

1 算法及收斂性分析

受文獻(xiàn)［5］中的算法啟發(fā)，結(jié)合式（2）的非單調(diào)技術(shù)，提出了ODE改進(jìn)算法.

算法1

步驟1 x0Rn，ε≥0，h0＞0給定正整數(shù)M，B0=I，0＜ρ0＜1，k:=0.

步驟2 計(jì)算gk，若≤ε停止.

步驟4 求解下面線性方程組獲得試探步dk.

步驟5 由式（2）求出fl（k），并計(jì)算fk+1及ρk，

步驟6 若ρk＜ρ0，hk=hk/2，轉(zhuǎn)步驟4（內(nèi)循環(huán)），否則轉(zhuǎn)下一步.

步驟7 hk=2hk，xk+1=xk+dk，利用BFGS公式［4］得到Bk+1，k:=k+1（外循環(huán)）.轉(zhuǎn)步驟2.

為了得到全局收斂性，故作如下假設(shè):

假設(shè)1f（x）在水平集L={x|f（x）≤f（x0）}有界.

假設(shè)2 Δf（x）是Lipschitz連續(xù)函數(shù)，即存在正常數(shù)L，滿足

引理2［6］算法1產(chǎn)生序列{xk}，當(dāng)下降方向dk滿足方程組式（3）的解時(shí)，有

1）當(dāng)h＜1/M時(shí)，此時(shí)，hBk+I正定.

定理1 在算法1以及引理2條件下，有

定理2 如果假設(shè)2、3成立，算法1的內(nèi)循環(huán)迭代有限步終止，即步驟4、步驟5、步驟6循環(huán)是有限的.

由定理1知，

引理4［5］假設(shè)2、3成立，fl（k）滿足式（2），則序列{fl（k）}單調(diào)遞減且收斂.

定理3 如果假設(shè)1、2、3成立，算法1產(chǎn)生的序列{xk}滿足:存在正整數(shù)k，gk=0.

情形1 假設(shè)存在{hk}的子列{hk}（子列仍然記為{hk}），?h0＞0，?k＞K，hk→0.類似于定理2的證明，可以得到當(dāng)hk→0+，有pk≥p0，此時(shí)必存在某個(gè)正常數(shù)m，對任意的k＞K，hk≥m，這與hk→0+矛盾.故情形1對于原命題成立.

情形2 假設(shè)?h0＞0，?k，hk≥h0.因?yàn)?/p>

由定理4，將式（20）兩端同時(shí)取極限得0≥c（矛盾），情形2原命題成立.得證.

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

選取了文獻(xiàn)［7］的15個(gè)標(biāo)準(zhǔn)函數(shù)進(jìn)行了數(shù)值試驗(yàn)，并同文獻(xiàn)［2］中的算法（M=0，記為TR-ODE）進(jìn)行了比較，數(shù)值實(shí)驗(yàn)結(jié)果如表1所示，其中算法的程序設(shè)計(jì)語言是Matlab7.1，終止條件為 gk≤10－6，其余參數(shù)選取如下，B0=I（單位矩陣），ρ0=0.75，h0=1.

表1 不同M值的數(shù)值實(shí)驗(yàn)結(jié)果比較

表1中的數(shù)值結(jié)果表明，非單調(diào)算法優(yōu)于單調(diào)算法.雖然非單調(diào)算法依賴M的選取，但非單調(diào)算法不失為一種有效的算法.

［1］BROWN A A，BIGGS M C.Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations［J］.Optim.Theory Appl，1989，62:211－224.

［2］OU Y G.A hybrid trust region algorithm for unconstrained optimization［J］.Applied Numerical Mathematics，2011，61:900－909.

［3］OU Y G.A superlinearly convergent ODE-type trust region algorithm for nonsmooth nonlinear equations［J］.Journal of Applied Mathematics＆Computing，2006，22（3）:371－380.

［4］DENG N Y，XIAO Y，ZHOU F J.A nonmonotonic trust region algorithm［J］.Journal of Optimization Theory and Applications，1993，76（2）:259－285.

［5］GRIPPO L，LAMPARIELLO F，LUCIDI S.A nonmonotone line search technique for Newton’s method［J］.SIAM.Numer.A-nal，1986，23:707－716.

［6］HAN L X.關(guān)于無約束規(guī)劃的一個(gè)ODE算法的收斂性質(zhì)［J］.計(jì)算數(shù)學(xué)，1992，15（4）:449－455.

［7］ZHOU F J，XIAO Y.A class of nonmonotone stabilization trust region methods［J］.Computing，1994，53:119－136.

Non-monotone ODE-type Trust Region Method

ZHANG Jun，WANG Guan-shu
（College of Information Science and Technology，Hainan University，Haikou 570228，China）

Non-monotone technology were combined with traditional trust region ODE-algorithm，and a new algorithm for unconstrained optimization problem were proposed，and which can reduce the number of iterations and trust region sub-problems number of calculation.Under certain assumptions，this paper also proved algorithm’s global convergence.Numerical results indicated that the proposed algorithm is effective and feasible.

non-monotonic technique;trust region ODE-algorithm;global convergence;unconstrained optimization

O 221

A

1004－1729（2012）01－0016－04

2011－10－06

海南省自然科學(xué)基金項(xiàng)目（111001）

張軍（1986－），男，四川大竹人，海南大學(xué)信息科學(xué)技術(shù)學(xué)院應(yīng)用數(shù)學(xué)系2009級碩士研究生.