一種非單調L－BFGS方法及其全局收斂性

鄒 舒，周群艷

(江蘇理工學院 數理學院，江蘇 常州 213001)

0 引言

考慮非線性無約束最優化問題

其中f:Rn→R二次連續可微。

擬牛頓法是求解問題(1)的最有效的方法之一。線搜索擬牛頓法最基本的迭代格式[1]是xk+1=xkαkHkgk，k=0，1，2，…。其中 x0給定，αk是由某種線搜索方法計算得到的步長，gk= ▽f(xk)，Hk∈Rn×n是當前迭代點xk處Hesse陣的逆的近似，滿足擬牛頓方程Hk+1yk=sk，其中sk=xk+1－xk，yk=gk+1－gk。通常Hk可借助擬牛頓公式校正得到，比如BFGS公式，其中在過去的幾十年中，BFGS擬牛頓算法被廣泛應用于非線性最優化，其全局與局部收斂性得到了論證。然而，當n較大時，不可能存儲以及校正一個n階的方陣。對于大規模無約束優化問題，有限內存BFGS(L－BFGS)算法更受青睞。

L－BFGS法是在BFGS法的基礎上改變得到的。若在第k步，已經存儲了m對最近的(si，yi)，i=k－m+1，L，K。選取Hesse陣▽2f(xk+1)的初始逆矩陣的近似H(0)k+1，用BFGS公式校正H(0)k+1^m=min(m，k)次，就得到▽2f(xk+1)的逆矩陣的近似Hk+1。故L－BFGS法中的Hk+1為[2]:

L－BFGS法最主要的優點是不需要明顯地存儲n階方陣Hk，只需存儲第k步的向量Hkgk，這可以通過文獻[1]中提出的雙循環算法計算得到。雙循環算法代價低，且H(0)k的計算獨立于其它的計算過程。

盡管有限內存法被認為非常有效，但是對于一些壞條件問題，可能速度非常慢。然而，可通過對初始Hesse陣的逆矩陣使用預條件的方式大大改進有限內存法的效率。本文嘗試著從另一個角度來改進LBFGS算法。我們注意到當今比較流行的非單調技術多數應用在牛頓類方法、共軛梯度法或信賴域算法，對有限內存類算法使用非單調技術的研究較少。

1 算法

通常的L－BFGS法使用如下的Wolfe－Powell準則確定步長因子中0＜σ1＜σ2＜1。為提高L－BFGS算法的效率，Yuan，Wei和Wu在文獻[3]中提出了一種采用Grippo[4]的非單調技術的L－BFGS法，要求步長因子αk滿足，其中，H為一非負整數。但這種方法只要求下一個迭代點處的函數值小于前面幾步迭代過程中函數的最大值，一定程度上忽視了當前迭代點處的函數值，影響了算法的效率。為了克服這一缺點，本文引進文獻[5]中的非單調策略，記Rk=ηkfl(k)+(1－ηk)fk，給出新的非單調 Wolfe準則

下面給出新的非單調L－BFGS算法。

算法1:

步0:給定 x0∈Rn，0 ＜ δ1，δ2＜1，0 ＜ ε ＜1=I，置 k=0;

步1:計算 gk，若‖gk‖≤εmax{1，‖xk‖}，停止計算，否則轉步 2;

步2:計算 dk= －Hkgk，xk+1=xk+αkdk，其中 αk滿足準則(3);

為了便于進行收斂性分析，記Hk的逆為Bk，則算法1的步2和步3等價于

步2’:解 Bkdk= －gk得 dk，令 xk+1=xk+ αkdk，其中 αk滿足準則(3)。

2 收斂性分析

假設1(1)水平集Ω={x|f(x)≤f(x0)}有界。(2)函數f(x)在Ω上二次連續可微。(3)f(x)一致凸，即存在兩個正數N1和N2使得對任何z∈Rn和x∈Ω有N1‖z‖2≤zTG(x)z≤N2‖z‖2。

顯然在假設條件下，存在M*＞0使得‖G(x)‖≤M*，x∈Ω。另外，假設1(2)表明存在一個常數L≥0滿足‖g(x)－g(y)‖≤L‖x－y‖，x，y∈Ω。

以下的定理1、定理2和定理3在文獻[3]中已經證明，這里僅加以敘述。

定理2 若Bk

定理3 若假設1(3)成立，則存在b0＞0使得，其中

定理4 若假設1成立，序列{xk}為算法產生的序列，則{f(xI(k))}收斂。

證:由Rk和 f(xI(k))的定義以及線搜索準則(3)得 Rk=ηkf(xI(k))+(1－ηk)fk≤ηkf(xi(k))+max{f(xI(k))，Rk}≤f(xI(k))，故{fI(k)}單調下降，又 fk+1≤fI(k+1)≤fI(k)≤f0，即序列{xk}含于 Ω 中，所以{f(xI(k))}收斂。

定理5 如果

歷史是在高中階段學習的一門重要的文科課程，歷史學習能夠幫助學生正確認識人類社會經濟與政治等方面的發展與演進，對學生綜合素質的發展有著積極的影響。因此教師在組織教學活動的過程中需要重視對高中生歷史核心素養的培養，為學生培養歷史核心素養，能夠幫助學生站在歷史的角度認識問題、分析問題，對學生今后的學習與發展有著積極作用。在進行歷史核心素養培養的過程中，不僅需要對課本的基礎知識和內容進行學習，還需要站在歷史發展的角度進行歸納與總結，將高中歷史課堂賦予濃厚的人文與歷史氣息。

其中 tk≥0，則

證明 由式(5)和定理4得f(xk+1)≤Rk－tk≤f(xI(k))－tk，f(xk+2)≤Rk+1－tk+1≤f(xI(k+1))－tk+1≤由此可得

分別選取 k=0，H+1，…，(n－1)(H+1)，可得，將這 n 個不等式相加

又由xI(nH+n)∈Ω及序列{f(xI(k))}單調下降得，于是

下面的定理6和定理7見文獻[3，6]。

定理6 如果非負數序列{mk}滿足，…，則 lim supkmk＞0。

定理7 若假設成立，序列{xk}為算法產生的點列。如果，則存在 ε ＞0，使得對任

定理8 若假設成立，序列{xk}為算法產生的點列，則

證明 由定理3和線搜索準則(3)得 fk+1≤Rk≤f(xI(k))－ε1‖sk‖ηk(xI(k))≤f(xI(k))－。令由定理 5 得

因此

因為xk∈Ω，并且Ω有界，所以可假設存在一個常數b3＞0使‖gk‖≤b3。故有

[1]袁亞湘，孫文瑜.最優化理論與方法[M].北京:科學出版社，1997.

[2]Conn A R，Gould N IM，Toint Ph L.Trust－ Region Methods[M].Philadelphia，PA:MPS/SIAM Series on Optimization，Society for Industrial and Applied Mathematics(SIAM)，Mathematical Programming Society(MPS)，Philadelphia，PA，2000.

[3]YUAN Gong －liu，WEIZeng － xin，Wu Yan － liu.Modified limited memory BFGSmethod with nonmonotone line search for unconstrained optimization[J].J.Korean Math.Soc.，2010，47:767 －788.

[4]Grippo L，Lamparillo F，Lucidi S.A nonmonotone line search technique for New ton’smethod[J].SIAM J.Numer.Anal.，1986，23:707 －716.

[5]Ahookhosh M，Amini K.An efficientnonmonotone trust－ regionmethod for unconstrained optimization[J].Numer.Algor.，2012，59:523 －540.

[6]HAN Ji－ ye，LIU Guang － hui.Global convergence analysis of a new nonmonotone BFGS algorithm on convex objective functions[J].Computational optimization and applications，1997，7:277 －289.