一種求解二次模型信賴域子問題的休恩算法

李 亮，王希云，張雅琦，于海波(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院，太原 030024)

無約束最優(yōu)化問題如下：

minf(x),x∈Rn

(1)

其中f(x)∶Rn→R是目標(biāo)函數(shù)，x∈Rn是待求變量。

對于求解無約束最優(yōu)化問題(1)，在現(xiàn)代優(yōu)化方法中，信賴域方法是一種被廣泛應(yīng)用而且具有全局收斂性的方法。所以，近二十多年來受到了非線性最優(yōu)化研究界的高度重視，成為了與傳統(tǒng)的線搜索方法并列的兩類主要算法之一。

當(dāng)用信賴域方法求解無約束最優(yōu)化問題(1)時(shí)，關(guān)鍵在于每步迭代時(shí)都需要求解下面形式的二次模型信賴域子問題：

(2)

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

如何求解二次模型信賴域子問題(2)，目前已經(jīng)提出了很多方法[2-11]。在Hessian矩陣正定的情況下，目前常用的折線法主要有單折線法、雙折線法和切線單折線法[12-14]。文獻(xiàn)[14]的數(shù)值實(shí)驗(yàn)表明，切線單折線法比單折線法、雙折線法求解二次模型信賴域子問題(2)更有效。切線單折線法的思想：連接點(diǎn)θ,δzp,δnp形成一條折線，稱為切線單折線，然后用該切線單折線近似最優(yōu)曲線來求解二次模型信賴域子問題(2).其中θ是初始點(diǎn)，δnp=-B-1g，δzp是最優(yōu)曲線在點(diǎn)δnp處的切線與-g方向的交點(diǎn)。與其它折線法相比，切線單折線法中所構(gòu)造的折線則更近似最優(yōu)曲線，但是當(dāng)信賴域半徑小于‖δzp‖2時(shí)，切線單折線法的數(shù)值結(jié)果是很不理想的。

折線法的基本思想就是尋找一條折線能夠很好的近似最優(yōu)曲線，從而用該折線代替最優(yōu)曲線來求解二次模型信賴域子問題(2).本文根據(jù)最優(yōu)曲線的參數(shù)方程首先構(gòu)造出了一個(gè)微分方程模型，從而采用求解微分方程的休恩方法[15]構(gòu)造一條折線Υ，進(jìn)而用該折線Υ代替最優(yōu)曲線來求解二次模型信賴域子問題(2).數(shù)值結(jié)果表明新算法較切線單折線法具有很好的效果，尤其是當(dāng)信賴域半徑小于‖δzp‖2時(shí)，更顯示了其明顯的優(yōu)越性。

1 微分方程模型的構(gòu)造

定理1.1[16]δ*是二次模型信賴域子問題(2)的解，當(dāng)且僅當(dāng)存在μ*≥0，使得：

而且(B+μ*I)是半正定矩陣。

由定理1.1可知，二次模型信賴域子問題的精確求解方法的思想即解如下的方程組：

(3)

當(dāng)μ=0時(shí)，二次模型信賴域子問題(2)的解δ*=-B-1g；當(dāng)μ>0時(shí)，則是通過求解一元非線性方程‖(B+μI)-1g‖2-△=0得到解μ*，然后把μ*代入式(3)的第一個(gè)方程，則可以求出二次模型信賴域子問題(2)的解δ*=-(B+μ*I)-1g.

根據(jù)二次模型信賴域子問題的精確求解方法的思想，則可以得到最優(yōu)曲線的參數(shù)方程如下：

δ=-(B+μI)-1g(μ>0)

(4)

對參數(shù)方程(4)求導(dǎo)，可得：

Bδ′+δ+μδ′=0

即

(B+μI)δ′=-δ

故求出最優(yōu)曲線上任意一點(diǎn)的切線斜率如下：

δ′=-(B+μI)-1δ(μ≥0)

從而構(gòu)造的微分方程模型如下：

(5)

對于微分方程(5)，利用求解微分方程的休恩方法，構(gòu)造了一條折線Υ，從而用該折線代替最優(yōu)曲線來求解二次模型信賴域子問題(2).

2 折線Υ的構(gòu)造

休恩公式如下：

從初始點(diǎn)P0(μ0,δ0)開始，先由公式：

求出下一點(diǎn)P1(μ1,δ1)，其中μ1=h.

…再從Pk-1(μk-1,δk-1)開始，先由公式：

求出下一點(diǎn)Pk(μk,δk)，其中μk=kh.

…再從點(diǎn)PN-1(μN(yùn)-1,δN-1)開始，先由公式：

求出下一點(diǎn)PN(μN(yùn),δN)，其中μN(yùn)=Nh.

依次作下去，直到滿足‖δN‖2≤△時(shí)停止。然后分別連接點(diǎn)P0，P1，…，PN，則可以得到折線P0P1…Pk…PN，這里記折線P0P1…Pk…PN為Υ，然后用Υ作為最優(yōu)曲線的近似，進(jìn)而來求解二次模型信賴域子問題(2)的解δ*.

3 休恩算法

通過上面的討論，下面給出休恩算法的具體步驟：

步0給定梯度g，正定矩陣B，信賴域半徑△.

步1令δ0=δnp=-B-1g，如果△≥‖δ0‖2，則取δ0=δ0.停止計(jì)算，否則轉(zhuǎn)步2.

停止計(jì)算，否則令n∶=1，轉(zhuǎn)步4.

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

取步長h=0.5，對給定的測試函數(shù)1和測試函數(shù)2的二次模型信賴域子問題，選取不同的信賴域半徑△，然后將休恩算法利用MATLAB進(jìn)行了實(shí)驗(yàn)。并且用該算法求得的相關(guān)數(shù)值結(jié)果與切線單折線法求得的相關(guān)數(shù)值結(jié)果進(jìn)行了比較。相關(guān)數(shù)據(jù)分別列在表1和表2中，其中△表示信賴域半徑，q表示測試函數(shù)的最優(yōu)解的函數(shù)值，TDL表示切線單折線法，HML表示休恩算法，qHML-qTDL表示使用休恩算法與切線單折線法所求得的測試函數(shù)的最優(yōu)解的函數(shù)值之差，該值越小，表明休恩算法越好。測試函數(shù)見附錄。

從表1和表2的數(shù)值結(jié)果可以看出，對給定的不同的信賴域半徑△，都有qHML-qTDL≤0.故本文構(gòu)造的折線Υ比切線單折線更好的近似了最優(yōu)曲線。當(dāng)信賴域半徑△≤‖δzp‖2[14]時(shí)，休恩算法所求得的測試函數(shù)的最優(yōu)解比切線單折線法好很多；當(dāng)信賴域半徑‖δzp‖2<△<‖B-1g‖2時(shí)，休恩算法求得的測試函數(shù)的最優(yōu)解也好于切線單折線法；當(dāng)信賴域半徑△≥‖B-1g‖2時(shí)，休恩算法與切線單折線法所求得的測試函數(shù)的最優(yōu)解相同。因此，休恩算法是一個(gè)比切線單折線法更好的求解信賴域子問題的折線法。對于測試函數(shù)Function 1，‖δzp‖2=2.99，‖B-1g‖2=15.34.對于測試函數(shù)Function 2，‖δzp‖2=3.64，‖B-1g‖2=11.00.

表1 測試函數(shù)1的數(shù)值結(jié)果

表2 測試函數(shù)2的數(shù)值結(jié)果

附錄：測試函數(shù)

參考文獻(xiàn)：

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

[2] CHEN J，SUN W Y.Nonmonotone Adaptive Trust Region Algorithms with Indefinite Dogleg Path for Unconstrained Minimization[J].Northeast Math J，2008，24(1)：19-30.

[3] 趙英良，徐成賢.信賴域子問題使用重新開始策略的共軛梯度法[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào)：A輯，2003，18(3)：341-349.

[4] 后六生，孫文瑜.三項(xiàng)預(yù)處理共軛梯度法與信賴域子問題[J].南京師大學(xué)報(bào)：自然科學(xué)版，2001，24(3)：1-6.

[5] 陳爭，馬昌風(fēng).求解信賴域子問題的一個(gè)光滑牛頓法[J].福建師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，27(4)：31-35.

[6] ZHANG X S，CHEN Z W，ZHANG J L.A Self-adaptive Trust Region Method For Unconstrained Optimization[J].Operation Research Transactions，2001，5(1)：53-62.

[7] 趙丹.解信賴域子問題的混合折線法[J].徐州師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，27(3)：38-41.

[8] 楊郁，王希云.基于信賴域子問題的共軛梯度法[J].太原科技大學(xué)學(xué)報(bào)，2010，31(6)：481-484.

[9] 張立，唐志強(qiáng).解信賴域子問題的混合折線法[J].南京師大學(xué)報(bào)：自然科學(xué)版，2001，24(1)：28-32.

[10] TOINT P L，TOMANOS D.A Multilevel Algorithm for Solving the Trust-region Subproblem[J].Optimization Methods and Software，2009，24(2)：299-311.

[11] 呂立波.解決大規(guī)模信賴域子問題的一種新算法[J].運(yùn)籌與管理，2007，16(5)：48-52.

[12] POWELL M J D.A Hybrid Method for Nonlinear Equations.In：Numerical Methods for Nolinear Algebraic Equations，Rabinowitz P.ed.London：Gordon and Breach，1970.

[13] 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.

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

[15] 顏慶津.數(shù)值分析[M].北京：北京航空航天大學(xué)出版社，2006.

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