Loading AI tools
ウィキペディアから
数理最適化において、ブロイデン・フレッチャー・ゴールドファーブ・シャンノ法(英: Broyden–Fletcher–Goldfarb–Shanno algorithm)、略してBFGS法は、非制限非線形最適化問題に対する反復的解法の一つである[1]。関連の深いDFP法と同様、BFGS法は勾配のプレコンディショニング[訳語疑問点]を曲率の情報を用いて行うことにより降下方向を決定する。その際、損失関数のヘッセ行列の推定値を勾配(またはその推定値)のみを用いて(一般化)割線法により漸進的に改善する[2]。
この項目「BFGS法」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。(原文:en: Broyden–Fletcher–Goldfarb–Shanno algorithm) 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。(2024年8月) |
BFGS法における曲率行列の更新には逆行列の評価を要さないため、計算複雑度はに留まり、ニュートン法のよりも高速である。L-BFGS法もよく用いられ、メモリ使用量を限定できるため、多変数(e.g. >1000)問題に対する解法としてより適している。BFGS-B法はシンプルなボックス拘束を扱える[3]。
このアルゴリズムの名前は、チャールズ・ジョージ・ブロイデン、ロジャー・フレッチャー、ドナルド・ゴールドファーブ、デイビッド・シャンノに因む[4][5][6]。
を上のベクトル、 を微分可能なスカラー値関数とし、の取り得る値に制限はないものとして、を最小化する最適化問題を考える。
BFGS法は初期推定値から始め、各ステージ毎に反復的により良い推定値へと更新していく。
ステージkにおける降下方向 pkはニュートン方程式に類似した次の方程式を解くことにより得られる。
ここでBkはxkにおけるヘッセ行列の推定値であり、各ステージごとにxkにおける目的関数の勾配を用いて反復的に更新される。降下方向pkを得たのち、この方向に向けて直線探索を行い、を最小とするようなスカラーγ > 0を求め、次の点xk+1を決定する。
Bkの更新においては、以下の式であらわされる準ニュートン条件が課せられる。
ここでおよびとおくと、Bk+1は以下の正割方程式を満たす。
Bk+1が正定値行列であるためには曲率条件sk⊤yk>0が満たされる必要がある。この条件は正割方程式に左からsk⊤をかけることにより検証できる。目的関数が強凸関数でない場合、この条件は明示的に課す必要があり、これはたとえばxk+1を決定する際にウルフ条件を満たす点を選べばよい。
点xk+1におけるヘッセ行列を全て計算するかわりに、ステージkにおける推定値に次のように2つの行列を足すことによりBk+1を計算する。
UkおよびVkはどちらも階数1の対称行列であるが、これらの和を取ることにより階数2の対称行列を用いて更新することとなる。対称ランク1法と比べ、BFGS法とDFP法はどちらも階数2の行列を更新に用いる点が異なる。より単純な手法である対称ランク1法は階数1の行列を用いて更新を行うが、正定値性が保証されない。Bkの対称性と正定値性を維持するため、更新式はのように選ぶ。正割条件を課すと、およびとして以下を得る[7]。
最後に、 αおよびβをに代入するとBk+1の更新式は以下のように書ける。
非線形関数を対称とする非制限最適化問題を考える。
初期推定解および初期推定ヘッセ行列から始め、次の各ステップを反復することによりxkは解に収束する。
何らかの基準値ε > 0のもと、勾配のノルムがを満たしたとき解が収束したものとみなしアルゴリズムを終了する。
のように選んだ場合、最初のステップは最急降下法と等価となるが、以降のステップはBkがヘッセ行列を推定することにより徐々に改善される。
このアルゴリズムのステップ1はBkの逆行列を用いて実行されるが、この逆行列はステップ5でSherman–Morrisonの公式 を用いることにより次のように効率的に求めることができる。
この計算は が対称行列であり、 および sk⊤ykがスカラーであることをもちいて次のように展開でき、一時行列を要せず実行することができる。
したがって、逆行列をもとめるための計算を一切することなく、ヘッセ行列の逆行列そのものを推定することが可能である[8]。
初期推定解x0、ヘッセ行列の逆行列の推定値H0から始め、次の各ステップを反復することによりxkは解へと収束する。
最尤推定やベイズ推定などの統計推定問題においては、最終的なヘッセ行列の逆行列を用いて解の信頼区間もしくは確信区間を推定することができる [要出典]。しかし、これらの量は正確には真のヘッセ行列により定義されるものであり、BFGS近似は真のヘッセ行列に収束しない場合がある[9]。
BFGS更新公式は曲率sk⊤ykが常に正であり、ゼロから離れた下界があることに強く依拠している。この条件は凸な対称関数においてウルフ条件を用いた直線探索を用いる場合は満たされるが、実際の問題(たとえば逐次二次計画法)では負やほぼゼロの曲率があらわれることがしばしばある。このようなことは非凸関数を対象とする場合や直線探索ではなく信頼領域アプローチをとった場合におこることがある。この場合、BFGS法は誤った値をあたえることがある。
このような場合には、減衰BFGS更新[10]などと呼ばれる、skおよび/またはykを修正して頑健にした更新式が用いられることがある。
オープンソースの実装として有名なものは以下のようなものがあげられる。
fsolve関数は
信頼領域をもちいた一種のBFGS法を用いる。プロプライエタリな実装としては以下のようなものがあげられる。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.