BFGS法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

数理最適化において、ブロイデン・フレッチャー・ゴールドファーブ・シャンノ法 (: Broyden–Fletcher–Goldfarb–Shanno algorithm)、略してBFGS法は、非制限非線形最適化問題に対する反復的解法の一つである[1]

BFGS法は山登り法の一種である、準ニュートン法に属しており、(2回微分可能であることが望ましい)関数の停留点を探索する。この種の問題の最適性の十分条件勾配が零となることである。ニュートン法とBFGS法は、最適点英語版の近傍で関数が二次までテイラー展開可能でない場合、収束が保証されない。しかし、BFGS法は関数が滑らかでない場合でもよい性能を発揮することが示されている[2]

準ニュートン法では、二次微分ヘッセ行列は必ずしも直接計算しなければならないわけではなく、勾配を計算(あるいは近似計算)した結果を用いて近似することもできる。準ニュートン法は、一次微分の根を探索する正割法英語版を多次元問題へ一般化したものである。多次元問題では、正割方程式は一意解を与えないため、準ニュートン法はどのように解を拘束するかによってことなる。BFGS法はこの種の手法の中で最も普及しているものの一つである[3]。その他にも、BFGS法を限られたメモリで実行できるようにし、非常に多くの変数を扱えるように変更されたL-BFGS法英語版も広く使われている。単純な矩形拘束を扱うBFGS-B法[4]と呼ばれる変種も存在する。

このアルゴリズムの名前は、チャールズ・ジョージ・ブロイデン英語版ロジャー・フレッチャー英語版ドナルド・ゴールドファーブ英語版デイビッド・シャンノ英語版に因む。

原理[編集]

最適化問題とは、  は  は微分可能なスカラー値関数とし、 の取り得る値に制限はないものとする。

このアルゴリズムでは、初期推定値  から初め、各ステージ毎に反復的により良い推定値へと更新していく。

ステージ k における探索方向 pk  はニュートン方程式に類似した次の方程式を解くことにより得られる。

ここで  はヘッセ行列の近似であり、各ステージ毎に反復的に更新する。 は xk で計算した勾配である。方向 pk を得たのち、この方向に向けて直線探索を行い、 を最小とするようなスカラー 

 の更新において課される準ニュートン条件は以下の通りである。

 および  は 曲率条件  が満たされている必要がある。もし関数が強凸性を持たない場合、この条件を明示的に課す必要がある。

点 xk+1 における完全なヘッセ行列を計算して Bk+1 とする代わりに、二つの行列を次のように加算して近似ヘッセ行列を更新する。

Uk および Vk はどちらも階数1の対称行列であるが、これらの和を取ることにより階数2の行列を用いて更新することとなる。BFGS法とDFP法英語版は、以前の行列更新法と階数2の行列を更新に用いる点が異なる。階数1行列を用いる、より単純な手法は対称ランク1英語版法と呼ばれ、正定値性が保証されない。 正割条件   および 

上の  および  を  に代入して書き下すと、次のようになる。

アルゴリズム[編集]

初期推定値  と初期近似ヘッセ行列  から始め、次のステップを反復することにより、 は解に収束する。

  1. 方向  を 
  2. 1次最適化(直線探索)によりステップサイズ  を求める。すなわち、 
  3.  と置き、

 は最小化の対象となる関数である。勾配のノルム   は  

このアルゴリズムのステップ1は 

この計算は、 が対象行列であり、 および  がスカラーであることを用いると次のように展開でき、一次行列を用いることなく効率的に計算できる。

最尤推定ベイズ推定などの統計推定問題においては、最終的なヘッセ行列の逆行列を用いて解の信頼区間もしくは確信区間英語版を推定することができる。しかし、これらの量は正確には真のヘッセ行列により定義されるものであり、BFGS近似は真のヘッセ行列に収束しない場合がある。

実装[編集]

GSL は gsl_multimin_fdfminimizer_vector_bfgs2 でBFGS法を実装している。Ceres Solver はBFGS法とL-BFGS法英語版の両方を実装している。

SciPyでは、scipy.optimize.fmin_bfgs 関数がBFGS法を実装している。パラメータ L にとても多きな数を指定することにより、L-BFGS法を実行することもできる。

Octave は double-dogleg 近似を用いたBFGS法を  cubic line search に用いている。

R言語では、BFGS法(および矩形拘束を扱えるL-BFGS-B法)が基本関数 optim() のオプションとして実装されている。

MATLAB Optimization Toolbox英語版 では、fminunc 関数が問題サイズを「中程度」に指定した場合にBFGS法を利用する。

C++ で実装され、高精度算術パッケージ ARPREC に統合されている高精度算術版BFGS法 (pBFGS) は(丸め誤差などの)数値的不安定性に対して頑強である。

他にも、C++ によるBFGS(およびL-BFGS, L-BFGS-B, CG, ニュートン法)の実装としては、MIT License で公開されている Eigen英語版 ライブラリが存在する。

オープンソースの C 実装としては、Gnu Regression, Econometrics and Time-series Library (gretl) がBFGSおよび L-BFGS法を含んでいる。

関連項目[編集]

出典[編集]

  1. ^ Fletcher, Roger (1987), Practical methods of optimization (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8 
  2. ^ Lewis, Adrian S.; Overton, Michael (2009), Nonsmooth optimization via BFGS, http://www.cs.nyu.edu/~overton/papers/pdffiles/bfgs_inexactLS.pdf 
  3. ^ Nocedal & Wright (2006), page 24
  4. ^ Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge; Zhu, Ciyou (1995), “A Limited Memory Algorithm for Bound Constrained Optimization”, SIAM Journal on Scientific Computing 16 (5): 1190–1208, doi:10.1137/0916069, http://www.ece.northwestern.edu/~nocedal/PSfiles/limited.ps.gz 

参照文献[編集]

外部リンク[編集]