李安玭，劉海林

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

0 引言

對于無約束優(yōu)化問題：

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

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

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

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

其中0＜δ≤σ＜1.

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

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

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

對應的參數(shù)βk為：

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

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

1 參數(shù)t的選取與完整算法

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

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

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

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

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

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

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

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

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

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

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

2 全局收斂性

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

3 數(shù)值實驗

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

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

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

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

圖1 算法迭代次數(shù)的對比圖

圖2 函數(shù)值計算次數(shù)的對比圖

圖3 梯度值計算次數(shù)的對比圖

圖4 耗費的CPU時間對比圖

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