簡(jiǎn)金寶, 宋 丹, 江羨珍

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

0 引言

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

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

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

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

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

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

不難推知

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

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

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

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

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

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

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

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

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

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

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

1 算法及其收斂性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

進(jìn)而由(14)式，有

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

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

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

由此遞推可知

因此

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

2 數(shù)值試驗(yàn)

為了檢驗(yàn)JSJ 算法的有效性，本文對(duì)100 個(gè)算例進(jìn)行數(shù)值實(shí)驗(yàn)，并在相同的計(jì)算環(huán)境下，與五個(gè)相近的算法進(jìn)行比較。他們分別是NA[11]和LFZ[12]譜共軛梯度法，數(shù)值效果好的三項(xiàng)共軛梯度法KD[15]，以及兩個(gè)帶有新型共軛條件的下降共軛梯度法HZ[16–17]和DK[18]。100 個(gè)測(cè)試算例的前50 個(gè)(從bard 到woods)取自CUTEr 問(wèn)題集[19]，其余50 個(gè)問(wèn)題取自測(cè)試問(wèn)題集[20–21]，問(wèn)題的維數(shù)在2～6 000 000 之間，所有測(cè)試都在強(qiáng)Wolfe 非精確線搜索準(zhǔn)則(5)下完成。測(cè)試環(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)時(shí)認(rèn)為該方法對(duì)相應(yīng)例子失效，并記為“F”。

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

表1 前50 個(gè)算例的數(shù)值試驗(yàn)報(bào)告

續(xù)表

續(xù)表

表2 其余50 個(gè)算例的數(shù)值試驗(yàn)報(bào)告

續(xù)表

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

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

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

圖1 CPU 計(jì)算時(shí)間比較

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

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

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