一種充分下降的共軛梯度法及其收斂性

高前明

(南京財經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院, 江蘇 南京 210023)

0 引言

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

(1)

其中f:Rn→R是連續(xù)可微的目標函數(shù),g(x)=f(x)是f(x)的梯度.在求解無約束優(yōu)化問題(1)的眾多經(jīng)典算法中,共軛梯度法是一種備受研究者青睞的優(yōu)化算法.由已知的初始點x0∈Rn,利用共軛梯度法可以得到如下迭代點列{xk}:

xk+1=xk+αkdk

(2)

其中αk>0為每一次迭代的搜索步長,由某種線搜索得到,其中有較為經(jīng)典的弱Wolfe線搜索,

(3)

其中0<δ<σ<1.

dk為每一次迭代的搜索方向,其定義為

(4)

其中g(shù)k表示g(xk),βk是一個標量參數(shù),用來調(diào)整每次迭代共軛梯度法的搜索方向.容易看出,βk的選取對共軛梯度法的全局收斂性和數(shù)值效果有較大影響.目前被廣泛使用的βk的選取公式有如下4種:

分別被稱為Fletcher-Reeves(FR)[1], Polak-Ribiere-Polyak(PRP)[2], Hestenes-Stiefel(HS)[3], Dai-Yuan(DY)[4],其中,‖·‖表示歐幾里得范數(shù).

眾所周知,上述4種方法的收斂性質(zhì)和數(shù)值效果有較大差異.通常FR方法和DY方法有良好的收斂性質(zhì),但數(shù)值實驗效果不如PRP和HS方法;PRP和HS方法雖然數(shù)值效果好,但即使采用精確線搜索步長也無法保證它們的全局收斂性.因此,在這些經(jīng)典算法的基礎(chǔ)上,也有許多修正的共軛梯度法被相關(guān)研究者相繼提出[5],并且有收斂性和數(shù)值效果都較為理想的方法.JIANG[9]等人提出了修正的DY(MDY)和修正的FR(MFR)共軛梯度法[9],它們均滿足充分下降條件:

(5)

Tsegay[10]等人在JIANG和JIAN研究的基礎(chǔ)上,提出一種新充分下降的共軛梯度法(SDCG),在多種線搜索下,它滿足充分下降性式(5),并且在弱Wolfe線搜索下,證明了它的全局收斂性.文[10]中提出的算法βk的表達式為

(6)

2006年，WEI[11]等人提出了一種修正的PRP(MYL)共軛梯度法,并滿足充分下降性(5)式和全局收斂性.該算法中參數(shù)βk的表達式為

(7)

基于MYL和SDCG這兩種修正的共軛梯度法,本文提出一種新的共軛梯度法,在多種線搜索下,它滿足充分下降性,并且在弱Wolfe線搜索下,容易證明它的全局收斂性.

1 算法及其性質(zhì)分析

1.1 算法

通過修正βk,提出一種新的充分下降的共軛梯法,其參數(shù)βk表達式如下:

(8)

為了方便,NCG用來表示本文提出的新型共軛梯度法,并基于弱Wolfe線搜索,給出如下算法步驟:

算法1 初始化給定ε>0,δ∈(0,1),σ∈(δ,1),x0∈Rn.令d0=g0,k=0.

步驟1: 若‖gk‖≤ε,則停止;否則,進入步驟2；

步驟2: 通過使用弱Wolfe線搜索確定步長αk；

步驟3: 更新迭代xk+1:=xk+αkdk；

步驟5: 令k:=k+1,并返回到步驟1.

1.2 算法的充分下降性

通過下面引理,可以得出新方法在多種線搜索下的充分下降性.

引理1 在某種線搜索下,考慮共軛梯度法中的βk為表達式(8),則充分下降條件式(5)成立.

對于任意兩個向量μ和ν,有

(9)

結(jié)合式(8),可得

1.3 算法收斂性

為保證算法的全局收斂性,給出如下假設(shè)：

(H1) 水平集Λ={x∈Rn|f(x)≤f(x0)};

(H2) 目標函數(shù)f(x)在水平集Λ上是連續(xù)可微有下界的,并且它在梯度水平集Λ上是Lipschitz連續(xù)的.即存在一個常數(shù)L>0,使得,

‖g(x)-g(y)‖≤L‖x-y‖,?x,y∈Λ

(10)

成立.

引理2(Zoutendijk條件)[12]假設(shè)(H1)和(H2)成立,dk為共軛梯度法的下降方向,并且步長αk滿足弱Wolfe條件(3),則有

(11)

證明由式(3)中的第二個式子和Lipschitz條件,得

(12)

所以

(13)

(14)

將上式不等號兩邊分別對k求級數(shù),并利用{f(xk)}單調(diào)不增有下界的性質(zhì),得

(15)

證畢.

由引理2,即可得到下面的定理.

定理1 在假設(shè)(H1)和(H2)成立的條件下,點列{xk}由算法1產(chǎn)生，則

(16)

證明假設(shè)式(16)不成立,則存在一個常數(shù)ρ>0,使得‖gk‖2≥ρ,?k≥0.由式(4)和式(8),有

(17)

將式(17)兩邊同時平方,可得

(18)

從而,由式(5)和式(8)可得

因此

從而有

由引理2,定理1得證,說明此方法具有全局收斂性.

2 數(shù)值實驗

本節(jié)通過數(shù)值實驗來說明NCG算法的有效性.實驗測試在PC機上完成,PC機配置:1.80GHzCPU,8GB內(nèi)存, windows10家庭中文版操作系統(tǒng).編程軟件為MatlabR2018a.

測試對象:函數(shù)Example和來自Neculai[13]的函數(shù)(見表1),Example的表達式如下:

x1=(x11,x12,…,x1n)=(3,3,…,3).

測試參數(shù):δ=0.4,σ=0.6,ε=10-6.

終止條件:‖gk‖≤ε=10-6或迭代次數(shù)I>1000.

分別采用本文NCG算法和SDCG算法[10]兩種算法求解上述測試問題.測試結(jié)果見表1.

表1 本文NCG算法和SDCG算法的測試結(jié)果

在迭代次數(shù)和運行時間兩個方面,NCG算法的數(shù)值實驗效果都要優(yōu)于SDCG算法，實驗結(jié)果如圖1和圖2所示.此外,在充分下降性的理論分析方面,SDCG算法的下降性取決于參數(shù)μ的取值范圍,而本文所提的NCG算法,不依賴于其他參數(shù)的取值范圍,即具有自動下降的性質(zhì).綜上,NCG算法是一種有效的新型共軛梯度法.

圖1 算法的迭代次數(shù) 圖2 算法的運行時間