改進共軛梯度法的收斂性

林 穗 華

廣西民族師范學院 教育科學學院，廣西 崇左 532200

解極小化問題min{f(x)|x∈Rn}的迭代法有多種，其中共軛梯度法由于無須用到2f(x)等n階矩陣數(shù)據(jù)，存儲需求少而特別適合大規(guī)模優(yōu)化問題[1-18]． 傳統(tǒng)共軛梯度法的迭代格式為：

xk+1=xk+αkdk

(1)

(2)

其中：dk為搜索方向，αk為步長因子，βk為參數(shù)，gk=f(xk)，sk=xk+1-xk． 不同的βk參數(shù)公式對應不同的共軛梯度法． 著名的PRP，HS，LS，F(xiàn)R，DY，CD方法的參數(shù)公式如下：

其中

相應的WYL，MHS，MLS方法都具有較好的收斂性．

(3)

其中：

這一修改方式能確保βk≥0，但卻無法滿足充分下降條件：?c∈(0，1)，使

(4)

然而某些類型共軛梯度法的收斂性依賴于充分下降條件，因此文獻[11]定理1只得將“滿足充分下降條件”作為預設前提． 事實上VPRP，VHS，VLS方法不滿足充分下降性，其全局收斂性仍無法保證．

受文獻[9-10，16-17]充分下降性策略的啟發(fā)，我們修改(3)式的分母，得到

(5)

(6)

(7)

其中常數(shù)μ>2． 我們將討論(1)，(2)式迭代法的收斂性，其中參數(shù)βk取自(5)，(6)或(7)式，步長因子αk考慮采用經(jīng)典的weak Wolfe-Powell(WWP)線搜索[2]及文獻[18]針對BFGS和PRP方法設計的modified weak Wolfe-Powell(MWWP)線搜索．

記參數(shù)為δ，σ的WWP線搜索條件為WWP(δ，σ)條件：

(8)

(9)

記參數(shù)為δ1，δ，σ的MWWP線搜索條件為MWWP(δ1，δ，σ)條件：

(10)

(11)

1 算法及性質

算法V-WWP

步驟1設定初值x1∈Rn，μ>2，0<δ1<δ<σ<1，ε>0，d1=-g1，k=1． 若‖gk‖≤ε，則停止．

步驟2計算αk滿足WWP(δ，σ)條件(8)和(9)式．

步驟3由(1)式計算xk+1． 若‖gk+1‖≤ε，則停止．

步驟4由(5)，(6)或(7)式計算βk+1，由(2)式計算dk+1．

步驟5置k=k+1，轉步驟2．

在算法V-WWP框架中，將步驟2改為計算αk滿足MWWP(δ1，δ，σ)條件(10)和(11)式，則得到V-MWWP算法．

定理1算法V-WWP生成的序列βk，gk，dk滿足0≤βk和充分下降條件(4)．

(12)

又有

(13)

(14)

(15)

從而可得

進一步可得

定理1得證．

2 原理與假設

證明算法的收斂性需要用到以下假設和引理．

假設：

‖g(x)-g(y)‖≤L‖x-y‖ ?x，y∈N

(16)

引理1[3，6]考慮滿足如下條件的任一共軛梯度法(1)-(2)：

(a)βk≥0．

(b) 搜索方向滿足充分下降條件(4)．

(c) 以下Zoutendijk條件成立：

(17)

以下算法收斂性分析中均假設‖gk‖≠0，否則算法已得到f(x)的穩(wěn)定點而終止．

3 全局收斂性

定理2若假設和成立，則算法V-WWP生成的序列gk，dk滿足Zoutendijk條件(17)．

從而可得

(18)

由(8)，(18)式可得

(19)

(19)式兩端對k=1，2，…求和，可得

從而可知(17)式成立，定理2得證．

定理3若假設和成立，βk，gk，dk為算法V-WWP生成的序列，則βk滿足性質(*)．

證由(9)式和定理1，可得

‖gk-1‖2≥c(1-σ)‖gk-1‖2

從而可得

根據(jù)算法V-WWP步驟(4)βk的取法，可知

(20)

由(12)和(20)式，可得

設‖sk-1‖≤λ，則由(16)，(20)式及

可得

定理3得證．

由定理1-3以及引理1，可得如下定理4．

定理4若假設和成立，gk為算法V-WWP生成的序列，則

定理5若αk滿足MWWP(δ1，δ，σ)條件，則αk也滿足WWP(δ-δ1，σ)條件．

(21)

(22)

由定理5，類似定理4的證明過程，可得算法V-MWWP全局收斂，即如下定理6成立．

定理6若假設和成立，gk為算法V-MWWP生成的序列，則

4 數(shù)值實驗

利用文獻[19]的部分測試問題，維數(shù)分別取1 000，5 000，10 000，對算法PRP(采用MWWP搜索)和算法V-MWWP進行數(shù)值試驗． 試驗環(huán)境為：ThinkPad E580，Intel(R) Core(TM) i5-8250U CPU@1.60GHz，RAM 8.00GB，Windows 10，Matlab R2016a． 算法參數(shù)δ1=0.05，δ=0.1，σ=0.9，μ=5.1，ε=10-6． 終止條件為‖gk‖≤10-6或迭代次數(shù)N≥1 000． 計算結果見表1，其中t表示算法所耗CPU時間，NaN表示算法終止時未滿足‖gk‖≤ε．

表1 數(shù)值結果

續(xù)表1

應用文獻[20]的技術得到算法PRP與算法V關于迭代次數(shù)和CPU時間比較的效能圖(圖1和圖2)． 可見算法V對這些測試問題的數(shù)值表現(xiàn)比算法PRP更好些．

圖1 算法迭代次數(shù)效能圖

圖2 算法CPU時間效能圖