一類改進(jìn)的譜共軛梯度法

陳秀芳，李 鋒

(1.滇西科技師范學(xué)院 數(shù)理學(xué)院 ，云南 臨滄 67700;2.云南師范大學(xué) 數(shù)學(xué)學(xué)院 ，云南 昆明 650500)

考慮如下無約束優(yōu)化問題

(1)

其中：函數(shù)f:Rn→R上是連續(xù)可微函數(shù).共軛梯度法(CG法)是Stiefel與Hestenes于1952年提出了一種求解線性方程組的算法,隨后，Reeves與Fletcher在1964年將該方法推廣到求解非線性優(yōu)化問題，提出了如下非線性共軛梯度法[1]：

xk+1=xk+αkdk,k=0,1,2，

(2)

其中xk為當(dāng)前迭代點(diǎn)，搜索步長(zhǎng)αk由合適的線搜索(精確和非精確)確定，搜索方向dk由以下公式給出：

(3)

共軛梯度法具有占用存儲(chǔ)空間小、收斂速度快的特點(diǎn)，廣泛應(yīng)用于控制科學(xué)、工程管理和流程研究等領(lǐng)域，在近年來興起的大數(shù)據(jù)科學(xué)顯示出特別的吸引力，因而一直受到學(xué)者們的廣泛關(guān)注，相關(guān)研究持續(xù)不斷.

共軛梯度法的改進(jìn)線索大致分為2條，一條是修改共軛系數(shù)βk(稱這類算法為經(jīng)典CG算法)，另一條是融合譜最速下降法的思想，引入譜系數(shù)(稱這類算法為譜共軛梯度法).

經(jīng)典CG算法分為2類：第1類包括Fletcher-Reeves(βkFR)[2]、Dai Yuan(βkDY)[3]公式如下：

(4)

其中‖·‖為Euclidean范數(shù)，yk=gk+1-gk，這些方法有很好的收斂性，然而數(shù)值性能卻不是很好.另一類包括Polak-Ribiére-Polyak(βkPRP)[4]、Hestenses-Stiefel(βkHS)[5]、Liu Storrey(βkLS)[6]，它們的βk公式分別如下:

(5)

這類方法收斂性分析不是很理想，然而數(shù)值實(shí)驗(yàn)結(jié)果較為良好，且PRP方法和HS方法被公認(rèn)為最有效的CG法.鑒于上述2類方法優(yōu)缺點(diǎn)互補(bǔ)的特點(diǎn)，學(xué)者們提出了把2種系數(shù)組合起來的混合共軛梯度法.2006年Wei等[7]提出一個(gè)新的共軛參數(shù)βk，βk與經(jīng)典的PRP公式有類似的形式，并且首次將線性組合的思想引入經(jīng)典共軛梯度法中，公式如下：

(6)

(7)

(8)

韋等在復(fù)雜線搜索下建立了新的PRP型共軛梯度法，并討論相關(guān)的問題.

鑒于經(jīng)典CG算法是基于最速下降的改進(jìn)算法，2001年Birgin和Martinez[12]基于譜梯度法提出了譜共軛梯度法(SCG法)，即在經(jīng)典共軛梯度法的搜索方向dk的迭代格式(3)中引入譜系數(shù)δk：

(9)

對(duì)應(yīng)的參數(shù)分別為：

(10)

景書杰等在Armijo線搜索下證明算法全局收斂，綜合前面2條線索，得到一個(gè)好的結(jié)果.沿著這個(gè)線索，大有工作可做.有關(guān)譜共軛梯度法的其他變種還很多，可以參看文獻(xiàn)[17-21].

文中深受上述討論的啟發(fā)，尤其是文獻(xiàn)[11]和[16]中2個(gè)參數(shù)的構(gòu)造.從這些算法的發(fā)展可以發(fā)現(xiàn)，確定不同的系數(shù)，算法的表現(xiàn)不一樣.文中嘗試用前面的思路確定2個(gè)系數(shù)的新公式，并討論他們的收斂性及相關(guān)問題，其它工作安排如下：第1節(jié)算法及其下降性，第2節(jié)算法的全局收斂性，第3節(jié)數(shù)值實(shí)驗(yàn)，第4節(jié)全文總結(jié).

1 算法及其下降性

(11)

其中，

(12)

該算法采用修正的強(qiáng)Wolfe線搜索求步長(zhǎng)

其中,0<ρ<σ<1.

算法1：

譜共軛梯度法算法流程如下：

Step 0 初始值x0∈Rn,ε>0,令μ>0,λ>0,0<ρ<σ<1,k:=1,d1=-g1,Step 1 計(jì)算gk,若‖gk‖≤ε,則停止,否則轉(zhuǎn)Step 2,Step 2 用強(qiáng)Wolfe線搜索公式計(jì)算αk,Step 3 用式(11),(12)分別計(jì)算dk,βFk,δk,Step 4 令xk+1=xk+αkdk求gk+1,并用式(11)求βFk+1,使得dk+1=-δk+1gk+1+βFk+1dk,使得k:=k+1,轉(zhuǎn)Step1.

算法的收斂性證明需要以下假設(shè)條件成立

假設(shè)A[21]：

(i)定義目標(biāo)函數(shù)f(x)在水平集L0={x∈Rn|f(x)≤f(x0)}上有下界，x0是初始點(diǎn).

(ii)目標(biāo)函數(shù)f(x)二次連續(xù)可微，它的梯度函數(shù)g(x)是Lipschitz連續(xù)，則存在常數(shù)L>0,使得：‖g(x)-g(y)‖≤L‖x-y‖,?x,y∈N.

(iii)目標(biāo)函數(shù)f(x)在Rn中是二階連續(xù)可微的一致凸函數(shù).

以下給出算法A的充分下降條件.在共軛梯度法的收斂性分析中，通常都有以下幾個(gè)經(jīng)典的引理，文中證明了相應(yīng)的結(jié)果.

引理1.1假設(shè){gk}和{dk}是由算法1產(chǎn)生的序列，則滿足充分下降條件

1) 對(duì)?k≥1，如果‖dk‖≠0,‖gk‖≠0，則有

(13)

由(13)式得

于是有

綜上，引理1.1得證.

(14)

證明：由式(12)和假設(shè)A得

(15)

將‖gk+1‖>3Lαk‖dk‖代入(15)式即得所要結(jié)論.

引理1.3若假設(shè)A成立，?k>0,gk,dk≠0，則由算法1生成的序列{gk}和{dk}滿足Zoutendjik條件

(16)

此外，由Lipschitz條件有 (gk+1-gk)Tdk≤αkL‖dk‖2.

以上2式結(jié)合得

(17)

(18)

即引理1.3成立

2 算法的全局收斂性

根據(jù)前面的引理部分，也能得到如下的收斂性證明.

證明：反證法，若結(jié)論不成立，就一定有常數(shù)ζ>0，滿足任給k≥0,

‖gk‖≥ζ.

(19)

顯然與引理1.3相矛盾，故定理2.1成立.

3 數(shù)值實(shí)驗(yàn)

本節(jié)中，為測(cè)試新方法的數(shù)值計(jì)算效果而建立數(shù)值實(shí)驗(yàn)，在強(qiáng)Wolfe線搜索下，文中的譜共軛梯度為記為PCSWP；在一般Wolfe線搜索下，建立共軛梯度法的數(shù)值實(shí)驗(yàn)，記為CWWP,分別與文獻(xiàn)[16]的方法作對(duì)比，記為JPSWP法，測(cè)試問題選自文獻(xiàn)[7]中的部分函數(shù)，算法的終止條件為‖gk‖≤10-6，或算法迭代次數(shù)超過 10 000，所有代碼均在Matlab2016a中進(jìn)行，數(shù)值結(jié)果以NI,NF,NG的形式給出，NI是算法迭代次數(shù)，NF是目標(biāo)函數(shù)計(jì)算次數(shù)，NG是梯度函數(shù)計(jì)算次數(shù)，“*”指算法運(yùn)行失效，經(jīng)過各種嘗試和嚴(yán)格的對(duì)比后，各參數(shù)的取值如下：PCSWP法中的參數(shù)μ=0.01,λ=0，CWWP法中參數(shù)μ=0.01,λ=0，而文獻(xiàn)[16]中作者只是在Armijo線搜索下分析算法的全局收斂性，并未進(jìn)行數(shù)值實(shí)驗(yàn)，故本文在強(qiáng)Wolfe線搜索下建立，且μ=1.1

各測(cè)試結(jié)果如表1：

表1 不同問題各算法測(cè)試結(jié)果表

續(xù)表1

從表格中可以看出，對(duì)于絕大部分測(cè)試問題，在強(qiáng)Wolfe線搜索下，本文提出的譜共軛梯度法(PCSWP)比文獻(xiàn)[16]中的譜共軛梯度法(JPSWP)更有效，算法更具有競(jìng)爭(zhēng)力，算法的迭代次數(shù)、目標(biāo)函數(shù)的計(jì)算次數(shù)和梯度函數(shù)計(jì)算次數(shù)等方面均能達(dá)到最小.極少數(shù)測(cè)試問題上，求解GAUSS函數(shù)和WATSON函數(shù)時(shí)，JSWP法更有效；另外，本文在進(jìn)行數(shù)值實(shí)驗(yàn)時(shí)，放寬線搜索條件，在一般Wolfe線搜索下，CWWP法比JSWP法和PCSWP法更有效；還有極少數(shù)問題，是無論選什么方法，測(cè)試結(jié)果都一樣.綜上，本文提出的譜共軛梯度法更有效，具有更好的數(shù)值性能.

4 結(jié)語