于海波,王希云,李 亮(太原科技大學(xué),太原 030024)
信賴域算法是求解非線性優(yōu)化問題的一類重要的數(shù)值計算方法,信賴域算法以其較強的適定性和全局收斂性受到最優(yōu)化研究者們的廣泛關(guān)注,一直以來是非線性規(guī)劃的研究熱點。對于求解如下無約束優(yōu)化問題[1],信賴域算法是一種重要的數(shù)值方法。
考慮無約束優(yōu)化問題:
minF(x),x∈Rn
(1)
其中F(x)∶Rn→R是目標函數(shù),二次連續(xù)可微,x∈Rn為待求變量。
信賴域方法的關(guān)鍵是每次迭代時都要求解下面形式的信賴域子問題:
(2)
其中g(shù)∈Rn為目標函數(shù)在當(dāng)前迭代點的梯度,B∈Rn×n為目標函數(shù)在當(dāng)前迭代點的Hessian矩陣或其近似,△∈R為信賴域半徑,δ∈Rn為待求變量。當(dāng)△變化時,上述信賴域子問題(2)的解δ*就形成一條空間曲線,稱為最優(yōu)曲線[2]。
基于信賴域子問題精確求解方法的思想,得到最優(yōu)曲線的參數(shù)方程如下:
δ=-(B+μI)-g(μ≥0)
(3)
定義函數(shù)y=f(μ)=‖δ‖2=‖-(B+μI)-1g‖2,(μ≥0).則信賴域子問題的解δ*為:
當(dāng)μ=0時,解δ*=-B-1g;當(dāng)μ>0時,通過求解一元非線性方程:
f(μ)-△=‖-(B+μI)-1g‖2-△=0
分段割線法的思想是在B正定的前提下,利用函數(shù)f(μ)的單調(diào)減性,當(dāng)給定的信賴域半徑△≥‖B-1g‖2時,令μ=μ0=0,得到子問題的最優(yōu)解δ*=-B-1g;當(dāng)給定的信賴域半徑△<‖B-1g‖2時,以適當(dāng)?shù)牟介L不斷增大μ,從而縮小函數(shù)f(μ)的值,最終找到一個最小的正整數(shù)m,使得f(μm)-△≤0,得到方程f(μ)-△=0的有根區(qū)間[μm-1,μm].通過對節(jié)點[μk,f(μk)],(k=0,1,…,m)進行線性插值構(gòu)造m條直線,連接所有直線構(gòu)成分段割線,最后在插值點[μm-1,f(μm-1)]和[μm,f(μm)]之間利用線性插值構(gòu)造的線性函數(shù)代替f(μ)來求解方程f(μ)-△=0的根μ*,從而求得子問題的解δ*=-(B+μ*I)-1g.
分段割線法的缺點是:在節(jié)點處分段線性插值函數(shù)一般不具有光滑性,出現(xiàn)尖點,并且與函數(shù)f(μ)的誤差較大。
為了克服分段割線法的上述缺陷,本文利用分段三次Hermite插值函數(shù)在節(jié)點處光滑,且與被插值函數(shù)的誤差較小的優(yōu)點,提出了一種求解信賴域子問題的分段Hermite插值法。
分段Hermite插值法的思想是在分段割線法的基礎(chǔ)上,通過對節(jié)點[μk,f(μk)],(k=0,1,…,m)進行三次Hermite插值構(gòu)造m條曲線,每條曲線的方程記為Hk(μ),(k=0,1,…,m).連接所有曲線構(gòu)成分段三次Hermite曲線,最后在插值點[μm-1,f(μm-1)]和[μm,f(μm)]之間利用三次Hermite插值構(gòu)造的三次插值函數(shù)H(μ)近似代替f(μ)來求解方程f(μ)-△=0的根μ*,從而求得子問題的最優(yōu)解δ*=-(B+μ*I)-1g.采用這種方法構(gòu)造的曲線,能夠有效的避免分段割線法在節(jié)點處曲線為尖點,不光滑的缺點,進而提高了子問題(2)的解的精度。
分段三次Hermite插值,分段線性插值及函數(shù)f(μ)的幾何意義如圖1所示:
圖1 分段三次Hermite插值,分段線性插值及函數(shù)f(μ)的圖示
從圖像可以看出,分段三次Hermite插值曲線更加逼近函數(shù)f(μ).
由此,可得下列結(jié)論:
定理2.1對函數(shù)f(μ)利用分段三次Hermite插值法所構(gòu)造的分段曲線Γ為:
其中:
(k=1,2,…,m),則H(μ)滿足:
(1)H(μ)關(guān)于μ為連續(xù)單調(diào)減函數(shù)。
(2)對任意給定的信賴域半徑△<‖-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表明,對于任意給定的信賴域半徑△<‖-B-1g‖2,方程H(μm)-△=0的根存在且唯一。
下面給出本文算法3.1和信賴域算法3.2的一般框架。
算法3.1(分段三次Hermite插值法):
步0給定梯度g,正定矩陣B,信賴域半徑△,適當(dāng)步長h.
步2計算f(μk)及f′(μk),μk=μk-1+h.在插值節(jié)點[μk-1,f(μk-1)]和[μk,f(μk)]之間使用三次Hermite插值的方法構(gòu)造曲線Hk(μ),形成分段曲線Γ.
注:步0中選取的步長h越小,由算法3.1求得的信賴域子問題(2)的解δ*就越精確。
算法3.2(非單調(diào)信賴域方法)[5]:
步1如果‖▽F(x(k))‖2≤ε,則算法終止,得到(1)的解x(k).否則,轉(zhuǎn)步2;
步2運用算法3.1求解信賴域子問題(2)得到解δk,‖δ(k)‖2≤△k,且滿足:
其中: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公式。
本文首先選取兩個測試函數(shù)Function1和Function2,運用算法3.1對信賴域子問題進行數(shù)值實驗,然后再利用算法3.2對從文獻[6]和[7]中選取的無約束優(yōu)化測試函數(shù)進行求解,并與采用分段割線法求解信賴域子問題的非單調(diào)信賴域算法進行了比較。
對于測試函數(shù)Function1和Function2,給定步長h=1,選取不同的信賴域半徑△,利用MATLAB數(shù)學(xué)軟件,采用本文算法3.1對測試函數(shù)進行數(shù)值實驗,并將實驗結(jié)果與分段割線算法進行比較,相關(guān)數(shù)值結(jié)果見表1和表2,其中SSD表示分段割線法,HCL表示本文算法3.1,fSSD表示分段割線法求得的測試函數(shù)最優(yōu)解的數(shù)值解,fHCL表示分段三次Hermite插值法求得的測試函數(shù)最優(yōu)解的數(shù)值解。fSSD-fHCL表示兩者的差值,則該差值越大,表明分段三次Hermite插值法越好。
表1 Function1數(shù)值結(jié)果
從表1和表2的數(shù)值結(jié)果可以看出,當(dāng)信賴域半徑△≥‖B-1g‖2時,分段三次Hermite插值法與分段割線法求得的測試函數(shù)的最優(yōu)解的數(shù)值結(jié)果相同(事實上,此時為牛頓算法);當(dāng)信賴域半徑△≤‖B-1g‖2時,分段三次Hermite插值法的結(jié)果要優(yōu)于分段割線法。因此,分段三次Hermite插值法的求解精度更高,能夠更好的逼近函數(shù)f(μ),是一種很好的求解信賴域子問題的精確解法。其中測試函數(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的實驗結(jié)果可以看出,對于不同的測試函數(shù),采用算法THCL與算法TSSD,在滿足終止條件‖▽F(x(k))‖2≤ε的前提下,對給定的初始點x(0),兩者計算所需的迭代次數(shù)及數(shù)值最優(yōu)解都十分接近。總體來說,利用算法THCL求得的測試函數(shù)的最優(yōu)解的數(shù)值結(jié)果要優(yōu)于算法TSSD.
數(shù)值實驗及理論分析都表明,運用本文提出的分段三次Hermite插值法求解信賴域子問題是有效且可行的。對于無約束優(yōu)化問題,能夠較好的結(jié)合非單調(diào)信賴域算法計算其最優(yōu)解。
參考文獻:
[1] 李亮,王希云.解信賴域子問題的分段割線法[J].太原科技大學(xué)學(xué)報,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] 姚升保,施保昌.一類帶線搜索的非單調(diào)信賴域算法[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實現(xiàn)[M].北京:高等教育出版社,2007.
[9] 李董輝,童小嬌,萬中.數(shù)值最優(yōu)化算法與理論[M].北京:科學(xué)出版社,2010.