解信賴(lài)域子問(wèn)題的分段Hermite插值法

于海波，王希云，李 亮(太原科技大學(xué)，太原 030024)

信賴(lài)域算法是求解非線性?xún)?yōu)化問(wèn)題的一類(lèi)重要的數(shù)值計(jì)算方法，信賴(lài)域算法以其較強(qiáng)的適定性和全局收斂性受到最優(yōu)化研究者們的廣泛關(guān)注，一直以來(lái)是非線性規(guī)劃的研究熱點(diǎn)。對(duì)于求解如下無(wú)約束優(yōu)化問(wèn)題[1]，信賴(lài)域算法是一種重要的數(shù)值方法。

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

minF(x),x∈Rn

(1)

其中F(x)∶Rn→R是目標(biāo)函數(shù)，二次連續(xù)可微，x∈Rn為待求變量。

信賴(lài)域方法的關(guān)鍵是每次迭代時(shí)都要求解下面形式的信賴(lài)域子問(wèn)題：

(2)

其中g(shù)∈Rn為目標(biāo)函數(shù)在當(dāng)前迭代點(diǎn)的梯度，B∈Rn×n為目標(biāo)函數(shù)在當(dāng)前迭代點(diǎn)的Hessian矩陣或其近似，△∈R為信賴(lài)域半徑，δ∈Rn為待求變量。當(dāng)△變化時(shí)，上述信賴(lài)域子問(wèn)題(2)的解δ*就形成一條空間曲線，稱(chēng)為最優(yōu)曲線[2]。

基于信賴(lài)域子問(wèn)題精確求解方法的思想，得到最優(yōu)曲線的參數(shù)方程如下：

δ=-(B+μI)-g(μ≥0)

(3)

定義函數(shù)y=f(μ)=‖δ‖2=‖-(B+μI)-1g‖2，(μ≥0).則信賴(lài)域子問(wèn)題的解δ*為：

當(dāng)μ=0時(shí)，解δ*=-B-1g；當(dāng)μ>0時(shí)，通過(guò)求解一元非線性方程：

f(μ)-△=‖-(B+μI)-1g‖2-△=0

分段割線法的思想是在B正定的前提下，利用函數(shù)f(μ)的單調(diào)減性，當(dāng)給定的信賴(lài)域半徑△≥‖B-1g‖2時(shí)，令μ=μ0=0，得到子問(wèn)題的最優(yōu)解δ*=-B-1g；當(dāng)給定的信賴(lài)域半徑△<‖B-1g‖2時(shí)，以適當(dāng)?shù)牟介L(zhǎng)不斷增大μ，從而縮小函數(shù)f(μ)的值，最終找到一個(gè)最小的正整數(shù)m，使得f(μm)-△≤0，得到方程f(μ)-△=0的有根區(qū)間[μm-1,μm].通過(guò)對(duì)節(jié)點(diǎn)[μk,f(μk)]，(k=0,1,…,m)進(jìn)行線性插值構(gòu)造m條直線，連接所有直線構(gòu)成分段割線，最后在插值點(diǎn)[μm-1,f(μm-1)]和[μm,f(μm)]之間利用線性插值構(gòu)造的線性函數(shù)代替f(μ)來(lái)求解方程f(μ)-△=0的根μ*，從而求得子問(wèn)題的解δ*=-(B+μ*I)-1g.

分段割線法的缺點(diǎn)是：在節(jié)點(diǎn)處分段線性插值函數(shù)一般不具有光滑性，出現(xiàn)尖點(diǎn)，并且與函數(shù)f(μ)的誤差較大。

為了克服分段割線法的上述缺陷，本文利用分段三次Hermite插值函數(shù)在節(jié)點(diǎn)處光滑，且與被插值函數(shù)的誤差較小的優(yōu)點(diǎn)，提出了一種求解信賴(lài)域子問(wèn)題的分段Hermite插值法。

1 分段三次Hermite插值法的思想

分段Hermite插值法的思想是在分段割線法的基礎(chǔ)上，通過(guò)對(duì)節(jié)點(diǎn)[μk,f(μk)]，(k=0,1,…,m)進(jìn)行三次Hermite插值構(gòu)造m條曲線，每條曲線的方程記為Hk(μ)，(k=0,1,…,m).連接所有曲線構(gòu)成分段三次Hermite曲線，最后在插值點(diǎn)[μm-1,f(μm-1)]和[μm,f(μm)]之間利用三次Hermite插值構(gòu)造的三次插值函數(shù)H(μ)近似代替f(μ)來(lái)求解方程f(μ)-△=0的根μ*，從而求得子問(wèn)題的最優(yōu)解δ*=-(B+μ*I)-1g.采用這種方法構(gòu)造的曲線，能夠有效的避免分段割線法在節(jié)點(diǎn)處曲線為尖點(diǎn)，不光滑的缺點(diǎn)，進(jìn)而提高了子問(wèn)題(2)的解的精度。

2 分段三次Hermite曲線路徑的性質(zhì)分析

分段三次Hermite插值，分段線性插值及函數(shù)f(μ)的幾何意義如圖1所示：

圖1 分段三次Hermite插值，分段線性插值及函數(shù)f(μ)的圖示

從圖像可以看出，分段三次Hermite插值曲線更加逼近函數(shù)f(μ).

由此，可得下列結(jié)論：

定理2.1對(duì)函數(shù)f(μ)利用分段三次Hermite插值法所構(gòu)造的分段曲線Γ為：

其中:

(k=1,2,…,m),則H(μ)滿(mǎn)足：

(1)H(μ)關(guān)于μ為連續(xù)單調(diào)減函數(shù)。

(2)對(duì)任意給定的信賴(lài)域半徑△<‖-B-1g‖2，一定存在μm，使得:

H(μm)-△≤0

證明：(1)由引理2.1的結(jié)論可知，H(μ)關(guān)于μ為連續(xù)單調(diào)減函數(shù)。

(2)利用(1)的結(jié)論可知結(jié)論(2)成立，證畢。

定理2.1表明，對(duì)于任意給定的信賴(lài)域半徑△<‖-B-1g‖2，方程H(μm)-△=0的根存在且唯一。

下面給出本文算法3.1和信賴(lài)域算法3.2的一般框架。

3 算法框架

算法3.1(分段三次Hermite插值法)：

步0給定梯度g，正定矩陣B，信賴(lài)域半徑△，適當(dāng)步長(zhǎng)h.

步2計(jì)算f(μk)及f′(μk)，μk=μk-1+h.在插值節(jié)點(diǎn)[μk-1,f(μk-1)]和[μk,f(μk)]之間使用三次Hermite插值的方法構(gòu)造曲線Hk(μ)，形成分段曲線Γ.

注：步0中選取的步長(zhǎng)h越小，由算法3.1求得的信賴(lài)域子問(wèn)題(2)的解δ*就越精確。

算法3.2(非單調(diào)信賴(lài)域方法)[5]：

步1如果‖▽F(x(k))‖2≤ε，則算法終止，得到(1)的解x(k).否則，轉(zhuǎn)步2；

步2運(yùn)用算法3.1求解信賴(lài)域子問(wèn)題(2)得到解δk，‖δ(k)‖2≤△k，且滿(mǎn)足:

其中:aredk=Fl(k)-F[x(k)+δ(k)]

步4如果rk≥η，轉(zhuǎn)步5；否則取λk為{1,β,β2,…}中使得下式成立的最大數(shù)：

令x(k+1)=x(k)+λkδ(k)，△k+1∈[c1‖δ(k)‖2,c2‖δ(k)‖2]，轉(zhuǎn)步6；

步5令x(k+1)=x(k)+δ(k)，△k+1∈[‖δ(k)‖2,c3‖δ(k)‖2]；

算法中Bk+1的產(chǎn)生可用BFGS公式。

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

本文首先選取兩個(gè)測(cè)試函數(shù)Function1和Function2，運(yùn)用算法3.1對(duì)信賴(lài)域子問(wèn)題進(jìn)行數(shù)值實(shí)驗(yàn)，然后再利用算法3.2對(duì)從文獻(xiàn)[6]和[7]中選取的無(wú)約束優(yōu)化測(cè)試函數(shù)進(jìn)行求解，并與采用分段割線法求解信賴(lài)域子問(wèn)題的非單調(diào)信賴(lài)域算法進(jìn)行了比較。

對(duì)于測(cè)試函數(shù)Function1和Function2，給定步長(zhǎng)h=1，選取不同的信賴(lài)域半徑△，利用MATLAB數(shù)學(xué)軟件，采用本文算法3.1對(duì)測(cè)試函數(shù)進(jìn)行數(shù)值實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果與分段割線算法進(jìn)行比較，相關(guān)數(shù)值結(jié)果見(jiàn)表1和表2，其中SSD表示分段割線法，HCL表示本文算法3.1，fSSD表示分段割線法求得的測(cè)試函數(shù)最優(yōu)解的數(shù)值解，fHCL表示分段三次Hermite插值法求得的測(cè)試函數(shù)最優(yōu)解的數(shù)值解。fSSD-fHCL表示兩者的差值，則該差值越大，表明分段三次Hermite插值法越好。

表1 Function1數(shù)值結(jié)果

從表1和表2的數(shù)值結(jié)果可以看出，當(dāng)信賴(lài)域半徑△≥‖B-1g‖2時(shí)，分段三次Hermite插值法與分段割線法求得的測(cè)試函數(shù)的最優(yōu)解的數(shù)值結(jié)果相同(事實(shí)上，此時(shí)為牛頓算法)；當(dāng)信賴(lài)域半徑△≤‖B-1g‖2時(shí)，分段三次Hermite插值法的結(jié)果要優(yōu)于分段割線法。因此，分段三次Hermite插值法的求解精度更高，能夠更好的逼近函數(shù)f(μ)，是一種很好的求解信賴(lài)域子問(wèn)題的精確解法。其中測(cè)試函數(shù)Function1的牛頓步‖B-1g‖2=10.31，F(xiàn)unction2的牛頓步‖B-1g‖2=10.05.

表2 Function2數(shù)值結(jié)果

表3 Test Function數(shù)值結(jié)果

從表3的實(shí)驗(yàn)結(jié)果可以看出，對(duì)于不同的測(cè)試函數(shù)，采用算法THCL與算法TSSD，在滿(mǎn)足終止條件‖▽F(x(k))‖2≤ε的前提下，對(duì)給定的初始點(diǎn)x(0)，兩者計(jì)算所需的迭代次數(shù)及數(shù)值最優(yōu)解都十分接近?？傮w來(lái)說(shuō)，利用算法THCL求得的測(cè)試函數(shù)的最優(yōu)解的數(shù)值結(jié)果要優(yōu)于算法TSSD.

數(shù)值實(shí)驗(yàn)及理論分析都表明，運(yùn)用本文提出的分段三次Hermite插值法求解信賴(lài)域子問(wèn)題是有效且可行的。對(duì)于無(wú)約束優(yōu)化問(wèn)題，能夠較好的結(jié)合非單調(diào)信賴(lài)域算法計(jì)算其最優(yōu)解。

參考文獻(xiàn)：

[1] 李亮，王希云.解信賴(lài)域子問(wèn)題的分段割線法[J].太原科技大學(xué)學(xué)報(bào)，2013，34(5)：393-397.

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

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

[4] FRITSCH F N，CARLSON R E.Monotone piecewise cubic interpolation[J].SIAM J Numer Anal，1980，17(1):238-246.

[5] 姚升保，施保昌.一類(lèi)帶線搜索的非單調(diào)信賴(lài)域算法[J].數(shù)學(xué)雜志，2003(3)：290-294.

[6] DENNIS J E，MEI H H W.Two new unconstrained optimization algorithms which use function and gradient values[J].Journal of Optimization Theory and Application，1979，28:453-482.

[7] MORE J J，GARBOW B S，HILLSTROM K E.Testing unconstrained optimization software[J].ACM Trans Math Software,1981，1(1/2)：17.

[8] 任玉杰.數(shù)值分析及其MATLAB實(shí)現(xiàn)[M].北京：高等教育出版社，2007.

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