鄒 舒，周群艷

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

0 引言

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

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

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

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

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

1 算法

通常的L－BFGS法使用如下的Wolfe－Powell準(zhǔn)則確定步長(zhǎng)因子中0＜σ1＜σ2＜1。為提高L－BFGS算法的效率，Yuan，Wei和Wu在文獻(xiàn)[3]中提出了一種采用Grippo[4]的非單調(diào)技術(shù)的L－BFGS法，要求步長(zhǎng)因子αk滿(mǎn)足，其中，H為一非負(fù)整數(shù)。但這種方法只要求下一個(gè)迭代點(diǎn)處的函數(shù)值小于前面幾步迭代過(guò)程中函數(shù)的最大值，一定程度上忽視了當(dāng)前迭代點(diǎn)處的函數(shù)值，影響了算法的效率。為了克服這一缺點(diǎn)，本文引進(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:計(jì)算 gk，若‖gk‖≤εmax{1，‖xk‖}，停止計(jì)算，否則轉(zhuǎn)步 2;

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

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

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

2 收斂性分析

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

顯然在假設(shè)條件下，存在M*＞0使得‖G(x)‖≤M*，x∈Ω。另外，假設(shè)1(2)表明存在一個(gè)常數(shù)L≥0滿(mǎn)足‖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í)的一門(mén)重要的文科課程，歷史學(xué)習(xí)能夠幫助學(xué)生正確認(rèn)識(shí)人類(lèi)社會(huì)經(jīng)濟(jì)與政治等方面的發(fā)展與演進(jìn)，對(duì)學(xué)生綜合素質(zhì)的發(fā)展有著積極的影響。因此教師在組織教學(xué)活動(dòng)的過(guò)程中需要重視對(duì)高中生歷史核心素養(yǎng)的培養(yǎng)，為學(xué)生培養(yǎng)歷史核心素養(yǎng)，能夠幫助學(xué)生站在歷史的角度認(rèn)識(shí)問(wèn)題、分析問(wèn)題，對(duì)學(xué)生今后的學(xué)習(xí)與發(fā)展有著積極作用。在進(jìn)行歷史核心素養(yǎng)培養(yǎng)的過(guò)程中，不僅需要對(duì)課本的基礎(chǔ)知識(shí)和內(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 個(gè)不等式相加

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

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

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

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

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

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

因此

因?yàn)閤k∈Ω，并且Ω有界，所以可假設(shè)存在一個(gè)常數(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.