信賴域子問題求解方法及其數(shù)值試驗研究

袁 遠(yuǎn)

（滁州城市職業(yè)學(xué)院教育學(xué)院，安徽滁州 239000）

信賴域算法是目前求解無約束優(yōu)化問題的一類常用的數(shù)值計算方法，在宏微觀經(jīng)濟分析、交通運輸管理、能源通信工程、機械結(jié)構(gòu)設(shè)計等眾多領(lǐng)域應(yīng)用廣泛。信賴域子問題是信賴域算法的重要組成部分，子問題的不同求解方法直接影響著信賴域算法的數(shù)值計算效率〔1〕。目前，求解信賴域子問題的方法主要有〔2〕：1）精確求解方法。目前的精確求解方法主要是牛頓法，然而一般意義上，精確求解方法在計算時需要相當(dāng)?shù)墓ぷ髁?。例如，李亮等?〕利用分段性插值的方法提出了一種新的精確求解方法，稱為分段折線法。2）折線法。折線法就是利用一條折線來近似這條最優(yōu)曲線，然后得到子問題的近似解。例如，趙英良等〔4〕的切線單折線法等。3）共軛梯度法。共軛梯度法不需要計算和存儲，是解決大型問題的首選方法。例如，趙英良等〔5〕提出的共軛梯度法解信賴域子問題的重新開始策略等。傳統(tǒng)的信賴域算法為了保證算法的整體收斂性，采取的都是具有單調(diào)下降性質(zhì)的算法，即在算法中要求Predk=q（k）（0）－q（k）（sk）＞0 以及成功迭代步滿足γk≥η1＞0〔6〕。但在解決實際問題中，當(dāng)目標(biāo)函數(shù)的非線性性態(tài)較強時，如著名的Rosenbrock 函數(shù)（曲率變化劇烈），嚴(yán)格單調(diào)下降的算法出現(xiàn)了負(fù)面影響，步長很小，收斂速度十分緩慢〔7〕。因此，不同算法的適應(yīng)性與優(yōu)劣程度不一致。本文主要從信賴域子問題的角度，討論和闡述幾種無約束優(yōu)化的信賴域算法，并且通過數(shù)值試驗來探究這些算法在求解信賴域子問題時的優(yōu)劣程度。

1 信賴域子問題與算法概述

1.1 非線性優(yōu)化的信賴域算法對于無約束優(yōu)化問題

對于無約束優(yōu)化問題（1），利用二次逼近，得信賴域算法的模型子問題：

其中s=x-xk，gk=f（xk），Bk是一個對稱矩陣，它是Hessian 矩陣△2f（xk）或其近似，△k＞0 為信賴域半徑，||·||為某一范數(shù)，通常采用l2范數(shù)。

根據(jù)模型函數(shù)q（k）（s）與目標(biāo)函數(shù)f（x）的一致性程度來調(diào)整信賴域半徑△k。對于式（2）的解sk，設(shè)目標(biāo)函數(shù)f（x）在第k 步的下降量

為實際下降量，設(shè)模型函數(shù)q（k）（s）在第k 步的下降量

為預(yù)測下降量。定義比值

它衡量了模型函數(shù)q（k）（s）對目標(biāo)函數(shù)f（x）的擬合程度。如果rk越接近1，說明模型函數(shù)q（k）（s）對目標(biāo)函數(shù)f（x）的擬合估計效果越好，這時可以增大△k以擴大信賴域；如果rk＞0 但不接近1，保持信賴域半徑△k不變；如果rk接近0 或取負(fù)值，說明模型函數(shù)q（k）（s）對目標(biāo)函數(shù)f（x）的擬合效果很差，則應(yīng)該減小△k，縮小信賴域。

1.2 求解信賴域子問題的算法信賴域算法實現(xiàn)的關(guān)鍵在于信賴域子問題（2）的有效求解，本文分別闡述求解信賴域子問題的3 種近似求解方法：不定折線法、Moré-Sorensen 法、截斷共軛梯度法。

（1）不定折線法

對于信賴域子問題（2），當(dāng)||Bk-1gk||＞△k時，折線法可以較為輕松地找到子問題（2）的近似解。在矩陣Bk不正定的情況下，朱紅蘭等〔6〕提出了一種不定折線法，不定折線法的基本思想：

①若Bk是正定的，則Γ（k）是Powell 的單折線路徑：Γps（k）＝［xk，xkcp，xknp］，其中xkcp，xknp分別為柯西點和牛頓點；

②若Bk是不正定的，有4 條路徑Γ（k）可選擇：

（i）當(dāng)gkTBkgk＞0 時，若gkTL-Tv≥0 或者當(dāng)gkTL-Tv＜0 且，選擇路徑：Γs1（k）＝［xk，xkcp，g］；

（ii）當(dāng)gkTBkgk＞0 時，令skB=-（Bk+μI）-1gk，xkB＝xk+skB，若||skB||≥△k且||skB||2＞（skB）Tskcp＞||skcp||2，選擇路徑：Γs2（k）＝［xk，xkcp，xkB］；

（iii）當(dāng)gkTBkgk＞0 時，除了（i）和（ii）兩種情況外：Γs3（k）＝［xk，xkB，?］，?=sgn（sTskB）s；

（iv）當(dāng)gkTBkgk≤0 時，若，選擇路徑：Γs4（k）＝［xk，xkB，-gk］；否則選擇路徑：Γs3（k）＝［xk，xkB，?］。

（2）Moré-Sorensen 法

當(dāng)μk充分大時，（Bk+μkI） 是正定的，Moré-Sorensen 法〔2〕將子問題（2）的求解基本上歸結(jié)于求下述方程組

的解。令p（μk）=-（Bk+μkI）-1gk，（3）式即為

將矩陣Bk進(jìn)行特征分解以便研究||p（μk）||的一些性質(zhì)。因為Bk是對稱矩陣，所以存在一個正交矩陣Q 以及一個對角矩陣Λ=diag（λ1，λ2，…，λn）（其中λ1≤λ2≤…≤λn且都是Bk的特征值），使得Bk=QΛQT，則Bk+μkI=Q（Λ+μkI）QT。當(dāng)μk≠λj時，有

成立。式中qj為矩陣Q 的第j 列向量，所以進(jìn)一步有

成立。事實上，如果μk＞－λ1時，則對于所有的j＝1，2，…，n，μk+λj＞0，由（6）式可以得到此外，如果qjTgk≠0，則有。所以，根據(jù)以上兩個性質(zhì)，可得p（μk）在μk∈（-λ1，+∞）是一個連續(xù)、單調(diào)遞減的凸函數(shù)，所以方程||p（μk）||＝△k在μk∈（-λ1，+∞）有唯一解μk*。令

當(dāng)μk略大于－λ1時，方程φ（μk）＝0 的解可以用牛頓迭代法來近似求得，設(shè)其解為μk*，將此代入p（μk）中，即可求出子問題（2）的解。

（3）截斷共軛梯度法

考慮與問題（2）相對應(yīng)的線性方程組

Steihaug〔7〕指出，當(dāng)矩陣Bk正定時，運算精確的共軛梯度法至多經(jīng)過n 次迭代可求得方程組（7）的最優(yōu)解－Bk-1gk。

（i） 若dkTBkdk≥0，dk＝－△f（xk）且||Bk-1gk||≤△k，則sk＝－Bk-1gk。

（ii）當(dāng)||sk||≤△k，||sk+1||≥△k，此時不論矩陣Bk是否正定，都能夠確定≥0 使得sk+1＝sk+ dk滿足||sk+1||=△k，取sk+1作為問題（2）的近似解。

（iii）若dkTBkdk≤0，即矩陣Bk不正定時，dk為矩陣Bk的一個負(fù)曲率方向，這時sk+1＝sk+ dk，使得||sk+1||=△k，取sk+1作為問題（2）的近似解。

2 數(shù)值結(jié)果與分析

2.1 對于中小規(guī)模問題的數(shù)值試驗采用Matlab R2012b 軟件，通過求解3 個試驗函數(shù)的無約束最優(yōu)化問題，從而對不定折線法、Moré-Sorensen 法、截斷共軛梯度法3 種算法的數(shù)值計算效率進(jìn)行比較。本文從國際上較流行的測試問題軟件包〔8〕和文獻(xiàn)〔9〕中選取了21 個試驗函數(shù)來進(jìn)行數(shù)值試驗，試驗函數(shù)名稱和規(guī)模（n 的大?。┮姳?。本文以求解無約束極小化問題的函數(shù)值迭代次數(shù)的大小為評價數(shù)值計算效率的指標(biāo)。

表1 試驗函數(shù)名稱

比較不定折線法、Moré-Sorensen 法、截斷共軛梯度法3 種算法在單調(diào)、非單調(diào)情況下（通過選取不同的非單調(diào)控制參數(shù)M 值實現(xiàn)改變算法的單調(diào)性數(shù)值效率，M=0 時數(shù)值效率最差呈單調(diào)性，M=10時數(shù)值效率較好呈非單調(diào)性〔10〕）求解中小規(guī)模問題的數(shù)值計算效率。表2 為在單調(diào)情況下所測試的3種算法的數(shù)值結(jié)果，表3 為在非單調(diào)情況下所測試的3 種算法的數(shù)值結(jié)果。其中ng 表示梯度迭代次數(shù)，nf 表示函數(shù)值迭代次數(shù)，min f 表示函數(shù)的最優(yōu)值。

表2 M＝0 單調(diào)時的數(shù)值結(jié)果

表3 M＝10 非單調(diào)時的數(shù)值結(jié)果

續(xù)表2

從表2 可以看出，當(dāng)M＝0 時，不定折線法、Moré-Sorensen 法、截斷共軛梯度法在求解第3、6、13、15、20 問題時計算效率一致，而截斷共軛梯度法在解決問題2、4、5、12、17、18 時數(shù)值計算效率明顯高于其他兩種算法，Moré-Sorensen 法在解決問題1、7、8、9、19 時效率最好，而不定折線法只在解決問題11、14、21 時效率較好。從表3 可以看出，當(dāng)M＝10 時，不定折線法、Moré-Sorensen 法、截斷共軛梯度法在求解第3、6、8、9、13、15、19 問題時計算效率一致，而截斷共軛梯度法在解決問題2、4、10、12、17、18 時數(shù)值計算效率明顯高于其他兩種算法，Moré-Sorensen 法在解決問題7、14、20、21 時效率最好，而不定折線法只在解決問題1、11、16 時效率較好。綜上所述可以得出在單調(diào)、非單調(diào)情況下，截斷共軛梯度法在求解以上無約束優(yōu)化問題上的數(shù)值計算效率略好于Moré-Sorensen 法，明顯優(yōu)于不定折線法。

2.2 對于大規(guī)模問題的數(shù)值試驗當(dāng)某些試驗函數(shù)維數(shù)n 很大，即處理一些大規(guī)模問題時，不定折線法、Moré-Sorensen 法、截斷共軛梯度法3 種算法在單調(diào)、非單調(diào)情況下的數(shù)值計算效率是不同的。探究和比較這3 種算法在非單調(diào)情況下（M=5）解決大規(guī)模無約束極小化問題的數(shù)值計算效率。本文所用到的試驗函數(shù)名稱及維數(shù)見表4，其中n 分別取100、500 和1 000。

表4 大規(guī)模測試問題

在Matlab R2012b 軟件中編制程序求解上述7個試驗問題，得到以下數(shù)值試驗結(jié)果。表5~7 分別表示在n=100、n=500 和n=1 000 時3 種算法的數(shù)值結(jié)果。

表5 n=100 的數(shù)值結(jié)果

從表5 可以看出，當(dāng)n＝100 時，不定折線法、Moré-Sorensen 法、截斷共軛梯度法3 種算法除了在解決第1、3、4、6 問題上計算效率一致，截斷共軛梯度法還在解決問題7 時數(shù)值計算效率高于其他兩種算法，Moré-Sorensen 法在解決問題5 時高于其他兩種算法，而不定折線法只在解決問題2 時效率較好。從表6 可以看出，當(dāng)n＝500 時，不定折線法、Moré-Sorensen 法、截斷共軛梯度法3 種算法除了在解決第2、6 問題上計算效率一致，截斷共軛梯度法還在解決問題7 時數(shù)值計算效率高于其他兩種算法，Moré-Sorensen 法在解決問題4 時高于其他兩種算法，而不定折線法只在解決問題5 時效率較好。從表7 可以看出，當(dāng)n＝1 000 時，不定折線法由于求解時間過長，軟件并未算出最終結(jié)果，可見當(dāng)函數(shù)維數(shù)較高時，其數(shù)值計算效率最低。而截斷共軛梯度法在解決第2、5 問題上計算效率要高于Moré-Sorensen 法。綜合以上分析可以得到：截斷共軛梯度法在解決大規(guī)模問題時，它的數(shù)值計算效率高于不定折線法和Moré-Sorensen 法，并且可以發(fā)現(xiàn)當(dāng)規(guī)模越大時，其數(shù)值計算效率越明顯高于其他算法。

表6 n=500 的數(shù)值結(jié)果

表7 n=1 000 的數(shù)值結(jié)果

2.3 對于病態(tài)問題的數(shù)值試驗針對病態(tài)的無約束優(yōu)化問題，運用不定折線法、Moré-Sorensen 法、截斷共軛梯度法3 種算法分別在單調(diào)和非單調(diào)情況下進(jìn)行求解。本文選取的病態(tài)問題是著名的Rosenbrock 函數(shù)

通過求解這個函數(shù)來比較單調(diào)、非單調(diào)的不同算法數(shù)值計算效率。利用Matlab R2012b 軟件求解該無約束優(yōu)化問題，得到的數(shù)值試驗結(jié)果見表8。

同時記錄求解函數(shù)時的一系列迭代點，其中初始迭代點為（-1.2，1.0），最優(yōu)點為（1.0，1.0）。用Matlab R2012b 將這些迭代點描出并反映在Rosenbrock 函數(shù)的等值線圖上，便可清晰直觀地比較單調(diào)算法和非單調(diào)算法的迭代路徑和計算效率，結(jié)果見圖1~3。

對比分析圖1（a）和圖1（b），非單調(diào)的不定折線法求解的迭代次數(shù)小于單調(diào)的不定折線法，而且在圖1（a）中當(dāng)?shù)c接近最優(yōu)點時，收斂速度變得非常慢，相反在圖1（b）中當(dāng)?shù)c接近最優(yōu)點時，收斂速度加快。對比分析圖2（a）和圖2（b），非單調(diào)的Moré-Sorensen 法求解的迭代次數(shù)明顯小于單調(diào)的Moré-Sorensen 法，而且在圖2（a）中當(dāng)?shù)c接近最優(yōu)點時，收斂速度變得非常慢，相反在圖2（b）中當(dāng)?shù)c接近最優(yōu)點時，迭代路徑明顯有變化，收斂速度明顯加快。對比分析圖3（a）和圖3（b），非單調(diào)的截斷共軛梯度法求解的迭代次數(shù)明顯小于單調(diào)的截斷共軛梯度法，而且在圖3（a）中當(dāng)?shù)c接近最優(yōu)點時，收斂速度變得非常慢，相反在圖3（b）中當(dāng)?shù)c接近最優(yōu)點時，收斂速度明顯加快。因此，當(dāng)處理的函數(shù)出現(xiàn)峽谷形時，相比于單調(diào)的信賴域算法，非單調(diào)的算法在最優(yōu)點附近的收斂速度要快得多，數(shù)值計算效率更高，而且這種算法的數(shù)值計算是相對比較穩(wěn)定的。

圖1 不定折線法求解的迭代點圖

圖2 Moré-Sorensen 法求解的迭代點圖

圖3 截斷共軛梯度法求解的迭代點圖

3 結(jié)論

本文主要比較了解決信賴域子問題的幾種算法的數(shù)值計算效率，通過大量的數(shù)值計算得出截斷共軛梯度法在一定程度上計算效率優(yōu)于Moré-Sorensen 法以及不定折線法，而且在解決大規(guī)模問題時，其計算效率更是明顯高于其他兩種算法。此外在解決一些病態(tài)問題上（如Rosenbrock 函數(shù)），非單調(diào)的信賴域算法收斂性更強、數(shù)值計算效率更高。然而，本文所用到的測試函數(shù)還十分有限，若想更全面地評估各種信賴域子問題求解方法的數(shù)值計算效率，還須做進(jìn)一步的探究。