BFGS法
数理最適化において、ブロイデン・フレッチャー・ゴールドファーブ・シャンノ法 (Broyden–Fletcher–Goldfarb–Shanno algorithm)、略してBFGS法は、非制限非線形最適化問題に対する反復的解法の一つである。
BFGS法は山登り法の一種である、準ニュートン法に属しており、(2回微分可能であることが望ましい)関数の停留点を探索する。この種の問題の最適性の十分条件は勾配が零となることである。ニュートン法とBFGS法は、最適点の近傍で関数が二次までテイラー展開可能でない場合、収束が保証されない。しかし、BFGS法は関数が滑らかでない場合でもよい性能を発揮することが示されている。
準ニュートン法では、二次微分のヘッセ行列は必ずしも直接計算しなければならないわけではなく、勾配を計算(あるいは近似計算)した結果を用いて近似することもできる。準ニュートン法は、一次微分の根を探索する割線法を多次元問題へ一般化したものである。多次元問題では、正割方程式は一意解を与えないため、準ニュートン法はどのように解を拘束するかによってことなる。BFGS法はこの種の手法の中で最も普及しているものの一つである。その他にも、BFGS法を限られたメモリで実行できるようにし、非常に多くの変数を扱えるように変更されたL-BFGS法も広く使われている。単純な矩形拘束を扱うBFGS-B法と呼ばれる変種も存在する。
このアルゴリズムの名前は、チャールズ・ジョージ・ブロイデン、ロジャー・フレッチャー、ドナルド・ゴールドファーブ、デイビッド・シャンノに因む。
最適化問題では、\mathbf{x}を R^n上のベクトル、 f(\mathbf{x})は微分可能なスカラー値関数とし、\mathbf{x} の取り得る値に制限はないものとして、f(\mathbf{x})を最小化する。
このアルゴリズムでは、初期推定値 \mathbf{x}_0から初め、各ステージ毎に反復的により良い推定値へと更新していく。
ステージ k における探索方向 pk  はニュートン方程式に類似した次の方程式を解くことにより得られる。
B_k \mathbf{p}_k = -\nabla f(\mathbf{x}_k),
ここで B_k はヘッセ行列の近似であり、各ステージ毎に反復的に更新する。\nabla f(\mathbf{x}_k) は xk で計算した勾配である。方向 pk を得たのち、この方向に向けて直線探索を行い、f(\mathbf{x}_k + \alpha\mathbf{p}_k) を最小とするようなスカラー \alpha > 0を求める。
B_kの更新において課される準ニュートン条件は以下の通りである。
B_{k+1} (\mathbf{x}_{k+1} - \mathbf{x}_k) = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)
\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k) および \mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k, B_{k+1} は B_{k+1} \mathbf{s}_k = \mathbf{y}_k曲率条件 \mathbf{s}_k^\top \mathbf{y}_k > 0 が満たされている必要がある。もし関数が強凸性を持たない場合、この条件を明示的に課す必要がある。
点 xk+1 における完全なヘッセ行列を計算して Bk+1 とする代わりに、二つの行列を次のように加算して近似ヘッセ行列を更新する。
￼
B_{k+1} = B_k + U_k + V_k
Uk および Vk はどちらも階数1の対称行列であるが、これらの和を取ることにより階数2の行列を用いて更新することとなる。BFGS法とDFP法は、以前の行列更新法と階数2の行列を更新に用いる点が異なる。階数1行列を用いる、より単純な手法は対称ランク1法と呼ばれ、正定値性が保証されない。B_{k+1} B_{k+1} = B_k + \alpha\mathbf{u}\mathbf{u}^\top + \beta\mathbf{v}\mathbf{v}^\top正割条件 B_{k+1} \mathbf{s}_k = \mathbf{y}_k  \mathbf{u} = \mathbf{y}_k および \mathbf{v} = B_k \mathbf{s}_k
\alpha = \frac{1}{\mathbf{y}_k^T \mathbf{s}_k}
\beta = -\frac{1}{\mathbf{s}_k^T  B_k \mathbf{s}_k}
上の \alpha および \beta を B_{k+1} = B_k + \alpha\mathbf{u}\mathbf{u}^\top + \beta\mathbf{v}\mathbf{v}^\top に代入して書き下すと、次のようになる。
B_{k+1} = B_k + \frac{\mathbf{y}_k \mathbf{y}_k^{\mathrm{T}}{\mathbf{y}_k^{\mathrm{T} \mathbf{s}_k} - \frac{B_k \mathbf{s}_k \mathbf{s}_k^{\mathrm{T} B_k^{\mathrm{T} }{\mathbf{s}_k^{\mathrm{T} B_k \mathbf{s}_k}
初期推定値 \mathbf{x}_0 と初期近似ヘッセ行列 B_0 から始め、次のステップを反復することにより、\mathbf{x}_k は解に収束する。
方向 \mathbf{p}_k を B_k \mathbf{p}_k = -\nabla f(\mathbf{x}_k)を解くことにより求める。
1次最適化(直線探索)によりステップサイズ \alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)を求める。
\mathbf{s}_k = \alpha_k \mathbf{p}_k とし、\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_kにより推定値を更新する。
\mathbf{y}_k = {\nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)}
B_{k+1} = B_k + \frac{\mathbf{y}_k \mathbf{y}_k^{\mathrm{T}}{\mathbf{y}_k^{\mathrm{T} \mathbf{s}_k} - \frac{B_k \mathbf{s}_k \mathbf{s}_k^{\mathrm{T} B_k }{\mathbf{s}_k^{\mathrm{T} B_k \mathbf{s}_k}
f(\mathbf{x}) は最小化の対象となる関数である。勾配のノルム ||\nabla f(\mathbf{x}_k)||を監視することにより収束判定を行う。 B_0 を B_0 = I のように初期化した場合、最初のステップは最急降下法と同等となるが、それ以降のステップでは近似ヘッシアン B_{k}の改善に伴って改善される。
このアルゴリズムのステップ1に用いられる B_kの逆行列は、シャーマン・モリソンの公式をステップ5に適用することにより次式のように計算することができる。
B_{k+1}^{-1} = \left(I - \frac{s_k y_k^T}{y_k^T s_k} \right) B_{k}^{-1} \left(I - \frac{y_k s_k^T}{y_k^T s_k} \right) + \frac{s_k s_k^T}{y_k^T s_k}
この計算は、B_k^{-1} が対称行列であり、\mathbf{y}_k^{\mathrm{T} B_k^{-1} \mathbf{y}_k および \mathbf{s}_k^{\mathrm{T} \mathbf{y}_k がスカラーであることを用いると次のように展開でき、行列を一時記憶領域に記憶する必要なく効率的に計算できる。
B_{k+1}^{-1} = B_k^{-1} + \frac{(\mathbf{s}_k^{\mathrm{T}\mathbf{y}_k+\mathbf{y}_k^{\mathrm{T} B_k^{-1} \mathbf{y}_k)(\mathbf{s}_k \mathbf{s}_k^{\mathrm{T})}{(\mathbf{s}_k^{\mathrm{T} \mathbf{y}_k)^2} - \frac{B_k^{-1} \mathbf{y}_k \mathbf{s}_k^{\mathrm{T} + \mathbf{s}_k \mathbf{y}_k^{\mathrm{T}B_k^{-1}{\mathbf{s}_k^{\mathrm{T} \mathbf{y}_k}
最尤推定やベイズ推定などの統計推定問題においては、最終的なヘッセ行列の逆行列を用いて解の信頼区間もしくは確信区間を推定することができる。しかし、これらの量は正確には真のヘッセ行列により定義されるものであり、BFGS近似は真のヘッセ行列に収束しない場合がある。
GSL は でBFGS法を実装している。 はBFGS法とL-BFGS法の両方を実装している。
SciPyでは、 関数がBFGS法を実装している。パラメータ L にとても大きな数を指定することにより、L-BFGS法を実行することもできる。
Octave は double-dogleg 近似を用いたBFGS法を  cubic line search に用いている。
R言語では、BFGS法(および矩形拘束を扱えるL-BFGS-B法)が基本関数 のオプションとして実装されている。
MATLAB Optimization Toolbox では、 関数が問題サイズを「中程度」に指定した場合にBFGS法を利用する。
C++ で実装され、高精度算術パッケージ  に統合されている高精度算術版BFGS法 () は(丸め誤差などの)数値的不安定性に対して頑強である。
他にも、C++ によるBFGS(およびL-BFGS, L-BFGS-B, CG, ニュートン法)の実装としては、MIT License で公開されている Eigen ライブラリが存在する。
オープンソースの C 実装としては、Gnu Regression, Econometrics and Time-series Library (gretl) がBFGSおよび L-BFGS法を含んでいる。