BFGS法

ウィキペディア

BFGS法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/05 14:58 UTC 版)

この項目「BFGS法」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en: Broyden–Fletcher–Goldfarb–Shanno algorithm） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2024年8月）

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

BFGS法における曲率行列の更新には逆行列の評価を要さないため、計算複雑度（英語版）は${\displaystyle {\mathcal {O}}(n^{2})}$

Optimization computes maxima and minima.

非線形（制約付き）

一般	バリア関数 ペナルティ関数法
微分可能	ラグランジュの未定乗数法 拡張ラグランジュ乗数法（英語版） 逐次二次計画法 逐次線形計画法

凸最適化

凸縮小化	切除平面法 簡約勾配法 劣勾配法
線形 および 二次	内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法）
グラフ理論	最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法
ネットワークフロー (最大流問題)	ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法（英語版）

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• ベイスンホッピング法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア