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

柳力

（吉林市廣播電視大學教學處，吉林吉林132002）

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

柳力

（吉林市廣播電視大學教學處，吉林吉林132002）

本文把正定矩陣關于向量的等內積分解算法應用于改進BFGS算法中搜索方向的計算.通過建立不依賴于搜索方式的用分解矩陣表達的校正公式，給出了用Hesse近似矩陣的等內積分解矩陣確定搜索方向的BFGS算法.

BFGS算法；校正矩陣；等內積分解；搜索方向；算法

1　引言

利用正定矩陣關于向量的等內積分解算法［1］，文［2］提出了由校正矩陣的等內積分解矩陣確定搜索方向的擬Newton算法．即對于無約束最優化問題

其中f：Rn→R1是連續可微函數，通過建立Hesse近似矩陣B關于目標函數梯度向量的等內積分解矩陣的校正公式，計算搜索方向的一種新算法．

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

在求迭代點xk+1處的搜索方向dk+1時，一般是解方程組

而不是用（1.3）式直接計算.

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

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

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

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

2　用分解矩陣形式表達的BFGS校正公式

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

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

其中σ0=

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

引理2.2對于BFGS校正公式（1.2），若Bk關于gk的等內積分解矩陣為.記

則Bk+1=，并且

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

所以Bk+1=.由于

由引理2.1，易得

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

證畢.

當記

定理2.1對于BFGS校正公式（1.2），若已求得Bk關于gk的等內積分解矩陣，則Bk+1關于gk+1的等內積分解矩陣

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

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

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

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

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

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

新的BFGS算法：

步1取初始點x0，ε≥0，計算g0=g（x0）.若‖g0‖≤ε，則停止運算；否則轉步2.

步2令k=0；對初始矩陣B0=I作關于g0的等內積分解，求出分解矩陣和

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

步4一維搜索：由線性搜索求出步長因子αk.

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

步6由公式（2.7）求出Bk+1關于gk+1的等內積分解矩陣和系數ak+1=ak.

步7令k=k+1，轉步3.

［1］柳力.一個矩陣分解算法的推廣及應用［J］.數學的實踐與認識，2011，41（21）：239-243.

［2］柳力.由校正矩陣的等內積分解矩陣確定搜索方向的擬牛頓算法［J］.數學的實踐與認識，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］席少霖.非線性最優化方法［M］.北京：高等教育出版社，1992.

［5］鄧乃揚等.無約束最優化計算方法［M］.北京：科學出版社，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）主題分類號：90C30O221.2

A

0255-7797（2016）05-1035-05

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

吉林省教育廳“十二五”科學技術研究項目資助（2014598）.

柳力（1958-），男，吉林吉林，副教授，主要研究方向：數學規劃.

2010 MR Subject Classification：90C30