基于混合割線方程修正的BB梯度法

陳 旦

(重慶師范大學數學科學學院，重慶沙坪壩 401331)

0 引言

BB梯度法[1]是由Barzilai和Borwein在1988年提出的一種求解大規模無約束優化問題的新型梯度算法，考慮無約束優化問題：

(1)

其中f(x):Rn→R為連續可微函數，n是變量的個數.Barzilai和Borwein給出如下迭代格式：

xk+1=xk-αkgk

(2)

其中gk為f(x)在xk處的梯度，步長αk由下面兩個迭代公式決定，分別為：

(3)

其中sk=xk+1-xk，yk=gk+1-gk，該步長利用了目標函數f(x)前后兩個迭代點處的梯度值.同時，f(x)在二維凸二次情況下，該方法超線性速度收斂.

BB梯度法的提出極大地激發了人們重新研究梯度法的熱情，也取得了很大的進展.文獻[2]進一步證明了BB算法具有R-線性收斂速度，文獻[3]結合GLL非單調線搜索[4]將BB算法推廣到一般的無約束優化領域，提出了解無約束優化問題的BB算法并證明了該算法具有全局收斂性，數值結果表明，BB算法的數值性能比一些經典的共軛梯度法的要好.隨后，許多解一般無約束優化問題的修正BB梯度法被提出來，如文獻[5-8]等.

(4)

(5)

由于擬牛頓方程對擬牛頓法的理論和數值性能都有至關重要的影響，于是許多具有更好性質的修正擬牛頓方程也隨之發展起來，例如：對于一類修正的擬牛頓方程[10]：

(6)

其中t為參數.當t=0時，(6)式為標準擬牛頓方程；當t=1時，(6)式為2006年文獻[11]提出的修正的擬牛頓方程；當t=2時，(6)式為2011年文獻[12]提出的修正擬牛頓方程；當t=3且uk=sk時，(6)式為1999年文獻[13]提出的修正擬牛頓方程.

2013年，文獻[15]從插值的角度得到一個步長：

(7)

(8)

基于(6)式這一類修正的割線方程，可以發現該式中(gk+1+gk)Tsk和fk-fk+1前面的系數比為1∶2，同時也可以發現將修正的割線方程結合BB步長時，為了讓修正的步長包含有更多迭代點處的信息，就分別令uk=sk和uk=yk得到了很多修正的步長，那么有沒有一種更好的選取uk的方式，使得它既可以包含上述兩種情況來獲得一個步長，也可以讓所得到的步長比上面這一類修正的BB步長都要好？本文通過結合文獻[19]給出的混合割線方程，來改進文獻[15]中提出的方法.該步長的選取不僅利用了更多迭代點處的函數值和梯度值信息，而且其對應的算法能進一步改進一類經典的BB型方法.數值結果表明，所改進的方法數值性能要優于文獻[9,15]中一些經典的BB型方法.

1 新步長的提出

在這一節中，對BB梯度法給出一些新的步長選擇.首先，給出文獻[19]中提出的混合割線方程以及新步長的推導，然后再說明改進的新步長的優點.

文獻[19]中提出了一個修正的混合割線方程：

(9)

其中?k=(gk+gk+1)Tsk+2(fk-fk+1)，uk=(1-θk)yk+θksk，θk是一個混合參數且θk∈[0,1].該文獻給出了θk的一個選擇，即：

(10)

步驟1 若k=0，選擇一個初始的θk∈[0,1]；

步驟2 由式子(10)計算θk；

步驟3 若θk<0，則令θk=0；

步驟4 若θk>0，則令θk=1.

(11)

進一步，結合上述混合割線方程，將(9)式中的uk分別應用到(6)式中t=2和t=3情形下的修正割線方程下，可以得到另外兩個新的BB步長：

(12)

基于這些步長的選擇，結合文獻[15]中的算法框架提出一個修正的BB型算法，并且期待它們的結果比之前所改進的一類BB型算法更加有效.

2 修正的BB梯度算法及其全局收斂性

在這一節中，給出所修正的BB梯度法的算法描述，選擇初始步長后，利用Hager-Zhang非單調線搜索[20]來計算后面的近似步長，修正的BB梯度法(MSBB)步驟如下：

步驟0 給定初始值x0∈Rn，λmax≥λmin≥0，ε，γ∈(0,1)，η∈[0,1]，0<σ1<σ2<1；計算f0，令C0=f0，Q0=1，α0=1，k=1.

步驟1 若‖gk‖≤ε，停止迭代；否則，令dk=-αkgk，t=1.

步驟2 計算步長αk(Hager-Zhang線搜索).若滿足：

(13)

令xk+1=xk+tdk，轉向步驟3；否則，選擇t∈[σ1t,σ2t]，轉向步驟2.

步驟3 通過(4)-(5)式，(8)式，(11)-(12)式計算步長αk，若αk<0，令αk=αBB1，若αk<0，再令αk=λmax；否則，αk=min{λmax,{λmin,αk}}；轉步驟4.

步驟5 令k=k+1；轉向步驟1.

進一步給出上述算法的收斂性分析，收斂性結果用到了如下兩個假設：

假設2.1 水平集Ω={x∈R:f(x)≤f(x0)}有界，即存在一個常數B>0，有

‖x‖≤B，?x∈L.

假設2.2 目標函數f在Ω的某個鄰域N連續可微，且梯度?fLipschitz連續，即存在常數L>0，有

上述引理表明任何tk都滿足非單調線搜索條件(13)，于是就可以確定上述算法.進一步，在[αmin,αmax]中選擇步長αk，能確保存在兩個常數c1和c2，使得搜索方向dk滿足：

gkdk≤-c1‖gk‖2，‖dk‖≤c2‖gk‖，?k∈R.

以這種方式，可以得到算法3.1的收斂性定理[13],下面定理的證明參考文獻[20].

3 數值實驗

Hager-Zhang線搜索過程中的參數分別為γ=10-4，ηk=0.7，σ=0.8，另外兩個參數分別為λmax=1030，λmin=10-30，混合參數的初始值為θk=0.5.這篇文章中的終止準則為：

‖gk‖∞≤10-6,

當迭代次數超過6 000時也會終止.從文獻[21]中選擇了85個測試函數，它們的維數介于100～100 000之間，算法的測試環境為Matlab2012a，聯想Windows10下Ubuntu14.04操作系統，電腦的處理器為2.1 Ghz的Intel(R)Core(TM)i5-5 500 CPU，內存為4 G.

圖1 計算時間性能曲線Fig.1 Performance profiles based on CPU time 圖2 迭代次數性能曲線Fig.2 Performance profiles based on the number of iterations圖3 梯度計算次數性能曲線Fig.3 Performance profiles based on the number of gradient calls圖4 函數計算次數性能曲線Fig.4 Performance profiles based on the number of function calls

圖1表明從計算時間性能曲線來看，SGW1和MSBB2可以解決22%的問題，SGZ1和MSBB1可以解決18%的問題，SBB4可以解決20%的問題，MSBB3可以解決36%的問題，如果我們青睞于能以最大效率解決95%的問題，那么MSBB1方法和MSBB3方法優選，如t>2時的性能曲線高度所示.類似地，從圖2，圖3，圖4我們也可以看出當t>2時，MSBB2方法和SGW1,SGZ1,SBB4方法是可比的，MSBB1和MSBB3方法對應的性能曲線都在其他方法對應的性能曲線之上，因此，MSBB1方法和MSBB3方法更優.

4 結論

本文基于文獻[19]所提出的混合割線方程修正文獻[14]中提出的步長，得到一個新的步長，新步長不僅利用了當前迭代點處的梯度值和函數值，也利用了前兩次迭代點處的梯度值和函數值，同時基于文獻[15]中新步長的推導過程，又提出了另外兩個新的步長.在文獻[15]中算法的框架下，結合Hager-Zhang非單調線搜索，所提出的方法具有全局收斂性.數值結果采用Dolan和More'提出的性能曲線，通過對6種方法的性能曲線分析MSBB1和MSBB3數值性能要更好.