鄒 舒，周群艷

(江蘇理工學(xué)院 數(shù)理學(xué)院，江蘇 常州 213001)

0 引言

考慮非線性無約束最優(yōu)化問題

其中f:Rn→R二次連續(xù)可微。

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

L－BFGS法是在BFGS法的基礎(chǔ)上改變得到的。若在第k步，已經(jīng)存儲了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法最主要的優(yōu)點是不需要明顯地存儲n階方陣Hk，只需存儲第k步的向量Hkgk，這可以通過文獻(xiàn)[1]中提出的雙循環(huán)算法計算得到。雙循環(huán)算法代價低，且H(0)k的計算獨立于其它的計算過程。

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

1 算法

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

下面給出新的非單調(diào)L－BFGS算法。

算法1:

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

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

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

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

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

2 收斂性分析

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

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

以下的定理1、定理2和定理3在文獻(xiàn)[3]中已經(jīng)證明，這里僅加以敘述。

定理2 若Bk

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

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

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

定理5 如果

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

其中 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))}單調(diào)下降得，于是

下面的定理6和定理7見文獻(xiàn)[3，6]。

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

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

定理8 若假設(shè)成立，序列{xk}為算法產(chǎn)生的點列，則

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

因此

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

[1]袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京:科學(xué)出版社，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.