Wolfe線搜索下的兩類修正FR譜共軛梯度法

夏麗娜朱志斌

(1.桂林電子科技大學數(shù)學與計算科學學院，廣西桂林541004;2.廣西高校數(shù)據(jù)分析與計算重點實驗室，廣西桂林541004)

1.引言

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

其中f:Rn→R為連續(xù)可微目標函數(shù)，其梯度函數(shù)記為g:Rn→Rn.共軛梯度法具有算法結構簡單、所需要的計算存儲量空間少等優(yōu)點，其一般迭代格式為:

其中xk是第k次迭代點，αk是搜索步長，dk是搜索方向，βk是共軛參數(shù).關于βk的著名公式有

這里yk－1=gk-gk－1，‖·‖為歐氏范數(shù).上面對應的算法分別是Flecher-Reeves(FR)方法[1]、Dai-Yuan(DY)方法[2]、Conjugate-Descent(CD)方法[3]、Polak-Ribi`ere-Polyak(PRP)方法[4，5]、Hestenes-Stiefel(HS)方法[6]和Liu-Storey(LS)方法[7].對于非凸的目標函數(shù)，這六個方法在數(shù)值表現(xiàn)和收斂性上有很大的差別.其中，F(xiàn)R方法、DY方法和CD方法具有良好的收斂性質，而PRP方法、HS方法和LS方法具有良好的數(shù)值表現(xiàn)性質.為了尋求兼具良好數(shù)值實驗和收斂性質的方法，研究者在上述方法的基礎上進行了大量的研究，對βk進行改進推出具有不同效果的方法.如文[8]提出一種修正的PRP共軛梯度法，文[9]提出了兩種修正的DY共軛梯度法，文[10]基于Dai-Liao參數(shù)提出三種不同的共軛梯度法.

文[11-13]提出一種譜共軛梯度法，其方向迭代由(1.3)式推廣為

其中θk為譜參數(shù).

文[14]中討論了如下形式的譜共軛梯度法：

其中c為大于0的參數(shù).

文[15]中討論了如下形式的譜共軛梯度法：

其中rk為向量gk與dk－1的夾角.

文[16]在FR方法的基礎上提出了兩種修正的FR譜共軛梯度法如下：

其中rk為向量gk與dk－1的夾角.

受文[14-16]的啟發(fā)，以及在文[16]中βk，和的基礎上，提出了新的共軛參數(shù)和譜參數(shù)：

其中φk為向量gk與gk－1的夾角.

本文采用標準的Wolfe線搜索：

其中0＜δ＜σ＜1.

本文提出兩個修正的譜共軛梯度法，基于(1.8)，(1.9)，(1.11)和(1.12)的譜共軛梯度法稱為ZFR1方法，基于(1.8)，(1.10)，(1.11)和(1.12)的譜共軛梯度法稱為ZFR2方法.

為了證明ZFR1方法和ZFR2方法具有全局收斂性，要求目標函數(shù)f(x)滿足如下假設:

(H1)f(x)在水平集Ω={x∈Rn|f(x)≤f(x1)}上有下界.

(H2)f(x)在Ω的一個鄰域內是連續(xù)可微的，且它的梯度g(x)滿足Lipschitz條件，即存在一個常數(shù)L＞0，使得‖g(x)-g(y)‖≤L‖x-y‖，?x，y∈Ω.

本文余下內容組織如下:在第2節(jié)和第3節(jié)中，將給出ZFR1方法和ZFR2方法在標準Wolfe線搜索下的性質及其全局收斂性;在第4節(jié)中，數(shù)值結果驗證了這兩個方法是有效的.

2.ZFR1方法及其全局收斂性

算法2.1(ZFR1譜共軛梯度算法)

步1 給定初值x1∈Rn，δ∈(0)，ε≥0，d1=-g1，k=1;若‖gk‖≤ε，停止.

步2 由Wolfe線搜索準則計算步長因子，即αk滿足(1.11)和(1.12)式.

步3 由(1.2)式計算xk+1，若‖gk+1‖≤ε，停止.

步4 由(1.8)式計算βk+1，(1.9)式計算θk+1，由(1.4)式計算dk+1.

步5k:=k+1，轉步2.

引理2.1若假設(H1)和(H2)成立，考慮ZFR1方法，βk和分別由(1.8)式和(1.9)式產生，步長αk滿足標準Wolfe線搜索準則，則

證若k=1，d1=-g1，則有

結論成立.對k＞1，假設由(1.12)式易得

設φk為向量gk與gk－1的夾角，則

若βk＞0，由(1.4)，(1.8)，(1.9)，(1.12)式，并將(1.4)式兩端分別與gk作內積可得

若βk=0，則結合可知

從而，由數(shù)學歸納法知，?k≥10成立，并且得到βk≥0.

引理2.2若假設(H1)和(H2)成立，考慮ZFR1方法，步長αk滿足標準Wolfe線搜索準則(1.11)，(1.12)式，則可推出

證引理2.1已證βk≥0，下證不等式右邊也成立.

定理2.1若假設(H1)和(H2)成立，考慮ZFR1方法，dk是下降方向，步長αk滿足標準Wolfe線搜索準則.則有Zoutendijk條件成立，即

證由引理2.1可知0.

由(1.12)式及假設(H2)，可得

又由于fk為單調遞減的收斂數(shù)列，再結合上式可得

對上式兩端求和得

因此，結論成立.

定理2.2若假設(H1)和(H2)成立，考慮ZFR1方法，步長αk滿足標準Wolfe線搜索且引理2.1成立，θk是(1.9)式中生成的序列，則

證用反證法證明.若假設(2.5)式不成立.則存在常數(shù)r＞0，使得對任意k≥1，有

對(1.4)式移項得dk+θkgk=βkdk－1，兩端取模平方并利用(2.3)式可得

由上式遞推，并利用d1=-g1和(2.6)式可得

對上式兩端分別求和得

這與定理2.1矛盾，所以定理2.2成立.

3.ZFR2方法及其全局收斂性

算法3.1(ZFR2譜共軛梯度算法)

步1 給定初值x1∈Rn，δ∈(0，)，ε≥0，d1=-g1，k=1;若‖gk‖≤ε，停止;

步2 由Wolfe線搜索準則計算步長因子，即αk滿足(1.11)和(1.12)式;

步3 由(1.2)式計算xk+1，若‖gk+1‖≤ε，停止;

步4 由(1.8)式計算βk+1，(1.10)式計算θk+1，由(1.4)式計算dk+1;

步5k:=k+1，轉步2.

引理3.1若假設(H1)和(H2)成立，考慮ZFR2方法，βk和分別由(1.8)式和(1.10)式產生，步長αk滿足標準Wolfe線搜索，則搜索方向dk滿足如下不等式

證若k=1，d1=-g1，則有

結論成立.

對k＞1，假設0，下證0.

由(1.12)式易得

設φk是gk與gk－1的夾角，則cosφk=

1)若βk=0，則由(1.4)式可得

2)若βk＞0，則由(1.4)式可得

由數(shù)學歸納法知引理3.1成立.

定理3.1若假設(H1)和(H2)成立，考慮ZFR2方法，dk是下降方向，步長αk滿足標準Wolfe線搜索準則.則有Zoutendijk條件成立，即

由引理3.1、定理3.1和定理2.2，可得以下全局收斂定理成立.

定理3.2若假設(H1)和(H2)成立，考慮ZFR2方法，θk是(1.10)式中的生成的序列，gk由ZFR2方法產生，則

4.數(shù)值實驗

為檢測ZFR1方法和ZFR2方法的數(shù)值效果，我們在文[17]中選取了30個大規(guī)模無約束優(yōu)化測試函數(shù)的廣義或擴展形式.本文用ZFR1方法和ZFR2方法與文[1]中的FR方法、文[2]中的PRP方法、文[16]中的算法1和算法2進行比較，其中文[16]中的算法2用的是Armijo線搜索，其它用的是標準Wolfe線搜索.測試環(huán)境為Win10操作系統(tǒng)，Inte(R)Core(TM)i5-8250U CPU 1.60GHz 8.00GB內存.Wolfe線搜索中的參數(shù)為:δ=0.01，σ=0.9，ε=10－6，終止條件為‖gk‖≤ε或迭代次數(shù)超過10000.Armijo線搜索中的參數(shù)為:δ=0.001，ρ=0.8，ε=10－6，終止條件為‖gk‖≤ε或迭代次數(shù)超過10000.表1列出了30個函數(shù)的名稱，N是測試函數(shù)編號，function代表測試函數(shù).

表1 測試函數(shù)

表2顯示了所有數(shù)值結果，Dim代表測試函數(shù)維數(shù)，NI/NF/CPU time分別代表算法迭代次數(shù)，目標函數(shù)迭代次數(shù)和CPU運行時間.“-/-/-”代表存在數(shù)值溢出或者該方法在10000次迭代中未能收斂.此外，表2和表3中標記的黑色實驗數(shù)據(jù)是六種方法中測試數(shù)據(jù)的最小值.

表2 算法的數(shù)值結果

同時，我們還采用了Dolan和Mor′e[18]性能圖對實驗效果進行直觀刻畫.上面的圖1、圖2和圖3分別對應FR方法、PRP方法、算法1和算法2、ZFR1方法和ZFR2方法在算法迭代次數(shù)，函數(shù)迭代次數(shù)和CPU運行時間比較結果.可以看出，ZFR1方法和ZFR2方法在算法迭代次數(shù)、目標函數(shù)迭代次數(shù)和CPU運行時間等三個指標上均明顯優(yōu)于FR方法、PRP方法、算法1和算法2.

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

圖2 目標函數(shù)迭代次數(shù)性能圖

圖3 CPU運行時間性能圖

5.結果的討論

首先，從性能圖的特征可以知道，曲線越高，相應的方法越好.其次，從上面圖1-3、表2和表3可知，ZFR1方法和ZFR2方法成功地解決了100%的測試函數(shù)問題，而FR方法、PRP方法和算法1還沒有達到100%.ZFR1方法、ZFR2方法在和FR方法、PRP方法、算法1和算法2進行數(shù)值比較時，ZFR1方法和ZFR2方法的算法迭代次數(shù)、目標函數(shù)迭代次數(shù)和CPU運行時間都明顯減小.因此，可以看出，本文所提出的ZFR1方法和ZFR2方法具有比FR方法、PRP方法、算法1和算法2更好的數(shù)值結果.

表3 算法的數(shù)值結果

6.結束語

本文在已有共軛梯度算法求解無約束優(yōu)化問題的基礎上，提出了兩種新的譜共軛梯度法，并給出了在Wolfe線搜索條件下的全局收斂性證明.數(shù)值實驗結果表明，本文方法的迭代次數(shù)、目標函數(shù)迭代次數(shù)和CPU運行時間都優(yōu)于FR方法、PRP方法、算法1和算法2.數(shù)值實驗驗證了這兩個方法的有效性.