利用分解校正矩陣確定搜索方向的BFGS算法

柳力

（吉林市廣播電視大學(xué)教學(xué)處，吉林吉林132002）

利用分解校正矩陣確定搜索方向的BFGS算法

柳力

（吉林市廣播電視大學(xué)教學(xué)處，吉林吉林132002）

本文把正定矩陣關(guān)于向量的等內(nèi)積分解算法應(yīng)用于改進(jìn)BFGS算法中搜索方向的計(jì)算.通過(guò)建立不依賴于搜索方式的用分解矩陣表達(dá)的校正公式，給出了用Hesse近似矩陣的等內(nèi)積分解矩陣確定搜索方向的BFGS算法.

BFGS算法；校正矩陣；等內(nèi)積分解；搜索方向；算法

1　引言

利用正定矩陣關(guān)于向量的等內(nèi)積分解算法［1］，文［2］提出了由校正矩陣的等內(nèi)積分解矩陣確定搜索方向的擬Newton算法．即對(duì)于無(wú)約束最優(yōu)化問(wèn)題

其中f：Rn→R1是連續(xù)可微函數(shù)，通過(guò)建立Hesse近似矩陣B關(guān)于目標(biāo)函數(shù)梯度向量的等內(nèi)積分解矩陣的校正公式，計(jì)算搜索方向的一種新算法．

以擬Newton算法中最有代表性的BFGS算法為例，當(dāng)記xk為迭代點(diǎn)，sk=xk+1-xk，yk=gk+1-gk，gk=▽f（xk），則對(duì)B和對(duì)H的BFGS校正公式分別為

在求迭代點(diǎn)xk+1處的搜索方向dk+1時(shí)，一般是解方程組

而不是用（1.3）式直接計(jì)算.

采用（1.4）式的計(jì)算量顯然大于用（1.5）式，“舍近求遠(yuǎn)”的原因是，由于計(jì)算誤差的存在，實(shí)際計(jì)算時(shí)用（1.3）式可能出現(xiàn)Hk+1不正定甚至奇異的情況．而（1.2）式可以化為據(jù)此，Gill與Murray提出了利用Cholesky分解技術(shù)解方程組（1.4）的方法.即先對(duì)Bk+1作 Cholesky分解：，其中Lk+1為單位下三角陣，Dk+1為對(duì)角陣，再依次解方程組

同時(shí)利用（1.6）式，給出由Lk，Dk求Lk+1，Dk+1的迭代公式，使實(shí)際計(jì)算時(shí)不必每次迭代都進(jìn)行一次Bk的Cholesky分解，具體算法詳見文［3-5］.

而文［2］提出的改進(jìn)算法，則是運(yùn)用了正定矩陣關(guān)于向量的等內(nèi)積分解算法，通過(guò)求Bk+1關(guān)于gk+1=▽f（xk+1）的等內(nèi)積分解矩陣.即滿足條件

顯然文［2］給出了求搜索方向的另一種路徑，但文［2］中的相關(guān)結(jié)論，都是在精確線搜索條件下給出的，所以理論意義大于實(shí)際應(yīng)用．在擬Newton算法中BFGS算法是最有代表性的一個(gè)算法，帶Wofle搜索的BFGS算法具有全局收斂和超線性收斂性（參見文［4］），與擬Newton算法中的其它算法比較其收斂速度和數(shù)值穩(wěn)定性都是最好的．本文就以BFGS算法為研究對(duì)象，通過(guò)建立不依賴搜索方式的用分解矩陣表達(dá)的校正公式，給出用Hesse近似矩陣的等內(nèi)積分解矩陣確定搜索方向BFGS新算法.

2　用分解矩陣形式表達(dá)的BFGS校正公式

當(dāng)記uk=yk，vk=gk+1，wk=gk.由文［2］定理2.2，在精確線搜索條件下對(duì)于BFGS校正公式（1.2）.若已求得Bk關(guān)于gk的等內(nèi)積分解矩陣，則Bk+1關(guān)于gk+1的等內(nèi)積分解矩陣

其中λk=，Qk=，σk=wk+tkvk，.由文［2］定理2.3，初始校正矩陣B0=I關(guān)于g0的等內(nèi)積分解矩陣

其中σ0=

引理2.1設(shè)u，v?Rn，若β/=0，γ/=0，vTu=β-1+γ-1，則矩陣I-βuvT非奇異，并且

引理2.2對(duì)于BFGS校正公式（1.2），若Bk關(guān)于gk的等內(nèi)積分解矩陣為.記

則Bk+1=，并且

證注意到sk=xk+1-xk=αkdk，其中αk為步長(zhǎng)，于是Bksk=-αkgk.直接計(jì)算得

所以Bk+1=.由于

由引理2.1，易得

引理2.3若0/=δk?Rn，記Qk=，其中σk=δk+，則

證畢.

當(dāng)記

定理2.1對(duì)于BFGS校正公式（1.2），若已求得Bk關(guān)于gk的等內(nèi)積分解矩陣，則Bk+1關(guān)于gk+1的等內(nèi)積分解矩陣

證注意到Qk為Householder矩陣，=I，所以

故由引理2.2知Bk+1=.再由引理2.3得

其中ak+1=.故由（2.7）式定義的為Bk+1關(guān)于gk+1的等內(nèi)積分解矩陣.

推論2.1在精確線搜索條件下，（2.7）式與（2.1）式等價(jià)，即（2.1）式為（2.7）式的特例.

3　利用分解校正矩陣確定搜索方向的BFGS算法

顯然，把由（2.2）式和（2.7）式為分解校正矩陣，由（1.9）式計(jì)算搜索方向的步驟替換到BFGS算法中對(duì)應(yīng)的步驟里，就可以構(gòu)成利用分解校正矩陣確定搜索方向的BFGS新算法.由于分解校正矩陣的迭代運(yùn)算僅是非奇異矩陣到非奇異矩陣的迭代運(yùn)算，因此計(jì)算精度的要求應(yīng)低于原BFGS算法中對(duì)稱正定矩陣到對(duì)稱正定矩陣的迭代運(yùn)算.

新的BFGS算法：

步1取初始點(diǎn)x0，ε≥0，計(jì)算g0=g（x0）.若‖g0‖≤ε，則停止運(yùn)算；否則轉(zhuǎn)步2.

步2令k=0；對(duì)初始矩陣B0=I作關(guān)于g0的等內(nèi)積分解，求出分解矩陣和

步3求搜索方向dk：dk=.其中，（j=1，2，···，n）是的第j列元素之和.

步4一維搜索：由線性搜索求出步長(zhǎng)因子αk.

步5令xk+1=xk+αkdk，計(jì)算gk+1=g（xk+1），若‖gk+1‖≤ε，則停止計(jì)算；否則轉(zhuǎn)步6.

步6由公式（2.7）求出Bk+1關(guān)于gk+1的等內(nèi)積分解矩陣和系數(shù)ak+1=ak.

步7令k=k+1，轉(zhuǎn)步3.

［1］柳力.一個(gè)矩陣分解算法的推廣及應(yīng)用［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011，41（21）：239-243.

［2］柳力.由校正矩陣的等內(nèi)積分解矩陣確定搜索方向的擬牛頓算法［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2013，43（10）：214-219.

［3］Gill P E，Murray W.Quasi-Newton methods for unconstrained optimization［J］.Insti.Math.Appl.，1972，（9）：91-108.

［4］席少霖.非線性最優(yōu)化方法［M］.北京：高等教育出版社，1992.

［5］鄧乃揚(yáng)等.無(wú)約束最優(yōu)化計(jì)算方法［M］.北京：科學(xué)出版社，1982.

BFGS ALGORITHM BY USING THE DECOMPOSITION MATRIX OF THE CORRECTION MATRIX TO OBTAIN THE SEARCH DIRECTION

LIU Li
（Department of Teaching，TV University of Jilin City，Jilin 132002，China）

In this paper，the equal inner product decomposition algorithm of positive definite matrix is applied to improve the search direction calculation in BFGS algorithm.By setting up the correction matrixes of both independent search mode and decomposition matrixes expression，BFGS algorithm is put forward，in which search directions are obtained by using equal inner product decomposition matrixes of the Hesse approximate matrixes.

BFGS algorithm；correction metrix；equal inner product decomposition；search direction；algorithm

MR（2010）主題分類號(hào)：90C30O221.2

A

0255-7797（2016）05-1035-05

2014-02-22接收日期：2014-07-31

吉林省教育廳“十二五”科學(xué)技術(shù)研究項(xiàng)目資助（2014598）.

柳力（1958-），男，吉林吉林，副教授，主要研究方向：數(shù)學(xué)規(guī)劃.

2010 MR Subject Classification：90C30