基于混合割線方程修正的L-BFGS算法

陳昱含

(重慶師范大學數(shù)學科學學院， 重慶 401331)

引 言

求解非線性無約束優(yōu)化問題是最優(yōu)化理論與算法研究方面最基本的問題，在許多高科技領域都有著重大的應用意義。本文中，考慮以下無約束優(yōu)化問題：

(1)

其中，函數(shù)f:Rn→R是一個二次可微連續(xù)函數(shù)。BFGS方法是解決無約束優(yōu)化問題的最有效的擬牛頓方法之一，具有良好的數(shù)值結果和理論收斂性。該方法通過更新對稱矩陣Bk去逼近目標函數(shù)的Hesse矩陣，使其滿足割線方程(擬牛頓條件)，即

Bk+1sk=yk

(2)

其中，sk=xk+1-xk,yk=gk+1-gk，Bk的更新公式如下

(3)

由于BFGS方法在每次迭代中都需要計算和存儲更新的矩陣，將其應用于大規(guī)模優(yōu)化問題時，效率可能會降低。為此，Liu[1]首先引入了有限記憶BFGS(L-BFGS)方法，這是對BFGS方法的改編。它可以看作是用額外的存儲來加速收斂速度的共軛梯度法，也可以被視為存儲受到限制的BFGS方法。它既克服了擬牛頓法計算量大的困難，同時又保持了良好的收斂性。

近年來，國內(nèi)外許多學者積極投身到L-BFGS方法的研究中。Hou[2]利用Li[3]提出的割線方程對標準的L-BFGS方法進行修正，建立了在非凸假設和一定條件下的超線性收斂性。Biglari等人[4]為了改善目標函數(shù)的曲率信息，使用四階張量模型導出了一個新的割線方程，提出了基于高階張量模型的L-BFGS算法，并研究了該方法在一致凸問題上的全局和局部收斂性。Tarzanagh等人[5]針對文獻[6-9]提出的幾種割線方程，進行組合改進，提出了一種基于修正割線方程的正則化有限記憶BFGS型新方法，并在某些標準假設下，提供了新方法的全局收斂性。Dehghani等人[10]采用鏈式法則，在使用梯度值和函數(shù)值信息的同時，利用最近三個點的信息引入了不同的割線關系。并在非凸假設性條件下，建立了BFGS方法的全局收斂性。Razieh等人[11]基于Zhang[9]提出的割線方程提出了新的割線方程，該方程保證了對于一般函數(shù)，Hesse矩陣逆的近似Hk+1的正定性。Boggs等人[12]對儲存大小m進行研究，提出了評估儲存大小m好壞的有效度量，使得L-BFGS可以自適應選取m。

受以上文獻的啟發(fā)，關注到割線方程在非線性優(yōu)化問題中起著核心作用?？梢灶A測，通過修正割線方程，既可以保持擬牛頓法的大多數(shù)優(yōu)良性質(zhì)，又能更好的逼近目標函數(shù)的二階曲率信息。為了利用L-BFGS方法獲得更好的計算效果，本文基于Li[3]和Yuan[9]等人提出的兩種割線方程，構造了一個新的割線方程，并將其應用到L-BFGS方法中求解大規(guī)模無約束優(yōu)化問題。在一定假設條件下檢驗了該方法全局收斂性，并對其收斂速度進行了研究。

1 混合割線方程

一般地，在擬牛頓法的每次迭代中，都滿足割線條件(2)。從該方程式很容易看出，對于給定的正定矩陣，如果滿足以下條件：

(4)

通常稱為曲率條件，則矩陣Bk+1是正定的。

為了更精確地近似Hesse矩陣，一些文獻對割線方程進行了一些修改。一類方法是將函數(shù)值fk合并到梯度差yk中，另一類方法是把迭代點差sk合并到y(tǒng)k中。下面概述一些近年來提出的有效割線方程。

Zhang和Xu[8]推導出了一種具有向量參數(shù)的割線方程：

(5)

其中，ωk=3(gk+1+gk)Tsk-6(fk+1-fk),uk可以取sk，yk，或者gk。當uk取sk時，就退化到了Zhang等人[7]提出的割線方程，當uk取yk時，就退化到了Yuan[9]提出的割線方程。

(6)

uk=(1-θk)yk+θksk,θk∈[0,1]

(7)

數(shù)值試驗結果表明，應用該割線方程改進的BFGS算法優(yōu)于文獻[6,9]中提出的改進的BFGS算法。這表明了所提出的混合割線方程的有效性。

此外，Li和Fukushima[3]等人提出了一種在非凸假設條件下依然保持全局收斂性的割線方程：

(8)

(9)

為了取得更好的數(shù)值結果，本文通過引入一個參數(shù)λ，對Li和Fukushima[3]以及Yuan[9]提出的兩種割線方程進行凸組合，提出了一種新的混合割線方程如下：

(10)

其中，λ∈[0,1]，rk如式(9)所示。當λ=0，該方程就退化到了Li和Fukushima[3]提出的方程，當λ=1，該方程就退化到了Yuan[9]提出的方法。

2 修正的BFGS方法(ML-BFGS)

考慮以上提出的無約束優(yōu)化問題(1)，標準的BFGS方法的迭代格式如下：

xk+1=xk+αkdk

(11)

dk=-Hkgk

(12)

其中，αk滿足以下標準Wolfe條件：

(13)

(14)

其中，dk為搜索方向，gk為xk處的梯度，Hk為xk處Hesse矩陣逆的近似，則Hk可由以下形式的BFGS更新公式進行更新：

(15)

其中，

(16)

(17)

當取γk為1時，該方法就退化到了無記憶BFGS方法。本文采取Al-Baali[15]的取法，如下：

(18)

本文將新提出的混合割線方程應用到L-BFGS方法當中，提出了一個修正的有限記憶BFGS算法(ML-BFGS)方法，如下：

Step3利用Wolfe條件式(13)及式(14)計算αk(通常設第一次的步長為單位步長1)。

Step6令k=k+1，轉(zhuǎn)Step2。

3 收斂性分析

在本節(jié)中，證明ML-BFGS方法在一致凸問題上是全局收斂的，并且其收斂速度是R-線性的。

假設A

1.目標函數(shù)f在Rn上下有界，在開集N上是二次連續(xù)可微的，

2.水平集L={x∈Rn|f(x)≤f(x0)}是凸的，其中L?N，x0為初始點，

3.存在正實數(shù)M1，M2，對于所有的z∈Rn和x∈L使得

(19)

(20)

且αk滿足Wolfe條件式(13)及式(14)，則

(21)

定理2設序列{xk}是由ML-BFGS算法生成的，若對任意的k有

(22)

則有

證明由引理1和Wolfe條件式(13)及式(14)可得

(23)

由式(22)可知，存在一個常數(shù)δ，使得對所有的k，有

cosθk≥δ>0

引理3[18]若a,b∈Rn，則有

tr(abT)=aTb=bTa

(24)

其中tr(abT)為abT的跡。

引理4[18]若u1,u2,u3,u4∈Rn，則有

(25)

fk-f*≤rk(f1-f*)

(26)

(27)

則由假設A、引理4～5可得式(26)，具體證明過程見文獻[19]，又由x*處的泰勒展開公式和式(19)，可得

即

所以{xk}是R-線性收斂的。

4 數(shù)值實驗結果

為了進行比較，本節(jié)中，將測試此算法ML-BFGS在一組測試問題上的數(shù)值性能，測試環(huán)境為華碩windows10操作系統(tǒng)Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz 1.80 GHz，4.00GB內(nèi)存。

本文對CUTEr[19]中40個500-100000維的非線性無約束問題進行實驗。其中每個問題都是規(guī)則的，即它的梯度和Hesse矩陣存在并且在各處都是連續(xù)的。對于每個測試問題，取ε=10-6，c1=10-2,c2=0.9，初始矩陣為γkI，γk的選取如式(18)所示。在用不同的m∈{3,20}處理了幾個問題后，發(fā)現(xiàn)當m=5時，數(shù)值結果相對較好，所以本文中的實驗取m=5。

下面對參數(shù)λ的選擇進行討論，當λ=0，割線方程就退化到了基于Li和Fukushima[3]提出的割線方程，當λ=1，割線方程就退化到了Yuan[9]提出的割線方程。因此本文提出以下三個策略：

LM1:m=5，λ=0，即基于Li和Fukushima[3]割線方程的L-BFGS方法；

LM2:m=5，λ=1，即基于Yuan[9]割線方程的L-BFGS方法；

LM3:m=5，λ=0.8，基于本文提出的混合割線方程的L-BFGS方法(ML-BFGS)

為了直觀有效地比較標準L-BFGS、LM1、LM2、LM3四種方法的數(shù)值效果，本文繪制了基于CPU時間(以秒為單位)，函數(shù)計算次數(shù)，梯度計算時間和迭代次數(shù)的性能曲線，如圖1～圖4所示。

圖1 基于cpu時間的性能概況

圖2 基于函數(shù)計算次數(shù)的性能概況

圖3 基于梯度計算次數(shù)的性能概況

圖4 基于迭代次數(shù)的性能概況

Dolan和Moré[20]的性能曲線圖描繪了在最佳算法的給定因子(水平軸)內(nèi)解決的問題(垂直軸)所占的比例，更有效的算法位于圖的左上側的“頂部”。因此，可以認為在整個圖中處于“左上方”的算法比其他算法更有效。

從圖1～圖4可以看出，不論是CPU時間、函數(shù)計算次數(shù)，還是梯度計算時間和迭代次數(shù)，本文提出的ML-BFGS方法和其他三種方法都是極具競爭力的，可見本文提出的基于混合割線方程的L-BFGS算法在部分的問題上是優(yōu)于其他三種算法的。

4 結束語

本文提出了一個新的混合割線方程，并將其應用到L-BFGS方法中，提出了ML-BFGS方法。在適當?shù)募僭O下，保持了該方法在一致凸函數(shù)上的全局收斂性。數(shù)值結果表明，該方法在部分問題上優(yōu)于其他三種方法?？偟膩碚f，本文提出的ML-BFGS算法通過修正割線方程提高了L-BFGS算法的計算效率，同時又保持了L-BFGS良好的理論收斂性。因此，該方法是有效的且與L-BFGS相比是極具競爭力的。