一種具有充分下降性的新混合型共軛梯度法 ①

鄭宗劍， 韓信，2

1.四川文理學院 數學學院， 四川 達州 635000； 2．西南大學 電子信息工程學院， 重慶 400715

本文考慮下面的無約束優化問題：

min{f(x)：x∈Rn}

(1)

xk+1： =xk+αkdk

(2)

這里xk∈Rn是一個解的第k次逼近，αk>0是由一種合適的線搜索所確定的步長，dk∈Rn是搜索方向， 其定義如下

(3)

其中：gk表示梯度g(xk)，βk∈R為共軛參數． 步長αk由標準的Wolfe線搜索

(4)

或者強Wolfe線搜索

確定， 其中0<δ<σ<1． 不同的共軛梯度法對應不同的共軛參數βk． 眾所周知的共軛梯度法包括Hestenes-Stiefel(HS)[2]，Polak-Ribière-Polyak(PRP)[3-4]，Dai-Yuan(DY)[5]，Liu-Storey(LS)[6]，Fletcher-Reeves(FR)[7]和Conjugate-Descent(CD)[8]， 它們所對應的共軛參數如下

其中yk-1： =gk-gk-1且‖·‖表示歐氏范數． 目標函數是一個嚴格凸二次函數并且步長由精確線搜索得到， 且在一般情形下， 它們的理論性質和數值表現不盡相同． 眾所周知， DY法、 CD法和FR法具有良好的收斂性質， 但它們的數值計算效果一般； 相反， PRP法、 HS法和LS法具備出色的數值表現， 但它們可能不收斂． 為了獲得收斂性數值效果的算法， 不少學者對共軛參數自身作了一些改進[9-10]和一些混合[11-12]． 本文主要考慮共軛梯度法的混合形式． 文獻[13]通過對PRP法和DY法進行凸組合， 得到一種新的共軛梯度法， 其共軛參數如下

受文獻[14]的啟發， 本文構造了一種新的混合共軛梯度法

(5)

這里

其中

1 NH+型共軛梯度算法

NH+算法

步驟1： 給定初始點x1和精度ε． 置k=1， 令d1=-g1．

步驟2： 若‖gk‖≤ε， 終止． 否則， 轉步驟3．

步驟3： 通過(3)式計算搜索方向dk．

步驟4： 由標準的Wolfe線搜索(4)確定步長因子αk．

步驟5： 由(2)式計算下一個迭代點xk+1．

步驟6： 令k： =k+1， 轉步驟2．

2 算法NH+的全局收斂性分析

為了論證算法NH+的收斂性， 給出了如下的基本假設．

目標函數的梯度函數在S的某鄰域U內Lipschitz連續， 即存在常數L>0， 對任意x，y∈U， 有‖g(x)-g(y)‖≤L‖x-y‖．

(6)

以Zoutendijk條件為基礎給出如下引理1． 這個引理在論證共軛梯度算法的全局收斂性過程中具有重要的作用．

證由標準Wolfe線搜索條件(4)， 知

另一方面， 由假設1和(2)式， 有

(gk-gk-1)Tdk-1≤αk-1L‖dk-1‖2

再結合算法NH+的下降性， 得

進一步由(4)式知

(7)

對(7)式從k=1，2，…，∞求和， 并注意目標函數f(x)有下界， 即知Zoutendijk條件成立． 因此， 結論得證．

從《意見》中還可以看出，國家層面上對生態補償的主體界定多集中在省、市政府和顯性受益人，對隱性受益人(生態利益的間接受益人)的付費義務和污染制造者的補償責任涉及較少。生態補償制度中財政轉移支付只是其中一個重要組成部分，但是，僅僅靠增加國家和地方政府的財政支出來進行生態補償，其有限的資金難以滿足生態環境可持續發展的需求；再者，若缺少對受益人的環保義務約束，相關人群不能有效履行義務，生態破壞者也沒有承擔相應的環境責任，將致使整個社會環境保護的意識提升緩慢，“搭便車”現象得不到有效制止。

下面的引理是論證算法NH+全局收斂性的關鍵． 這個引理的具體論證過程可參見文獻[17]．

接下來， 假設全局收斂性不在有限步發生．

證由dk≠0，gk≠0及充分下降性知，uk的定義有意義．

(8)

由(3)式和(5)式， 對任意k≥1， 有

uk=ρk+ωkuk-1

(9)

基于‖uk‖=‖uk-1‖=1和(9)式， 得

‖ρk‖=‖uk-ωkuk-1‖=‖ωkuk-uk-1‖

(10)

(11)

由Zoutendijk條件、 充分下降條件和(8)式知

(12)

現令N+為非零自然數集． 給定正常數λ和正整數Δ， 定義

證利用反證法論證． 假設存在Δ∈N+和常數k0， 對任意正常數λ和任意k≥k0， 有

(13)

b>1和η>0是性質(*)中的常數． 令λ=η， 由性質(*)和(13)式， 有

(14)

因此

(15)

對任意i≥1，k0≤l≤k0+iΔ， 存在i′， 使得

k0+i′Δ≤l≤k0+(i′+1)Δ≤k0+iΔ

再由b>1和(14)式得

(16)

其中c1=(2b2)Δ+1．

通過性質(*)、 (6)式、 (15)式和(16)式， 有

結合引理3和4， 利用文獻[14]的論證方法易得下面的定理1． 限于篇幅， 這里略去證明過程．

定理1若假設1和標準Wolfe線搜索都成立． 如果算法NH+滿足下面3個性質：

(p2) 充分下降性和Zoutendijk條件均滿足；

(p3) 性質(*)成立， 而且存在正常數M， 使得θk≤M‖sk-1‖．

則算法NH+全局收斂．

3 數值實驗

為了比較算法NH+與算法NYF[16]、 算法HCG+[14]、 算法PRP+[18]， 對文獻[19]中的63個測試函數進行實驗． 4種算法均利用Matlab程序實現， 且在Windows 7操作系統、 AMD Athlon(tm) II Dual-Core M320 CPU和2 GB內存環境測試運行． 常數σ=0.95，δ=0.000 1． 令pk=gk． 終止準則為‖gk‖≤10-6或迭代時間超過3 600 s． 部分數值結果見表1． 所有數值實驗具體結果請參見鏈接https： //weibo． com/2145331053/IsvzxrnEi?from=page_1005052145331053_profile&wvr=6&mod=weibotime&type=comment．

表1 部分數值實驗結果

此外， 利用文獻[20]提出的性能理論刻畫算法的計算效率和穩定性． 為此， 以迭代時間、 迭代次數為度量， 縱軸為性能指標Ps(t)， 描繪出下面的性能圖(圖1，圖2)． 實驗結果表明： NYF和PRP+在1.8 s前收斂速度都比NH+稍慢， 之后都與NH+接近， 并都達到穩定； HCG+比其他3種算法的收斂速度都慢； NH+一直快于其他3種算法， 最終與PRP+同時穩定． 原因可能是NH+法充分利用了PRP和NYF的加速特性以及FR的良好收斂性． 因此， NH+是一個有效的算法．

圖1 迭代時間算法性能圖

圖2 迭代次數算法性能圖