BFGS法

テンプレート:翻訳直後

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

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

このアルゴリズムの名前は、テンプレート:仮リンク、ロジャー・フレッチャー、テンプレート:仮リンク、テンプレート:仮リンクに因む^[4]^[5]^[6]。

理論的根拠

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

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

ステージテンプレート:Mvarにおけるテンプレート:仮リンクテンプレート:Mathはニュートン方程式に類似した次の方程式を解くことにより得られる。

B_{k} 𝒑_{k} = - \nabla f (𝒙_{k})

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

テンプレート:Mathの更新においては、以下の式であらわされる準ニュートン条件が課せられる。

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

ここで $𝒚_{k} = \nabla f (𝒙_{k + 1}) - \nabla f (𝒙_{k})$ および $𝒔_{k} = 𝒙_{k + 1} - 𝒙_{k}$ とおくと、テンプレート:Mathは以下の正割方程式を満たす。

B_{k + 1} 𝒔_{k} = 𝒚_{k}

テンプレート:Mathが正定値行列であるためには曲率条件テンプレート:Mathが満たされる必要がある。この条件は正割方程式に左からテンプレート:Mathをかけることにより検証できる。目的関数が強凸関数でない場合、この条件は明示的に課す必要があり、これはたとえばテンプレート:Mathを決定する際にウルフ条件を満たす点を選べばよい。

点テンプレート:Mathにおけるヘッセ行列を全て計算するかわりに、ステージテンプレート:Mvarにおける推定値に次のように2つの行列を足すことによりテンプレート:Mathを計算する。

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

テンプレート:Mathおよびテンプレート:Mathはどちらも階数1の対称行列であるが、これらの和を取ることにより階数2の対称行列を用いて更新することとなる。対称ランクワン法と比べ、BFGS法とDFP法はどちらも階数2の行列を更新に用いる点が異なる。より単純な手法である対称ランクワン法は階数1の行列を用いて更新を行うが、正定値性が保証されない。テンプレート:Mathの対称性と正定値性を維持するため、更新式は $B_{k + 1} = B_{k} + α 𝒖 𝒖^{⊤} + β 𝒗 𝒗^{⊤}$ のように選ぶ。正割条件 $B_{k + 1} 𝒔_{k} = 𝒚_{k}$ を課すと、 $𝒖 = 𝒚_{k}$ および $𝒗 = B_{k} 𝒔_{k}$ として以下を得る^[7]。

α = \frac{1}{𝒚_{k}^{⊤} 𝒔_{k}}

β = - \frac{1}{𝒔_{k}^{⊤} B_{k} 𝒔_{k}}

最後に、テンプレート:Mvarおよびテンプレート:Mvarを $B_{k + 1} = B_{k} + α 𝒖 𝒖^{⊤} + β 𝒗 𝒗^{⊤}$ に代入するとテンプレート:Mathの更新式は以下のように書ける。

B_{k + 1} = B_{k} + \frac{𝒚_{k} 𝒚_{k}^{⊤}}{𝒚_{k}^{⊤} 𝒔_{k}} - \frac{B_{k} 𝒔_{k} 𝒔_{k}^{⊤} B_{k}^{⊤}}{𝒔_{k}^{⊤} B_{k} 𝒔_{k}}

アルゴリズム

非線形関数 $f : ℝ^{n} \to ℝ$ を対象とした無制約最適化問題 $\begin{matrix} \underset{𝒙 \in ℝ^{n}}{minimize} & f (𝒙) \end{matrix}$ を考える。

初期推定解 $𝒙_{0} \in ℝ^{n}$ および初期推定ヘッセ行列 $B_{0} \in ℝ^{n \times n}$ から始め、次の各ステップを反復することによりテンプレート:Mathは解に収束する。

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

何らかの基準値テンプレート:Mathのもと、勾配のノルムが $| | \nabla f (𝒙_{k}) | | \leq ε$ を満たしたとき解が収束したものとみなしアルゴリズムを終了する。

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

このアルゴリズムのステップ1はテンプレート:Mathの逆行列を用いて実行されるが、この逆行列はステップ5でテンプレート:仮リンクを用いることにより次のように効率的に求めることができる。

B_{k + 1}^{- 1} = (I - \frac{𝒔_{k} 𝒚_{k}^{⊤}}{𝒚_{k}^{⊤} 𝒔_{k}}) B_{k}^{- 1} (I - \frac{𝒚_{k} 𝒔_{k}^{⊤}}{𝒚_{k}^{⊤} 𝒔_{k}}) + \frac{𝒔_{k} 𝒔_{k}^{⊤}}{𝒚_{k}^{⊤} 𝒔_{k}}

この計算は $B_{k}^{- 1}$ が対称行列であり、 $𝒚_{k}^{⊤} B_{k}^{- 1} 𝒚_{k}$ およびテンプレート:Mathがスカラーであることを用いて次のように展開でき、一時行列を要せず実行することができる。

B_{k + 1}^{- 1} = B_{k}^{- 1} + \frac{(𝒔_{k}^{⊤} 𝒚_{k} + 𝒚_{k}^{⊤} B_{k}^{- 1} 𝒚_{k}) (𝒔_{k} 𝒔_{k}^{⊤})}{(𝒔_{k}^{⊤} 𝒚_{k})^{2}} - \frac{B_{k}^{- 1} 𝒚_{k} 𝒔_{k}^{⊤} + 𝒔_{k} 𝒚_{k}^{⊤} B_{k}^{- 1}}{𝒔_{k}^{⊤} 𝒚_{k}} .

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

初期推定解テンプレート:Math、ヘッセ行列の逆行列の推定値テンプレート:Mathから始め、次の各ステップを反復することによりテンプレート:Mathは解へと収束する。

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

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

発展

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

このような場合には、減衰BFGS更新^[10]などと呼ばれる、テンプレート:Mathおよび/またはテンプレート:Mathを修正して頑健にした更新式が用いられることがある。

実装

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

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法を用いて陰解を求めている。

脚注

テンプレート:脚注ヘルプテンプレート:Reflist

外部リンク

Source code of high-precision BFGS

テンプレート:最適化アルゴリズム

[1] テンプレート:Citation

[2] テンプレート:Citation

[3] テンプレート:Citation

[4] テンプレート:Citation

[5] テンプレート:Citation

[6] テンプレート:Citation

[7] テンプレート:Citation

[Nocedal-8] テンプレート:Citation

[9] テンプレート:Cite journal

[10] テンプレート:Citation

[11] テンプレート:Cite web

[12] テンプレート:Cite web

[13] テンプレート:Cite web

[14] テンプレート:Cite web

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

BFGS法

目次

理論的根拠

アルゴリズム

発展

実装

脚注

関連文献

関連項目

外部リンク

ナビゲーションメニュー

BFGS法

理論的根拠

アルゴリズム

発展

実装

脚注

関連文献

関連項目

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー