PROFILPELAJAR.COM

数理最適化において、ブロイデン・フレッチャー・ゴールドファーブ・シャンノ法(英: Broyden–Fletcher–Goldfarb–Shanno algorithm)、略してBFGS法は、非制限非線形最適化問題に対する反復的解法の一つである^[1]。関連の深いDFP法と同様、BFGS法は勾配のプレコンディショニング^{[訳語疑問点]}を曲率の情報を用いて行うことにより降下方向を決定する。その際、損失関数のヘッセ行列の推定値を勾配(またはその推定値)のみを用いて(一般化)割線法により漸進的に改善する^[2]。

BFGS法における曲率行列の更新には逆行列の評価を要さないため、計算複雑度（英語版）は ${\mathcal {O}}(n^{2})$ に留まり、ニュートン法の ${\mathcal {O}}(n^{3})$ よりも高速である。L-BFGS法もよく用いられ、メモリ使用量を限定できるため、多変数(e.g. >1000)問題に対する解法としてより適している。BFGS-B法はシンプルなボックス拘束を扱える^[3]。

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

理論的根拠

${\boldsymbol {x}}$ を $\mathbb {R} ^{n}$ 上のベクトル、 $f({\boldsymbol {x}})$ を微分可能なスカラー値関数とし、 ${\boldsymbol {x}}$ の取り得る値に制限はないものとして、 $f({\boldsymbol {x}})$ を最小化する最適化問題を考える。

BFGS法は初期推定値 ${\boldsymbol {x}}_{0}$ から始め、各ステージ毎に反復的により良い推定値へと更新していく。

ステージ $k$ における降下方向（英語版） $p k$ はニュートン方程式に類似した次の方程式を解くことにより得られる。

B_{k}{\boldsymbol {p}}_{k}=-\nabla f({\boldsymbol {x}}_{k})

ここで $B k$ は $x k$ におけるヘッセ行列の推定値であり、各ステージごとに $x k$ における目的関数の勾配 $\nabla f({\boldsymbol {x}}_{k})$ を用いて反復的に更新される。降下方向 $p k$ を得たのち、この方向に向けて直線探索を行い、 $f({\boldsymbol {x}}_{k}+\gamma {\boldsymbol {p}}_{k})$ を最小とするようなスカラー $γ > 0$ を求め、次の点 $x k +1$ を決定する。

$B k$ の更新においては、以下の式であらわされる準ニュートン条件が課せられる。

B_{k+1}({\boldsymbol {x}}_{k+1}-{\boldsymbol {x}}_{k})=\nabla f({\boldsymbol {x}}_{k+1})-\nabla f({\boldsymbol {x}}_{k})

ここで ${\boldsymbol {y}}_{k}=\nabla f({\boldsymbol {x}}_{k+1})-\nabla f({\boldsymbol {x}}_{k})$ および ${\boldsymbol {s}}_{k}={\boldsymbol {x}}_{k+1}-{\boldsymbol {x}}_{k}$ とおくと、 $B k +1$ は以下の正割方程式を満たす。

B_{k+1}{\boldsymbol {s}}_{k}={\boldsymbol {y}}_{k}

$B k +1$ が正定値行列であるためには曲率条件 $s k ⊤ y k >0$ が満たされる必要がある。この条件は正割方程式に左から $s k ⊤$ をかけることにより検証できる。目的関数が強凸関数でない場合、この条件は明示的に課す必要があり、これはたとえば $x k +1$ を決定する際にウルフ条件を満たす点を選べばよい。

点 $x k +1$ におけるヘッセ行列を全て計算するかわりに、ステージ $k$ における推定値に次のように2つの行列を足すことにより $B k +1$ を計算する。

B_{k+1}=B_{k}+U_{k}+V_{k}

$U k$ および $V k$ はどちらも階数1の対称行列であるが、これらの和を取ることにより階数2の対称行列を用いて更新することとなる。対称ランク1（英語版）法と比べ、BFGS法とDFP法はどちらも階数2の行列を更新に用いる点が異なる。より単純な手法である対称ランク1法は階数1の行列を用いて更新を行うが、正定値性が保証されない。 $B k$ の対称性と正定値性を維持するため、更新式は $B_{k+1}=B_{k}+\alpha {\boldsymbol {u}}{\boldsymbol {u}}^{\top }+\beta {\boldsymbol {v}}{\boldsymbol {v}}^{\top }$ のように選ぶ。正割条件 $B_{k+1}{\boldsymbol {s}}_{k}={\boldsymbol {y}}_{k}$ を課すと、 ${\boldsymbol {u}}={\boldsymbol {y}}_{k}$ および ${\boldsymbol {v}}=B_{k}{\boldsymbol {s}}_{k}$ として以下を得る^[7]。

\alpha ={\frac {1}{{\boldsymbol {y}}_{k}^{\top }{\boldsymbol {s}}_{k}}}

\beta =-{\frac {1}{{\boldsymbol {s}}_{k}^{\top }B_{k}{\boldsymbol {s}}_{k}}}

最後に、 $α$ および $β$ を $B_{k+1}=B_{k}+\alpha {\boldsymbol {u}}{\boldsymbol {u}}^{\top }+\beta {\boldsymbol {v}}{\boldsymbol {v}}^{\top }$ に代入すると $B k +1$ の更新式は以下のように書ける。

B_{k+1}=B_{k}+{\frac {{\boldsymbol {y}}_{k}{\boldsymbol {y}}_{k}^{\top }}{{\boldsymbol {y}}_{k}^{\top }{\boldsymbol {s}}_{k}}}-{\frac {B_{k}{\boldsymbol {s}}_{k}{\boldsymbol {s}}_{k}^{\top }B_{k}^{\top }}{{\boldsymbol {s}}_{k}^{\top }B_{k}{\boldsymbol {s}}_{k}}}

アルゴリズム

非線形関数 $f:\mathbb {R} ^{n}\to \mathbb {R}$ を対称とする非制限最適化問題 ${\begin{aligned}{\underset {{\boldsymbol {x}}\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f({\boldsymbol {x}})\end{aligned}}$ を考える。

初期推定解 ${\boldsymbol {x}}_{0}\in \mathbb {R} ^{n}$ および初期推定ヘッセ行列 $B_{0}\in \mathbb {R} ^{n\times n}$ から始め、次の各ステップを反復することにより $x k$ は解に収束する。

降下方向 $p k$ を $B_{k}{\boldsymbol {p}}_{k}=-\nabla f({\boldsymbol {x}}_{k})$ を解くことにより求める。
1次元最適化(直線探索)を行い、前ステップで求めた降下方向に向う許容しうるステップサイズ $α k$ を求める。厳密な直線探索が行われた場合、 $\alpha _{k}=\arg \min f({\boldsymbol {x}}_{k}+\alpha {\boldsymbol {p}}_{k})$ となる。実用上は $α k$ がウルフ条件を満たすことをもって許容する、非厳密な直線探索で十分なことが多い。
${\boldsymbol {s}}_{k}=\alpha _{k}{\boldsymbol {p}}_{k}$ とし、 ${\boldsymbol {x}}_{k+1}={\boldsymbol {x}}_{k}+{\boldsymbol {s}}_{k}$ により推定解を更新する。
${\boldsymbol {y}}_{k}={\nabla f({\boldsymbol {x}}_{k+1})-\nabla f({\boldsymbol {x}}_{k})}$ を計算する。
$B_{k+1}=B_{k}+{\frac {{\boldsymbol {y}}_{k}{\boldsymbol {y}}_{k}^{\top }}{{\boldsymbol {y}}_{k}^{\top }{\boldsymbol {s}}_{k}}}-{\frac {B_{k}{\boldsymbol {s}}_{k}{\boldsymbol {s}}_{k}^{\top }B_{k}^{\top }}{{\boldsymbol {s}}_{k}^{\top }B_{k}{\boldsymbol {s}}_{k}}}$ により推定ヘッセ行列を更新する。

何らかの基準値 $ε > 0$ のもと、勾配のノルムが $||\nabla f({\boldsymbol {x}}_{k})||\leq \varepsilon$ を満たしたとき解が収束したものとみなしアルゴリズムを終了する。

$B_{0}=I$ のように選んだ場合、最初のステップは最急降下法と等価となるが、以降のステップは $B k$ がヘッセ行列を推定することにより徐々に改善される。

このアルゴリズムのステップ1は $B k$ の逆行列を用いて実行されるが、この逆行列はステップ5でSherman–Morrisonの公式（英語版）を用いることにより次のように効率的に求めることができる。

B_{k+1}^{-1}=\left(I-{\frac {{\boldsymbol {s}}_{k}{\boldsymbol {y}}_{k}^{\top }}{{\boldsymbol {y}}_{k}^{\top }{\boldsymbol {s}}_{k}}}\right)B_{k}^{-1}\left(I-{\frac {{\boldsymbol {y}}_{k}{\boldsymbol {s}}_{k}^{\top }}{{\boldsymbol {y}}_{k}^{\top }{\boldsymbol {s}}_{k}}}\right)+{\frac {{\boldsymbol {s}}_{k}{\boldsymbol {s}}_{k}^{\top }}{{\boldsymbol {y}}_{k}^{\top }{\boldsymbol {s}}_{k}}}

この計算は $B_{k}^{-1}$ が対称行列であり、 ${\boldsymbol {y}}_{k}^{\top }B_{k}^{-1}{\boldsymbol {y}}_{k}$ および $s k ⊤ y k$ がスカラーであることをもちいて次のように展開でき、一時行列を要せず実行することができる。

B_{k+1}^{-1}=B_{k}^{-1}+{\frac {({\boldsymbol {s}}_{k}^{\top }{\boldsymbol {y}}_{k}+{\boldsymbol {y}}_{k}^{\top }B_{k}^{-1}{\boldsymbol {y}}_{k})({\boldsymbol {s}}_{k}{\boldsymbol {s}}_{k}^{\top })}{({\boldsymbol {s}}_{k}^{\top }{\boldsymbol {y}}_{k})^{2}}}-{\frac {B_{k}^{-1}{\boldsymbol {y}}_{k}{\boldsymbol {s}}_{k}^{\top }+{\boldsymbol {s}}_{k}{\boldsymbol {y}}_{k}^{\top }B_{k}^{-1}}{{\boldsymbol {s}}_{k}^{\top }{\boldsymbol {y}}_{k}}}.

したがって、逆行列をもとめるための計算を一切することなく、ヘッセ行列の逆行列 $H_{k}{\overset {\operatorname {def} }{=}}B_{k}^{-1}$ そのものを推定することが可能である^[8]。

初期推定解 $x 0$ 、ヘッセ行列の逆行列の推定値 $H 0$ から始め、次の各ステップを反復することにより $x k$ は解へと収束する。

降下方向 $p k$ を ${\boldsymbol {p}}_{k}=-H_{k}\nabla f({\boldsymbol {x}}_{k})$ により得る。
1次元最適化(直線探索)を行い、前ステップで求めた降下方向に向う許容しうるステップサイズ $α k$ を求める。厳密な直線探索が行われた場合、 $\alpha _{k}=\arg \min f({\boldsymbol {x}}_{k}+\alpha {\boldsymbol {p}}_{k})$ となる。実用上は $α k$ がウルフ条件を満たすことをもって許容する、非厳密な直線探索で十分なことが多い。
${\boldsymbol {s}}_{k}=\alpha _{k}{\boldsymbol {p}}_{k}$ とし、 ${\boldsymbol {x}}_{k+1}={\boldsymbol {x}}_{k}+{\boldsymbol {s}}_{k}$ により推定解を更新する。
${\boldsymbol {y}}_{k}={\nabla f({\boldsymbol {x}}_{k+1})-\nabla f({\boldsymbol {x}}_{k})}$ を計算する。
$H_{k+1}=H_{k}+{\frac {({\boldsymbol {s}}_{k}^{\top }{\boldsymbol {y}}_{k}+{\boldsymbol {y}}_{k}^{\top }H_{k}{\boldsymbol {y}}_{k})({\boldsymbol {s}}_{k}{\boldsymbol {s}}_{k}^{\top })}{({\boldsymbol {s}}_{k}^{\top }{\boldsymbol {y}}_{k})^{2}}}-{\frac {H_{k}{\boldsymbol {y}}_{k}{\boldsymbol {s}}_{k}^{\top }+{\boldsymbol {s}}_{k}{\boldsymbol {y}}_{k}^{\top }H_{k}}{{\boldsymbol {s}}_{k}^{\top }{\boldsymbol {y}}_{k}}}$ によりヘッセ行列の逆行列の推定値を計算する。

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

発展

BFGS更新公式は曲率 $s k ⊤ y k$ が常に正であり、ゼロから離れた下界があることに強く依拠している。この条件は凸な対称関数においてウルフ条件を用いた直線探索を用いる場合は満たされるが、実際の問題(たとえば逐次二次計画法)では負やほぼゼロの曲率があらわれることがしばしばある。このようなことは非凸関数を対象とする場合や直線探索ではなく信頼領域アプローチをとった場合におこることがある。この場合、BFGS法は誤った値をあたえることがある。

このような場合には、減衰BFGS更新^[10]などと呼ばれる、 $s k$ および/または $y k$ を修正して頑健にした更新式が用いられることがある。

実装

オープンソースの実装として有名なものは以下のようなものがあげられる。

ALGLIBはC++およびC#用のBFGSおよびL-BFGS法を実装する。
GNU Octaveのfsolve関数は信頼領域をもちいた一種のBFGS法を用いる。
GSLはgsl_multimin_fdfminimizer_vector_bfgs2関数としてBFGSを実装している^[11]。
R言語では、、BFGS法（および矩形拘束を扱えるL-BFGS-B法）が基本関数optim()のオプションとして実装されている^[12]。
SciPyでは、scipy.optimize.fmin_bfgs関数がBFGS法を実装している^[13]。パラメータLにとても大きな数を指定することにより、なんらかのL-BFGS法を実行することもできる。
Juliaでは、Optim.jlパッケージにBFGSおよびL-BFGSが実装されている^[14]。

プロプライエタリな実装としては以下のようなものがあげられる。

大規模非線形最適化ソフトウェアArtelys KnitroはBFGS法およびL-BFGS法の両方を実装する。
MATLAB Optimization Toolboxでは、fminunc関数がBFGS法を3次直線探索と組み合わせたアルゴリズムを「中規模スケール」の問題向けに実装している。
MathematicaにはBFGS法が含まれる。
LS-DYNAもBFGS法を用いて陰解を求めている。