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

袁 遠

（滁州城市職業學院教育學院，安徽滁州 239000）

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

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

1.1 非線性優化的信賴域算法對于無約束優化問題

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

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

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

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

為預測下降量。定義比值

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

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

（1）不定折線法

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

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

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

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

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

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

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

（2）Moré-Sorensen 法

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

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

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

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

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

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

（3）截斷共軛梯度法

考慮與問題（2）相對應的線性方程組

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

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

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

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

2 數值結果與分析

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

表1 試驗函數名稱

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

表2 M＝0 單調時的數值結果

表3 M＝10 非單調時的數值結果

續表2

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

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

表4 大規模測試問題

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

表5 n=100 的數值結果

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

表6 n=500 的數值結果

表7 n=1 000 的數值結果

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

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

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

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

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

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

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

3 結論

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