一種求解不定信賴域子問題的精確解法

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

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

(1)

其中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í)，上述信賴域子問題(1)的解δ*就形成一條空間曲線，稱為最優(yōu)曲線[1]。

求解信賴域子問題的方法主要有精確求解法、折線法和截?cái)喙曹椞荻确?其中折線法是比較有效和實(shí)用的方法，如單折線法、雙折線法[1]、切線單折線法、不定折線法、混合折線法、雙割線折線法等[2-5]。而目前常用的精確求解法主要是牛頓法，為避免牛頓法中初始迭代點(diǎn)位置選取的困難，李亮[6]在Hessian陣正定的前提下提出了一種解信賴域子問題的分段割線法，有效避免了牛頓法中初值選取的困難，提高了計(jì)算效率。本文在此基礎(chǔ)上，針對Hessian陣不定的情況，提出了一種求解信賴域子問題的修正分段割線算法，進(jìn)一步完善了這一精確求解方法在一般二次模型中的應(yīng)用。

1 分段割線法的思想

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

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

(2)

定義函數(shù)y=f(μ)=‖δ‖2=‖-(B+μI)-1g‖2，(μ≥0).則信賴域子問題(1)的解δ*就是：當(dāng)μ=0時(shí)，解δ*=-B-1g；當(dāng)μ>0時(shí)，通過求解一元非線性方程f(μ)-△=‖-(B+μI)-1g‖2-△=0得到解μ*，此時(shí)解δ*=-(B+μ*I)-1g.

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

2 不定矩陣的修正

上述分段割線法是在B正定的前提下提出的，若B不定，則二次模型(1)不一定有極小值點(diǎn)，甚至沒有平穩(wěn)點(diǎn)[1]。為了克服這些困難，通常采用強(qiáng)迫矩陣正定的方法。文中采用了兩種修正不定矩陣B的方法，一種是利用Bunch-Parlett分解和矩陣的特征值來構(gòu)造新的對稱正定矩陣G[2]；另一種是利用Gill-Murray提出的修改Cholesky分解來修正不定矩陣B[1]，從而提出了兩種解決不定信賴域子問題的修正分段割線算法。通過數(shù)值實(shí)驗(yàn)比較了利用兩種修正方法解不定子問題(1)的最優(yōu)解。

2.1 Bunch-Parlett分解

對實(shí)對稱矩陣B進(jìn)行Bunch-Parlett分解：

RBRT=LDLT

其中R為置換陣，L是單位下三角矩陣，D為一塊對角陣，對角塊的階數(shù)為1或2.為方便計(jì)算，不妨設(shè)置換陣R=I，其中I為單位矩陣。從而上式變?yōu)椋?/p>

B=LDLT

由于矩陣D和B具有相同的慣性，即它們具有相同數(shù)目的正特征值、零特征值和負(fù)特征值[7]，本文利用D的特征值來構(gòu)造對稱正定矩陣G.

不妨記D的特征值為λ1,λ2,…,λn，對應(yīng)于特征值λ1,λ2,…,λn的特征向量為p1,p2,…,pn，令P=(p1,p2,…,pn)T，下面分λi>0，i=1,2,…,n和存在i使λi≤0兩種情況來構(gòu)造正定矩陣G.

由文獻(xiàn)[4]可知，G是對稱正定陣且-Gg是擬牛頓方向。

2.2 修改Cholesky分解

采用文獻(xiàn)[1]中Gill-Murray提出的修改Cholesky分解對不定矩陣B進(jìn)行修正。

3 修正分段割線算法

下面給出該算法的具體步驟：

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

步1取調(diào)整參數(shù)ε=0.1(或ε=1.1)，對B進(jìn)行Bunch-Parlett分解[7]，得到B=LDLT，利用D的特征值來構(gòu)造對稱正定矩陣G，令B=G-1；

步3計(jì)算f(μk)，μk=kh，令yk=f(μk).在插值節(jié)點(diǎn)(μk-1,yk-1)和(μk,yk)之間用線性插值方法構(gòu)造直線Lk(μ)，形成修正分段割線Γ.

注：步0中選取的步長h越小，則由該算法求得的信賴域子問題的最優(yōu)解δ*越精確。

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

對于無約束優(yōu)化的信賴域子問題(1)，本文選取不同的信賴域半徑△，利用測試函數(shù)Function 1和Function 2，分別測試了以上兩種不定修正分段割線算法。其中q(δ)表示測試函數(shù)最優(yōu)解的函數(shù)值，BPD表示采用Bunch-Parlett分解和矩陣的特征值的信息來修正不定矩陣的修正算法，CHD表示采用修改Cholesky方法修正不定矩陣的修正算法，HD表示文獻(xiàn)[2]的混合折線算法。qCHD-qBPD表示分別采用CHD和BPD修正方法所得到的最優(yōu)解的差值，該差值越大，說明采用BPD方法的修正分段割線法越好；qHD-qBPD表示分別采用HD和BPD方法得到的最優(yōu)解的差值。具體數(shù)值結(jié)果見表1、表2及表3.

當(dāng)選取不同的信賴域半徑△來求解子問題(1)時(shí)，分析表1和表2可以看出，當(dāng)信賴域半徑相對較小時(shí)，采用CHD方法的修正分段割線法與采用BPD方法的修正分段割線法相比，CHD的結(jié)果要略優(yōu)于BPD的且與精確解十分接近。然而隨著信賴域半徑的增大，CHD方法逐漸達(dá)到局部最優(yōu)解并趨于穩(wěn)定，采用BPD方法求得的最優(yōu)解要優(yōu)于CHD方法得到的最優(yōu)解。

綜上所述，雖然采用CHD方法在小半徑下求解時(shí)精度較高，但是隨著半徑的增大，求解過程容易陷入局部最優(yōu)的境地；對于BPD方法，求解過程比較穩(wěn)定，而且可以得到相應(yīng)半徑下的全局最優(yōu)解。為此，我們選取BPD方法來求解子問題(1)，并與HD算法進(jìn)行比較。對比表3的數(shù)值結(jié)果可以看出，采用BPD方法求解子問題(1)得到的最優(yōu)值明顯優(yōu)于運(yùn)用HD算法得到的最優(yōu)值。由此可見，修正分段割線法是一種求解不定信賴域子問題的很好的方法。

其中測試函數(shù)Function 1的擬牛頓步‖Gg‖=22.398，測試函數(shù)Function 2的擬牛頓步‖Gg‖=36.23.

其中測試函數(shù)如下：

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

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

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

參考文獻(xiàn)：

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

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

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

[4] CHEN JUN，SUN WENYU.Nonmonotone Adaptive Trust Region Algorithms with Inde-finite Dogleg Path for Unconstrained Minimization[J].Northeast Math ，2008，24(1)：19-30.

[5] 王希云，邵安.一種雙割線折法求解線信賴域子問題[J].應(yīng)用數(shù)學(xué)，2012，25(2)：419-424.

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

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

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

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

[10] 王建宏，錢峰.基于最速下降曲線的特征值法[J].南通大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，6(1)：20-22.