一類具有擬牛頓形式的共軛梯度法

李安玭，劉海林

(1.廣州工商學院，廣東 廣州 510850；2.廣東技術師范大學，廣東 廣州 510665)

0 引言

對于無約束優化問題：

其中Rn為n維歐氏空間，f:Rn→R連續可微且有下界，且gk=?f(xk)，通常用較低存儲且計算量更小的共軛梯度法來解決.其基本思想即通過迭代法來產生一點列：

其中αk為步長因子，由某種線搜索確定，通過該線搜索產生的搜索方向dk滿足：

這里的βk為算法參數，且gk=?f(xk).

顯然，在非線性共軛梯度法的求解過程中，不同的步長因子αk＞0和參數βk確定了不同的共軛梯度法.本文提出的新算法主要依賴于非精確線搜索方法中常用的Wolfe線搜索：

其中0＜δ≤σ＜1.

Perry[1]提出了一類共軛梯度法，它被許多學者認為是最有效且穩健的共軛梯度法之一[2]-[7]，其中的參數βk定義如下：

其中yk-1=gk-gk-1，sk=xk+1-xk.Perry提出的這個方法的優點在于，由(3)、(6)式產生的搜索方向具有擬牛頓形式:

實際上，Andrei作出此修正的目的是將Dai-Liao[9]提出的共軛梯度法（DL方法）中的近似矩陣Qk+1對稱化，DL方法中的Qk+1定義為：

對應的參數βk為：

受上述研究者的啟發，本文將提出一個類似Perry方法的共軛梯度法，其中的參數βk為：

本文將在第二部分給出新算法(NP方法)的擬牛頓形式，并對(12)式中的參數t作出討論及選取，最后給出完整的算法；在第三部分，算法的全局收斂性將建立在Wolfe線搜索的條件下進行論證分析；最終的數值實驗結果將在第四部分給出，表明算法的有效性和可行性.

1 參數t的選取與完整算法

考慮到NP方法中的參數βk由(12)式給出，通過結合Perry方法中的推導思路，我們給出以下分析:

因此，NP方法的擬牛頓形式可如下表示：

實際上，當步長因子αk滿足Wolfe線搜索條件中的(5)式時，我們可以得到.接下來，我們將對(15)式中的參數t的選取作出詳細討論.此前，建立在Saman Babaie-Kafaki[11]關于DL方法提出的理論基礎上，我們需要對近似矩陣Hk+1的相關性質作出討論.首先通過下面的這條定理，它表明了矩陣Hk+1的特征根都是實根，這一點對于保證矩陣Hk+1的正定性至關重要.

定理2.1令Hk+1如(15)所定義，則Hk+1是一個非奇異矩陣，且它的特征根為1(n-1重)、λ,其中λ=ak-bk，且

此外，矩陣Hk+1的特征根均為實根.

證明：不妨將矩陣Hk+1寫成如下形式：

為了保證近似矩陣Hk+1的正定性，也就是確保矩陣Hk+1的所有特征根都是正實數，即要求它們滿足ak-bk＞0.由此易知應滿足

因此，只要滿足(23)式，NP方法中的近似矩陣Hk1+就是正定的.并且，由(14)式我們可以得到：

其中常數c=min{λ,1}，也就是說由NP方法產生的搜索方向是充分下降的.

下面我們將通過討論如何保證算法的穩定性來選取適當的參數t，這一工作需要通過矩陣Hk+1的條件數來完成.對于一個矩陣A，其條件數定義為：

矩陣的條件數的意義在于研究一個矩陣在計算中的敏感性，即受其他數據影響的程度.一般來說，正交矩陣的條件數為1，若一個矩陣的條件數太大（遠大于1），我們就說這個矩陣是病態的.下面的性質表明了矩陣的條件數與矩陣特征根之間的關系.

2 全局收斂性

在這一部分，我們需要建立在以下基本假設之上對NP方法的全局收斂性作出分析.

3 數值實驗

由于DY方法具有良好的高效性和數值表現，是經典共軛梯度法中較優秀的方法之一，且前面提到的HZ方法也是具有擬牛頓形式的共軛梯度法，我們在這一部分對NP方法、DY方法和HZ方法在強Wolfe線搜索下進行數值實驗的對比，比較項為迭代次數、函數值計算次數、梯度值計算次數和CPU時間.(4)(5)式中的參數取值為：δ=0.01，σ=0.1.所選取的測試函數來源于文獻[16]，并且算法在或者迭代次數超過9999次時終止，測試所得的實驗數據將通過MATLAB進行繪圖處理得到直觀的比較圖像.測試代碼通過Visual Studio 2012編寫，運行環境為PC 2.7GHZ CPU，4G Memory，Windows 10操作系統，測試函數來源于Dolan and More[17]，他們在文中給出如下定義：P為測試函數集，S為算法集，nS和nP分別表示算法的個數和測試函數的個數，tp.s表示用某個算法s求解某個測試函數P所需的耗費，以及性能比

其中，性能比的定義可以理解為不同算法的耗費與其中最小耗費的比值.假設在所有的耗費中最小的耗費量為a,即min(tp,s:s∈S)=a，顯然，其他的耗費必定會大于a.并且，若性能比rp,s的值越小，則表明算法s求解測試函數P的耗費越小，數值表現則越好，反之則表明耗費越大，對應的數值表現即越差.另外，文中給出了性能比分布函數：

上式定義的性能比分布函數單調遞增且分段連續，結合性能比的定義式可以看到，值越小，算法求解測試函數的耗費就越小，數值表現也就越好.由(34)式可以發現，實驗圖中靠左的曲線反映的是算法中表現為優的數值與所有數值的比，靠右的曲線則反映算法能夠成功求解的測試函數與所有測試函數的比值.考慮整體的圖像，可以理解為，越靠上的曲線就具有越強的處理測試函數的能力，其對應的算法相較對比項越優，且越有效.

以下是通過MATLAB得到的三種方法的測試結果對比圖像：

圖1 算法迭代次數的對比圖

圖2 函數值計算次數的對比圖

圖3 梯度值計算次數的對比圖

圖4 耗費的CPU時間對比圖

由上面的數值結果對比圖像可以看到，NP方法的數值表現要比HZ方法和DY方法更好一些，證明本文提出的NP方法不僅具有足夠的穩定性，而且在應用于求解大規模無約束優化問題時是有效的.