胡倩蕊，周光輝，曹尹平

（1.淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院 安徽 淮北 235000；2.南京財(cái)經(jīng)大學(xué)紅山學(xué)院 江蘇 南京 210006）

前 言

對于大規(guī)模無約束優(yōu)化問題

其中f是一階連續(xù)的可微函數(shù).共軛梯度法是解決問題（1）的一種很受歡迎的方法，憑借其計(jì)算簡單且存儲數(shù)據(jù)少，收斂迅速和二次終止性等特點(diǎn)，被廣泛應(yīng)用于求解大規(guī)模無約束優(yōu)化問題.其迭代形式為：

這里αk為步長因子，dk是搜索方向且dk被定義為

其中g(shù)k=?f(xk)為目標(biāo)函數(shù)f的梯度函數(shù)，βk為參數(shù)標(biāo)量。幾類經(jīng)典的βk［1-6］的形式有：

其中yk-1=gk-gk-1，‖·‖表示為歐幾里得范數(shù)。當(dāng)目標(biāo)函數(shù)f是嚴(yán)格凸二次函數(shù)且采用精確線搜索確定步長因子αk時(shí)，上述經(jīng)典共軛梯度法可以相互等價(jià)。

上述公式對應(yīng)的共軛梯度法分別為FR算法、HS 算法、PRP 算法以及DY 算法。其中FR和DY 算法具有良好的收斂性質(zhì)，而PRP和HS兩個(gè)算法具有良好的數(shù)值實(shí)驗(yàn)效果。因此，為了使算法具有好的收斂性質(zhì)又能達(dá)到良好的數(shù)值實(shí)驗(yàn)效果，許多專家學(xué)者在以上四類經(jīng)典共軛梯度法的基礎(chǔ)上做出改進(jìn)，得到了一些新的算法［7-14］。

近年來，人們構(gòu)造出一類充分下降的共軛梯度法，使得算法的充分下降性是獨(dú)立于線搜索的選擇，如Hager和Zhang［7］提出了著名的CG共軛梯度法?；谖墨I(xiàn)［8-9］，Cheng等［11］給出了一類具有充分下降性質(zhì)的共軛梯度法，使得搜索方向dk滿足充分下降性，且不依賴于線搜索αk的選擇和βk選取，大量的數(shù)值結(jié)果表明修正后的共軛梯度算法比傳統(tǒng)的共軛梯度算法更有效，其搜索方向被定義為：

但是當(dāng)線搜索αk的使用和參數(shù)標(biāo)量βk的選取不同時(shí)，可能會(huì)對算法的收斂性造成一定的影響。

本文的目的是構(gòu)造一種數(shù)值實(shí)驗(yàn)結(jié)果良好且在一定的條件下能保證是全局收斂的新算法，受文獻(xiàn)［11］和文獻(xiàn)［13］的啟發(fā)，我們對文獻(xiàn)［14］中參數(shù)βk做出修正，并給出了修正后的參數(shù)βk(t)，其中參數(shù)的形式如下:

這里

其中t ≥0，sk-1=αk-1dk-1，fk表示函數(shù)f在xk處的函數(shù)值。

當(dāng)搜索方向滿足（4）式時(shí)，若步長αk采用標(biāo)準(zhǔn)Armijo線搜索［15-16］，該算法是全局收斂的，數(shù)值實(shí)驗(yàn)表明該算法是有效的。

1 新算法及其框架

算法1

步驟1.給定初值：x1∈Rn,?ε＞0,d1=-g1,k=1。

步驟2.檢驗(yàn)終止條件：若‖gk‖ ＜ε，則停止。否則進(jìn)入步驟3。

其中βk滿足：

步驟4.由標(biāo)準(zhǔn)Armijo線搜索確定步長，αk=max{θj,j=0,1,2,…}滿足不等式：

步驟5.計(jì)算新點(diǎn).令xk+1=xk+αkdk，k=k+1，進(jìn)入循環(huán)返回步驟2。

2 全局收斂性

2.1 準(zhǔn)備

為了更好的證明新共軛梯度法具有較好的全局收斂性，我們給出使用的線搜索為標(biāo)準(zhǔn)Armijo線搜索，步長αk=max{θj,j=0,1,2,…}滿足不等式：

其中θ∈(0,1)，δ1∈(0,1)。

為了證明算法的全局收斂性，需要下面兩個(gè)常見假設(shè)。

假設(shè)（i）水平集Ω={x∈Rn|f(x)≤f(x1)}有界，其中x1為初始點(diǎn)。

由假設(shè)可知，存在正常數(shù)γ1使得下列不等式成立：

引理1 若假設(shè)（i）（ii）成立，βk(t)由算法1確定，步長αk滿足標(biāo)準(zhǔn)Armijo線搜索。如果存在ε0＞0對所有的k有

則有

證明：如果αk≠1，由線搜索過程我們知道θ-1αk不滿足（6），則有

由中值定理可知，存在μk∈(0,1)使得

因此有

g(x)滿足Lipschitz連續(xù)，μk∈(0,1)，c1=(1-δ1)θL-1，我們有

結(jié)合（6）有

則存在連續(xù)的M1＞0使得

當(dāng)αk=1，則

對等式gTkdk=-‖gk‖2使用Cauahy-Schwarz不等式，有

由（10）和（11）可知

再由（9）可知引理成立。

2.2 一致凸函數(shù)的全局收斂性

若假設(shè)（i）（ii）成立，由于f的一致凸性，存在連續(xù)的μ＞0

使得

或

由（12）和（13）可得

和

定理1 若假設(shè)（i）（ii）成立，f是一致凸函數(shù)，{xk}、{dk}是由算法1產(chǎn)生的序列，αk滿足標(biāo)準(zhǔn)Armijo線搜索，則或者gk=0對于某個(gè)k成立，或者

證明：假設(shè)結(jié)論不成立，即存在連續(xù)的ε＞0使得‖gk‖≥ε對所有的k都成立，

由中值定理得

這里ηk=xk+ξk(xk+1-xk)，ξk∈(0,1)，因此由（7）和上式可得

由（14）（15）可得

由（7）、（8）及（16）可得

再由（4）、（17）、（18）可得

則有

這與引理1矛盾，則假設(shè)不成立，定理成立。

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

測試算法1 的數(shù)值效果，并與文獻(xiàn)［13］中的算法MDL 以及經(jīng)典算法CG-Descent 進(jìn)行對比，算法的測試環(huán)境在Matlab 7.0，Win 7.0操作系統(tǒng)，Intel（R）Core（TM）I5-3210M CPU 2.50GHz 4.00GB內(nèi)存下進(jìn)行的。算法1以及算法MDL采用標(biāo)準(zhǔn)Armijo線搜索，而經(jīng)典算法CG-Descent采用的是標(biāo)準(zhǔn)Wolfe線搜索。其中算法1中Armijo 線搜索參數(shù)選取如下:θ=0.5，δ1=0.2，經(jīng)典算法中Wolfe 線搜索參數(shù)選取如下:δ=0.1，σ=0.9，ε=10-5。算法終止的條件為‖ ‖gk＜ε或迭代次數(shù)超過1000。在實(shí)驗(yàn)中，我們對算法1與算法MDL以及經(jīng)典算法CG-Descent分別在100維，1000維和2000維三種維數(shù)下，對函數(shù)進(jìn)行了測試比對。測試函數(shù)問題見表1，將數(shù)值結(jié)果繪制成Dolan 性能對比圖［17］（見圖1-6），其中algorithm1 所代表的就是算法1，MDL 所代表的是文獻(xiàn)［13］中算法。

圖1 100維迭代次數(shù)對比Fig.1 The number of Iterations comparison under 100 dimensions

表1 測試函數(shù)Table 1 Test functions

表2 不同維數(shù)下各算法實(shí)驗(yàn)的迭代次數(shù)Table 2 The number of iterations of each algorithm under different dimensions

續(xù)表2：

表3 不同維數(shù)下各算法實(shí)驗(yàn)的迭代時(shí)間Table 3 Iterations time of each algorithm under different dimensions

續(xù)表3：

圖2 100維迭代時(shí)間對比Fig.2 The number of Iterations time comparison under 100 dimensions

圖4 1000維迭代時(shí)間對比Fig.42 The number of iterations time comparison under 1000 dimensions

圖5 2000維迭代次數(shù)對比Fig.5 The number of iterations comparison under 2000 dimensions

圖6 2000維迭代時(shí)間對比Fig.6 The number of iterations time comparison under 2000 dimensions

4 數(shù)值結(jié)果分析

由算法1、算法MDL以及算法CG-Descent通過實(shí)驗(yàn)得到Dolan性能對比圖（圖1-6），令ρs(τ)為圖像縱坐標(biāo)，τ為橫坐標(biāo)。其性能圖的意義為：對每一種方法，曲線表示此方法在τ倍最佳時(shí)間內(nèi)好于其他方法的概率。因此在圖像最上方的曲線相對應(yīng)算法的數(shù)值效果最好。我們通過圖像可以看出，算法1 始終位于圖像最上方，但是在低維度時(shí)算法1與算法MDL出現(xiàn)了交叉，我們推測可能是由于在低維度下算法1的優(yōu)越性沒有體現(xiàn)出來，但是隨著維度的增高，由Dolan性能對比圖（圖3-6）可以清楚地發(fā)現(xiàn)不論是迭代所消耗的時(shí)間還是迭代次數(shù)，算法1是明顯優(yōu)于算法MDL以及經(jīng)典算法CG-Descent的。由此我們可以推斷算法1更加適合解決較大規(guī)模的無約束優(yōu)化問題。

圖3 1000維迭代次數(shù)對比Fig.3 The number of iterations comparison under 1000 dimensions