一種改進的BFGS算法及其收斂性分析

陳奎林

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

1 問題的提出

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

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

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

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

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

改進的BFGS算法步驟:

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

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

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

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

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

2 收斂性證明

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

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

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

③f(x)在凸集Ω上連續(xù)可微，且存在一個常數(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］對任意給定的 k 和由改進的 BFGS 算法產(chǎn)生的(α，x，g，d)，若＞0，那么

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

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

證明由Taylor公式，

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

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

證明

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

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

對式(1)有

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

因為函數(shù)p(t)=1－t+lnt對任意的t＞0都是非正的，所以有

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

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

2.2 超線性收斂性證明

引理4 若{ xk}是由改進的BFGS算法產(chǎ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ī)則下改進的BFGS算法產(chǎn)生的迭代序列 { xk}收斂到最優(yōu)解x*，且滿足，則 { xk}超線性收斂到x*。證明過程類似于文獻［1］的描述。不再贅述。

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

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

［3］張恒，何偉.基于新擬牛頓方程的改進BFGS方法［J］.淮海工學(xué)院學(xué)報，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.