一個充分下降的修正PRP 型譜共軛梯度法

簡金寶, 宋 丹, 江羨珍

(廣西民族大學數學與物理學院，南寧 530006)

0 引言

共軛梯度法是求解光滑無約束優化問題min{f(x)|x ∈Rn}最有效的方法之一，其迭代公式的一般形式為

其中gk=g(xk) =?f(xk)為當前迭代點的梯度，βk為共軛參數，αk為步長。常用于產生步長的非精確線搜索準則有三種：

1) Armijo 線搜索準則，選擇步長αk=max{ρ0,ρ1,ρ2,···},0<ρ<1，滿足

2) 標準Wolfe 線搜索準則，即

3) 強Wolfe 線搜索準則，即

其中，(3)式中的參數滿足δ ∈(0,1)，(4)式及(5)式中的參數δ和σ滿足0<δ<σ<1。眾所周知，共軛參數βk對共軛梯度法的理論和數值性質有重要影響。著名的參數βk計算公式有[1–5]

不難推知

由(7)式可知，修正的JSJ 公式不僅保持了PRP 公式的結構和性能，并且傳承了FR方法的收斂性質。

譜共軛梯度法是共軛梯度法的一種推廣，其搜索方向結構為

其中θk稱為譜參數。它最大優點是通過共軛參數和譜參數的二維度調整使得搜索方向滿足某一預設條件，比如，充分下降條件或共軛條件等。特別是當譜參數θk>1 時，算法可獲得較大的下降量。較早的譜共軛梯度法由Birgin 和Martin′ez[8]提出，相應的譜參數為

隨后，譜共軛梯度法得到進一步研究，并且獲得了一些收斂性和數值表現良好的計算方法，詳見文獻[9—12]。

文獻[11]取定共軛參數為

再由牛頓方向和擬牛頓方程設計譜參數為

由(11)式和(12)式產生的譜共軛梯度法簡記為NA 方法。由NA 方法產生的搜索方向不依賴于任何線搜索均滿足充分下降條件，在強Wolfe 線搜索準則下證明了NA 方法的全局收斂性，獲得較好的數值效果。為了使方向dk的充分下降性不依賴于線搜索，文獻[12]在假設

的條件下，構造譜參數為

并由此建立了一類新的譜共軛梯度法，該方法在標準的Wolfe 線搜索準則下全局收斂，并且數值表現良好。

易見，由(13)式及(14)式構造的搜索方向dk恒滿足充分下降條件

基于(6)式、(13)式和(14)式，我們在第1 部分建立一個修正PRP 型譜共軛梯度算法，并證明算法的全局收斂性；在第2 部分對算法進行數值測試與比較，并報告測試結果。

1 算法及其收斂性

基于搜索方向(13)及強Wolfe 線搜索準則，我們給出修正PRP 型譜共軛梯度算法(簡記為JSJ 算法)的步驟如下：

初始步 任取初始點x1∈Rn，參數0<δ<σ< 1。給定終止精度?> 0。d1=?g1，置k:=1；

步驟1 若//gk//≤?，則停止。否則，轉入步驟2；

步驟2 采用強Wolfe 線搜索條件(5)求步長αk；

步驟3 按xk+1=xk+αkdk產生新的迭代點，計算gk+1:=g(xk+1)，并由(6)式、(13)式和(14)式計算搜索方向dk+1；

步驟4 令k:=k+1，返回步驟1。

為獲得JSJ 算法的全局收斂性，目標函數需要有以下兩個常規假設條件：

(H1) 目標函數f(x)在水平集Λ={x ∈Rn|f(x)≤f(x1)}上有界，其中x1為JSJ算法的初始點；

(H2) 目標函數f(x)在水平集Λ 的一個鄰域U 內可微，且其梯度函數g(x)滿足Lipschitz 條件，即存在L>0，使

下面引理所給出的是著名的Zoutendijk 條件[14]，其在下降迭代算法全局收斂性分析中起著重要作用。

引理1 設假設(H1)和(H2)成立，考慮一般迭代方法xk+1=xk+αkdk，若搜索方向dk滿足下降條件<0，步長因子αk滿足標準Wolfe 線搜索準則(4)，則

特別地，當搜索方向dk滿足充分下降條件時，有

基于充分下降性(15)式和引理1，可建立JSJ 算法的全局收斂性定理。

定理1 若假設(H1)和(H2)成立，則由JSJ 算法產生的點列xk滿足lim infk→∞//gk//=0。

進而由(14)式，有

結合強Wolfe 線搜索條件(5)以及充分下降性(15)式，得

另一方面，由(13)式，得dk=?θkgk+βkdk?1。對上式兩邊分別平方后得

對等式兩邊同時除以//gk//4并結合(17)式、(18)式以及充分下降性(15)式，得

由此遞推可知

因此

這與(16)式相矛盾，從而lim infk→∞//gk//=0 獲證。

2 數值試驗

為了檢驗JSJ 算法的有效性，本文對100 個算例進行數值實驗，并在相同的計算環境下，與五個相近的算法進行比較。他們分別是NA[11]和LFZ[12]譜共軛梯度法，數值效果好的三項共軛梯度法KD[15]，以及兩個帶有新型共軛條件的下降共軛梯度法HZ[16–17]和DK[18]。100 個測試算例的前50 個(從bard 到woods)取自CUTEr 問題集[19]，其余50 個問題取自測試問題集[20–21]，問題的維數在2～6 000 000 之間，所有測試都在強Wolfe 非精確線搜索準則(5)下完成。測試環境為Matlab R2016a, Windows 7 操作系統，DELL 電腦4GB 內存。相關選取參數為：δ=0.01, σ=0.1。本文算法的終止準則為以下兩者情形之一：

終止準則2)出現時認為該方法對相應例子失效，并記為“F”。

為了綜合比較，在試驗中，我們分別對迭代次數(Itr)，函數計算次數(NF)，梯度計算次數(NG)，CPU 計算時間(Tcpu)，精度//g?//五個指標進行觀察和比較，數值結果詳見表1 和表2。

表1 前50 個算例的數值試驗報告

續表

續表

表2 其余50 個算例的數值試驗報告

續表

同時，我們還采用Dolan 和Mor`e[22]性能圖對試驗效果進行直觀刻劃，圖1 至圖4 分別對應CPU 計算時間(Tcpu)，函數計算次數(NF)，梯度計算次數(NG)和迭代次數(Itr)的比較結果。圖中

其中size A 表示集合A 的元素個數，P表示由測試問題p構成的問題集，np表示問題集中問題個數，S表示由算法s組成的算法集，定義：tp,s=算法s在求解問題p所消耗的計算時間(或迭代次數或函數計算次數或梯度計算次數)，且給表1 中“F”的比率rp,s均賦值為2 max{rp,s:s ∈S}。性能圖的具體解釋參見文獻[22]。總體來說，ρ(τ)的曲線越居上，其對應方法的數值性能越好。

從表1 和表2，圖1 至圖4 可以看出，JSJ 算法成功地解決了96%的測試問題，是所有測試的6 個算法中占比最高的，同時，JSJ 算法在成功解決的問題中有約41%的算例在所考查的四個指標中占優，略高于KD 算法和LFZ 算法，明顯高于其余的三個算法。故JSJ 算法在我們所測試的100 個問題中的數值效果總體上要優于其他五個算法。

圖1 CPU 計算時間比較

圖2 函數計算次數比較

圖3 梯度計算次數比較

圖4 迭代次數比較