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

簡金寶, 宋 丹, 江羨珍

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

0 引言

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

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

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

2) 標(biāo)準(zhǔn)Wolfe 線搜索準(zhǔn)則，即

3) 強Wolfe 線搜索準(zhǔn)則，即

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

不難推知

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

譜共軛梯度法是共軛梯度法的一種推廣，其搜索方向結(jié)構(gòu)為

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

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

文獻[11]取定共軛參數(shù)為

再由牛頓方向和擬牛頓方程設(shè)計譜參數(shù)為

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

的條件下，構(gòu)造譜參數(shù)為

并由此建立了一類新的譜共軛梯度法，該方法在標(biāo)準(zhǔn)的Wolfe 線搜索準(zhǔn)則下全局收斂，并且數(shù)值表現(xiàn)良好。

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

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

1 算法及其收斂性

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

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

步驟1 若//gk//≤?，則停止。否則，轉(zhuǎn)入步驟2；

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

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

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

為獲得JSJ 算法的全局收斂性，目標(biāo)函數(shù)需要有以下兩個常規(guī)假設(shè)條件：

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

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

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

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

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

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

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

進而由(14)式，有

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

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

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

由此遞推可知

因此

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

2 數(shù)值試驗

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

終止準(zhǔn)則2)出現(xiàn)時認(rèn)為該方法對相應(yīng)例子失效，并記為“F”。

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

表1 前50 個算例的數(shù)值試驗報告

續(xù)表

續(xù)表

表2 其余50 個算例的數(shù)值試驗報告

續(xù)表

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

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

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

圖1 CPU 計算時間比較

圖2 函數(shù)計算次數(shù)比較

圖3 梯度計算次數(shù)比較

圖4 迭代次數(shù)比較