ブロイデン・フレッチャー・ゴールドファーブ・シャノアルゴリズム

Optimization method

数値 最適化において、ブロイデン・フレッチャー・ゴールドファーブ・シャノ（BFGS）アルゴリズムは、制約のない非線形最適化問題を解くための反復法です。^[1]関連するデイビッドン・フレッチャー・パウエル法と同様に、BFGSは曲率情報を用いて勾配を前処理することで降下方向を決定します。これは、一般化セカント法を用いて勾配評価（または近似勾配評価）のみから得られる損失関数のヘッセ行列の近似値を徐々に改善することで行われます。^[2]

BFGS曲率行列の更新には逆行列が必要ないため、ニュートン法と比較して計算量はわずか です。また、BFGSのメモリ制限版であるL-BFGSもよく用いられています。これは、非常に多くの変数（例えば、1000以上）を持つ問題に適しています。BFGS-B版は、単純なボックス制約を扱います。^[3] BFGS行列はコンパクトな表現も許容するため、大規模な制約付き問題に適しています。 ${\displaystyle {\mathcal {O}}(n^{2})}$ ${\displaystyle {\mathcal {O}}(n^{3})}$

このアルゴリズムは、チャールズ・ジョージ・ブロイデン、ロジャー・フレッチャー、ドナルド・ゴールドファーブ、デイヴィッド・シャノにちなんで名付けられました。^{[4] [5] [6] [7]}これは、ジョン・グリーンシュタットによるより一般的なアルゴリズムの一例です。^[8]

根拠

最適化問題は、 を最小化することです。ここで、は のベクトルであり、は微分可能なスカラー関数です。 が取り得る値には制約はありません ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle f}$ ${\displaystyle \mathbf {x} }$

アルゴリズムは最適値の初期推定から始まり、各段階でより良い推定値を得るために反復的に進行します。 ${\displaystyle \mathbf {x} _{0}}$

ステージkにおける探索方向 p _kは、ニュートン方程式の類似体の解によって与えられる。

${\displaystyle B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k}),}$

ここで、は各段階で反復的に更新される におけるヘッセ行列の近似値であり、はx kで評価_される関数の勾配である_。次に、p k_方向の直線探索を用いて、_スカラー ${\displaystyle B_{k}}$ ${\displaystyle \mathbf {x} _{k}}$ ${\displaystyle \nabla f(\mathbf {x} _{k})}$ ${\displaystyle f(\mathbf {x} _{k}+\gamma \mathbf {p} _{k})}$ ${\displaystyle \gamma >0.}$

の更新に課される準ニュートン条件は ${\displaystyle B_{k}}$

${\displaystyle B_{k+1}(\mathbf {x} _{k+1}-\mathbf {x} _{k})=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k}).}$

とすると、 ${\displaystyle \mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$ ${\displaystyle \mathbf {s} _{k}=\mathbf {x} _{k+1}-\mathbf {x} _{k}}$ ${\displaystyle B_{k+1}}$

${\displaystyle B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}}$,

これは正割方程式です。

が正定値であるためには曲率条件を満たす必要があり、これは正割方程式にあらかじめ乗算することで確認できます。関数が強凸でない場合、例えば直線探索を用いて、曲率条件を伴うWolfe条件を満たす点x k+1を見つけるなど、条件を明示的に強制する必要が_あります ${\displaystyle \mathbf {s} _{k}^{\top }\mathbf {y} _{k}>0}$ ${\displaystyle B_{k+1}}$ ${\displaystyle \mathbf {s} _{k}^{T}}$

点における完全なヘッセ行列を として計算する必要はなく、ステージkにおける近似ヘッセ行列は2 つの行列を追加することで更新されます。 ${\displaystyle \mathbf {x} _{k+1}}$ ${\displaystyle B_{k+1}}$

${\displaystyle B_{k+1}=B_{k}+U_{k}+V_{k}.}$

と はどちらも対称ランク1行列ですが、それらの和はランク2の更新行列になります。BFGSとDFP更新行列はどちらも、ランク2行列であるという点で先行法と異なります。もう1つのより単純なランク1法は対称ランク1法として知られており、これはの正定値性を保証しません。 の対称性と正定値性を維持するために、更新形式を と選択することができます。セカント条件を課すと、となります。 と を選択すると、次式が得られます。^[9] ${\displaystyle U_{k}}$ ${\displaystyle V_{k}}$ ${\displaystyle B_{k+1}}$ ${\displaystyle B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }}$ ${\displaystyle B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}}$ ${\displaystyle \mathbf {u} =\mathbf {y} _{k}}$ ${\displaystyle \mathbf {v} =B_{k}\mathbf {s} _{k}}$

${\displaystyle \alpha ={\frac {1}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}},}$

${\displaystyle \beta =-{\frac {1}{\mathbf {s} _{k}^{T}B_{k}\mathbf {s} _{k}}}.}$

最後に、とをに代入して、の更新方程式を取得します。 ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }}$ ${\displaystyle B_{k+1}}$

${\displaystyle 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}}}.}$

アルゴリズム

非線形で2回微分可能な目的関数である次の制約なし最適化問題を考えます $${\displaystyle {\begin{aligned}{\underset {\mathbf {x} \in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(\mathbf {x} ),\end{aligned}}}$$ ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$

初期推定値とヘッセ行列の初期推定値から、解に収束するまで次の手順を繰り返します。 ${\displaystyle \mathbf {x} _{0}\in \mathbb {R} ^{n}}$ ${\displaystyle B_{0}\in \mathbb {R} ^{n\times n}}$ ${\displaystyle \mathbf {x} _{k}}$

1. を解いて方向を取得します。 ${\displaystyle \mathbf {p} _{k}}$ ${\displaystyle B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}$
2. 1次元最適化（直線探索）を実行し、最初のステップで求めた方向における許容可能なステップサイズを見つけます。正確な直線探索を実行すると、 となります。実際には、通常は不正確な直線探索で十分であり、許容可能な はWolfe条件 を満たします。 ${\displaystyle \alpha _{k}}$ ${\displaystyle \alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ ${\displaystyle \alpha _{k}}$
3. 設定して更新します。 ${\displaystyle \mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}}$ ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}}$
4. ${\displaystyle \mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}}$。
5. ${\displaystyle 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}}}}$。

収束は勾配のノルムを観察することで判断できます。ある が与えられた場合、 のときにアルゴリズムを停止できます。がで初期化された場合、最初のステップは勾配降下法と同等になりますが、それ以降のステップは によってますます洗練されていきます。これはヘッセ行列の近似です ${\displaystyle \epsilon >0}$ ${\displaystyle ||\nabla f(\mathbf {x} _{k})||\leq \epsilon .}$ ${\displaystyle B_{0}}$ ${\displaystyle B_{0}=I}$ ${\displaystyle B_{k}}$

アルゴリズムの最初のステップは行列の逆行列を使って実行される。これは、アルゴリズムのステップ5にシャーマン・モリソンの公式を適用することで効率的に得られ、 ${\displaystyle B_{k}}$

${\displaystyle B_{k+1}^{-1}=\left(I-{\frac {\mathbf {s} _{k}\mathbf {y} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}\right)B_{k}^{-1}\left(I-{\frac {\mathbf {y} _{k}\mathbf {s} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}\right)+{\frac {\mathbf {s} _{k}\mathbf {s} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}.}$

これは、対称行列であること、およびスカラーであることを認識して、次のような展開を用いることで、一時行列を使わずに効率的に計算することができる。 ${\displaystyle B_{k}^{-1}}$ ${\displaystyle \mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}\mathbf {y} _{k}}$ ${\displaystyle \mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}}$

${\displaystyle 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}}}.}$

したがって、逆行列を避けるために、ヘッセ行列そのものではなく、ヘッセ行列の逆行列を近似することができる。 ^[10] ${\displaystyle H_{k}{\overset {\operatorname {def} }{=}}B_{k}^{-1}.}$

初期推定値と近似逆ヘッセ行列から、解に収束するまで次の手順を繰り返します。 ${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle H_{0}}$ ${\displaystyle \mathbf {x} _{k}}$

1. を解いて方向を取得します。 ${\displaystyle \mathbf {p} _{k}}$ ${\displaystyle \mathbf {p} _{k}=-H_{k}\nabla f(\mathbf {x} _{k})}$
2. 1次元最適化（直線探索）を実行し、最初のステップで求めた方向における許容可能なステップサイズを見つけます。正確な直線探索を実行すると、 となります。実際には、通常は不正確な直線探索で十分であり、許容可能な はWolfe条件 を満たします。 ${\displaystyle \alpha _{k}}$ ${\displaystyle \alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ ${\displaystyle \alpha _{k}}$
3. 設定して更新します。 ${\displaystyle \mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}}$ ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}}$
4. ${\displaystyle \mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}}$。
5. ${\displaystyle H_{k+1}=H_{k}+{\frac {(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}+\mathbf {y} _{k}^{\mathrm {T} }H_{k}\mathbf {y} _{k})(\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} })}{(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k})^{2}}}-{\frac {H_{k}\mathbf {y} _{k}\mathbf {s} _{k}^{\mathrm {T} }+\mathbf {s} _{k}\mathbf {y} _{k}^{\mathrm {T} }H_{k}}{\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}}}}$。

統計的推定問題（最大尤度法やベイズ推論など）においては、解の信頼区間は最終的なヘッセ行列の逆行列から推定することができる[要出典] 。^{しかし、これら}の量は厳密には真のヘッセ行列によって定義されるため、BFGS近似は真のヘッセ行列に収束しない可能性がある^{[11] 。}

さらなる発展

BFGS更新式は、曲率が厳密に正であり、ゼロから離れた有界性を持つことに大きく依存しています。この条件は、凸目標に対してWolfe条件付き直線探索を実行すると満たされます。しかし、実際の応用（逐次二次計画法など）では、負またはほぼゼロの曲率が日常的に生成されます。これは、非凸目標を最適化する場合、または直線探索の代わりに信頼領域アプローチを使用する場合に発生する可能性があります。また、目標のノイズによって誤った値が生成される可能性もあります ${\displaystyle \mathbf {s} _{k}^{\top }\mathbf {y} _{k}}$

このような場合には、いわゆる減衰BFGS更新の1つを使用することができる（^[12]を参照）。これは、より堅牢な更新を得るために、および/またはを修正する。 ${\displaystyle \mathbf {s} _{k}}$ ${\displaystyle \mathbf {y} _{k}}$

注目すべき実装

注目すべきオープンソース実装は次のとおりです。

• ALGLIBは、BFGSとそのメモリ制限バージョンをC++およびC#で実装しています
• GNU Octave は、信頼領域拡張を伴うBFGS の形式をそのfsolve機能で使用します。
• GSLはBFGSをgsl_multimin_fdfminimizer_vector_bfgs2として実装している。^[13]
• Rでは、BFGSアルゴリズム（およびボックス制約を許可するL-BFGS-Bバージョン）は、基本関数optim()のオプションとして実装されています。^[14]
• SciPyでは、 scipy.optimize.fmin_bfgs 関数がBFGSを実装しています。^{[15]また、パラメータLを非常に大きな値に設定することで、} L-BFGSアルゴリズムのいずれかを用いてBFGSを実行することも可能になります。これは、制約なしで scipy.optimize.minimize を実行する際のデフォルトのメソッドの一つでもあります。^[16]
• Juliaでは、Optim.jlパッケージがBFGSとL-BFGSをoptimize()関数のソルバーオプションとして実装しています（他のオプションも含まれています）。^[17]
• Stan は、最大尤度推定問題と最大事後推定問題を解決するためのオプションとして、自動微分とともに BFGS を実装します。

注目すべき独自の実装には次のものがあります。

• 大規模非線形最適化ソフトウェアArtelys Knitro は、BFGS アルゴリズムと L-BFGS アルゴリズムの両方を実装しています。
• MATLAB Optimization Toolboxでは、問題のサイズが「中規模」に設定されている場合に、 fminunc 関数は 3 次直線探索による BFGS を使用します。
• Mathematica には BFGS が含まれています。
• LS-DYNA は暗黙的な問題を解決するために BFGS も使用します。

参照

• BHHHアルゴリズム
• ダビドン・フレッチャー・パウエルの公式
• 勾配降下法
• L-BFGS
• レーベンバーグ・マルカート法
• ネルダー・ミード法
• パターン探索（最適化）
• 準ニュートン法
• 対称ランク1
• コンパクト準ニュートン表現

参考文献

1. フレッチャー、ロジャー（1987）、最適化の実践的手法（第2版）、ニューヨーク：ジョン・ワイリー・アンド・サンズ、ISBN 978-0-471-91547-8
2. デニス、JE Jr.、シュナーベル、ロバート B. (1983)、「制約なし最小化のためのセカント法」、制約なし最適化と非線形方程式の数値解析、ニュージャージー州エングルウッド・クリフス：プレンティス・ホール、  194～ 215ページ、ISBN 0-13-627216-9
3. バード、リチャード・H.; ルー、ペイファン; ノセダル、ホルヘ; チュー、シヨウ (1995)、「境界制約最適化のためのメモリ制限アルゴリズム」、SIAM Journal on Scientific Computing、16 (5): 1190– 1208、CiteSeerX 10.1.1.645.5814、doi :10.1137/0916069 
4. Broyden, CG (1970)、「ダブルランク最小化アルゴリズムのクラスの収束」、数学とその応用研究所誌、6 : 76–90、doi :10.1093/imamat/6.1.76
5. Fletcher, R. (1970)、「可変メトリックアルゴリズムへの新しいアプローチ」、Computer Journal、13 (3): 317– 322、doi : 10.1093/comjnl/13.3.317
6. ゴールドファーブ, D. (1970)、「変分平均によって導出される可変メトリック更新のファミリー」、計算数学、24 (109): 23– 26、doi : 10.1090/S0025-5718-1970-0258249-6
7. Shanno, David F. (1970年7月)、「関数最小化のための準ニュートン法の条件付け」、Mathematics of Computation、24 (111): 647– 656、doi : 10.1090/S0025-5718-1970-0274029-X、MR  0274029
8. Greenstadt, J. (1970). 「変数メトリック法のバリエーション（考察付き）」.計算数学. 24 (109): 1– 22. doi :10.1090/S0025-5718-1970-0258248-4. ISSN  0025-5718.
9. フレッチャー、ロジャー（1987）、最適化の実践的手法（第2版）、ニューヨーク：ジョン・ワイリー・アンド・サンズ、ISBN 978-0-471-91547-8
10. ノセダル、ホルヘ、ライト、スティーブン・J. (2006)、『数値最適化（第2版）』、ベルリン、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-0-387-30303-1
11. Ge, Ren-pu; Powell, MJD (1983). 「制約なし最適化における可変計量行列の収束」.数理計画. 27 (2). 123. doi :10.1007/BF02591941. S2CID  8113073
12. Jorge Nocedal、Stephen J. Wright (2006)、数値最適化
13. 「GNU Scientific Library — GSL 2.6 ドキュメント」www.gnu.org . 2020年11月22日閲覧。
14. 「R: 汎用最適化」. stat.ethz.ch . 2020年11月22日閲覧。
15. "scipy.optimize.fmin_bfgs — SciPy v1.5.4 リファレンスガイド". docs.scipy.org . 2020年11月22日閲覧。
16. "scipy.optimize.minimize — SciPy v1.5.4 リファレンスガイド". docs.scipy.org . 2025年1月22日閲覧。
17. 「Optim.jl 設定可能オプション」。julianlsolvers。

さらに詳しい参考文献

• アヴリエル、モーデカイ（2003年）、非線形計画法：分析と方法、ドーバー出版、ISBN 978-0-486-43227-4
• ボナンズ、J.フレデリック、ギルバート、J.チャールズ、ルマレシャル、クロード、サガスティザバル、クラウディア・A. (2006)、「ニュートン法」『数値最適化：理論と実践』 （第2版）、ベルリン：シュプリンガー、 51～ 66ページ 、ISBN 3-540-35445-X
• フレッチャー、ロジャー（1987年）、最適化の実践的手法（第2版）、ニューヨーク：ジョン・ワイリー・アンド・サンズ、ISBN 978-0-471-91547-8
• Luenberger, David G. ; Ye, Yinyu (2008),線形計画法と非線形計画法、International Series in Operations Research & Management Science、第116巻（第3版）、ニューヨーク：Springer、pp. xiv+546、ISBN 978-0-387-74502-2、MR  2423726
• Kelley, CT (1999)、『反復法による最適化』、フィラデルフィア：産業応用数学協会、  71～ 86ページ、ISBN 0-89871-433-8

Retrieved from "https://en.wikipedia.org/w/index.php?title=Broyden–Fletcher–Goldfarb–Shanno_algorithm&oldid=1326793485"