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

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

minf(x),x∈Rn

(1)

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

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

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

(2)

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

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

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

1 微分方程模型的構造

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

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

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

(3)

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

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

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

(4)

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

Bδ′+δ+μδ′=0

即

(B+μI)δ′=-δ

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

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

從而構造的微分方程模型如下：

(5)

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

2 折線Υ的構造

休恩公式如下：

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

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

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

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

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

求出下一點PN(μN,δN)，其中μN=Nh.

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

3 休恩算法

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

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

步1令δ0=δnp=-B-1g，如果△≥‖δ0‖2，則取δ0=δ0.停止計算，否則轉步2.

停止計算，否則令n∶=1，轉步4.

4 數(shù)值結果

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

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

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

附錄：測試函數(shù)

參考文獻：

[1] 徐成賢，陳志平，李乃成.近代優(yōu)化方法[M].北京：科學出版社，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].高校應用數(shù)學學報：A輯，2003，18(3)：341-349.

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

[5] 陳爭，馬昌風.求解信賴域子問題的一個光滑牛頓法[J].福建師范大學學報：自然科學版，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].徐州師范大學學報：自然科學版，2009，27(3)：38-41.

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

[9] 張立，唐志強.解信賴域子問題的混合折線法[J].南京師大學報：自然科學版，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].運籌與管理，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ù)值計算與計算機應用，2000，21(1)：77-80.

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

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