陳奎林

(重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶 401331)

1 問題的提出

本文針對(duì)無約束最優(yōu)化問題:minf(x)，x∈Rn開展研究，其中f:Rn→R是一個(gè)連續(xù)可微的函數(shù)。擬牛頓算法中的BFGS算法是一類解決無約束最優(yōu)化問題的有效算法，這類算法的關(guān)鍵是Bk的選取，不同的選取方式，對(duì)應(yīng)不同的BFGS算法。

為了使算法更具優(yōu)越性，文獻(xiàn)［1－5］在傳統(tǒng)的擬牛頓方程的基礎(chǔ)上提出了一個(gè)新的擬牛頓方程，即，其中是一個(gè)對(duì)稱正定矩陣，從而得到了一類改進(jìn)的BFGS方法，其迭代公式為

受以上思想的啟發(fā)，提出了Ak的一種選取方法，即Ak=‖gk+1－gk‖I，進(jìn)而提出了一類新的BFGS算法，并證明了它的全局收斂性和超線性收斂性。

本文采用的搜索準(zhǔn)則(Wolfe準(zhǔn)則)為:

其中0＜σ1＜σ2＜1。

改進(jìn)的BFGS算法步驟:

步驟1 給出初始點(diǎn)x0∈Rn和初始對(duì)稱正定矩陣B0∈Rn×n，令ε＞0，k=0。

步驟2 若梯度函數(shù)在迭代點(diǎn)xk處滿足‖gk‖≤ε，則停止;否則計(jì)算Bkdk+gk=0，求出搜索方向dk。

步驟3 利用Wolfe準(zhǔn)則求得步長αk，令xk+1=xk+αkdk。

步驟4 計(jì)算Ak=‖gk+1－gk‖I，并代入 式(1)，修正Bk得Bk+1。

步驟5 令k:=k+1，轉(zhuǎn)步驟2。

2 收斂性證明

為證明算法的全局收斂性和超線性收斂性需要以下假設(shè):

①f(x)是二階連續(xù)可微的，x*是f(x)的極小點(diǎn)。

②水平集Ω={x|f(x)≤f(x0)}是有界凸集，其中x0是給定的。

③f(x)在凸集Ω上連續(xù)可微，且存在一個(gè)常數(shù)L＞0，使得下式成立:

其中:g(x)=▽f(x);‖·‖是Euclidean范數(shù)。

④f(x)一致凸，即存在常數(shù)m和M，使得

這里?x∈Ω，z∈Rn，其中 G(x)是 f(x)的海色矩陣。

⑤ G(x)在Ω上Lipschitz連續(xù)。即存在L'＞0使得?x，y∈Ω，有

由上面的假設(shè)容易得到

2.1 全局收斂性證明

引理1［4］對(duì)任意給定的 k 和由改進(jìn)的 BFGS 算法產(chǎn)生的(α，x，g，d)，若＞0，那么

kk+1k+1k+1Bk+1正定。

引理2 若假設(shè)(a)、(b)、(d)成立，由改進(jìn)的BFGS算法產(chǎn)生的點(diǎn)列為 {xk}，則，其中sk=xk+1－xk。

證明由Taylor公式，

由假設(shè)④及式(2)有

引理3 若假設(shè)②～④成立，則式(4)(5)成立

證明

定理1 設(shè)x0為任意初始點(diǎn)，f(x)在Ω上滿足假設(shè)(a)，(d)，則對(duì)任何對(duì)稱正定矩陣B0，由改進(jìn)的BFGS算法產(chǎn)生的點(diǎn)列 { xk}收斂到f(x)的極小點(diǎn)x*。

證明記，由引理 3 可知 mk≥m'，Mk≤M'。

對(duì)式(1)有

令 ψ(Bk+1)=tr(Bk+1)－ln(det(Bk+1))，則有

因?yàn)楹瘮?shù)p(t)=1－t+lnt對(duì)任意的t＞0都是非正的，所以有

不失一般性，假設(shè) c=M'－ lnm'－1 ＞0，cosθj→0，那么存在 k1＞0，使得對(duì)?j＞ k1都有 ln cos2θj＜ －2c，所以

當(dāng)k充分大時(shí)，上式右端的值為負(fù)，與左端矛盾，所以假設(shè)不成立，從而存在一個(gè)子序列 {jk}，使得cosθjk≥ε＞0。而由文獻(xiàn)［1］中式(3.14)可知lim inf‖▽fk‖→0。又因?yàn)槟繕?biāo)函數(shù)是凸的，所以由改進(jìn)的BFGS算法產(chǎn)生的點(diǎn)列 { xk}收斂到f(x)的極小點(diǎn)x*。

2.2 超線性收斂性證明

引理4 若{ xk}是由改進(jìn)的BFGS算法產(chǎn)生的點(diǎn)列，且假設(shè)(c)成立，則

證明由 Taylor公式，有 gk+1－ gk=G(ξk)sk，其中 ξk=xk+ σsk，σ∈(0，1)。所以 ‖Ak‖=‖gk+1－gk‖≤L‖sk‖，再結(jié)合引理2可知成立。

定理2 在假設(shè)①～⑤成立的前提下，設(shè)以1作為試探步長的Wolfe步長規(guī)則下改進(jìn)的BFGS算法產(chǎn)生的迭代序列 { xk}收斂到最優(yōu)解x*，且滿足，則 { xk}超線性收斂到x*。證明過程類似于文獻(xiàn)［1］的描述。不再贅述。

［1］王宜舉，修乃華.非線性規(guī)劃理論與算法［M］.陜西:科學(xué)技術(shù)出版社，2008.

［2］王安平，馬爍，趙天玉.一種改進(jìn)的BFGS算法及其全局收斂性分析［J］.河北科技大學(xué)學(xué)報(bào)，2009，30(1):8－10.

［3］張恒，何偉.基于新擬牛頓方程的改進(jìn)BFGS方法［J］.淮海工學(xué)院學(xué)報(bào)，2007，16(3):10－12.

［4］WEI Zengxin，LI Guoyin，QI Liqun.New quasi-Newton methods for unconstrained optimization problems［J］.Applied Math and Comp，2006，175:1156 －1188.

［5］Jorge Nocedal，Stephen J.Wright.Numerical optimization［M］.［S.l.］:Springer，1999.