DFP法

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

Davidon–Fletcher–Powell法またはDFP法とは、あるセカント方程式を満たす解のうち、現在の推定値に最も近く、曲率条件を満たす解を与える式（DFP公式）を用いる準ニュートン法である。名称はWilliam C. Davidon、Roger Fletcher、Michael JD Powellに因む。セカント法を多次元問題に一般化したものであり、準ニュートン法としては初めての解法だった。この公式によりヘッセ行列を更新すれば、対称性と正定性が保証される。

所与の関数${\displaystyle f(x)}$ のテイラー展開は、その勾配( ${\displaystyle \nabla f}$ )、正定値ヘッセ行列${\displaystyle B}$ 、を用いて以下のように書ける。

${\displaystyle f(x_{k}+s_{k})=f(x_{k})+\nabla f(x_{k})^{T}s_{k}+{\frac {1}{2}}s_{k}^{T}{B}s_{k}+\dots ,}$

また、勾配自体のテイラー展開（セカント方程式）は以下のように書ける。

${\displaystyle \nabla f(x_{k}+s_{k})=\nabla f(x_{k})+Bs_{k}+\dots }$

これを${\displaystyle B}$の更新に用いる。

下に示すDFP公式は、対称かつ正定値であり、現在の近似値${\displaystyle B_{k}}$に最も近い解を与える。

${\displaystyle B_{k+1}=(I-\gamma _{k}y_{k}s_{k}^{T})B_{k}(I-\gamma _{k}s_{k}y_{k}^{T})+\gamma _{k}y_{k}y_{k}^{T},}$

ここで、

${\displaystyle y_{k}=\nabla f(x_{k}+s_{k})-\nabla f(x_{k})}$

${\displaystyle \gamma _{k}={\frac {1}{y_{k}^{T}s_{k}}}}$

とし、${\displaystyle B_{k}}$は対称正定値行列とした。

対応する逆ヘッセ行列${\displaystyle H_{k}=B_{k}^{-1}}$の近似値は、以下の式により与えられる。

${\displaystyle H_{k+1}=H_{k}-{\frac {H_{k}y_{k}y_{k}^{T}H_{k}}{y_{k}^{T}H_{k}y_{k}}}+{\frac {s_{k}s_{k}^{T}}{y_{k}^{T}s_{k}}}.}$

${\displaystyle B}$は正定値行列と仮定されるため、${\displaystyle s_{k}^{T}}$と${\displaystyle y}$は以下の曲率条件を満たす必要がある。

${\displaystyle s_{k}^{T}y_{k}=s_{k}^{T}Bs_{k}>0}$

DFP法は非常に効果的だったものの、すぐにその双対である（yとsの役割が入れ替わっている）BFGS法に置き換えられた^[1]。

関連項目[編集]

• ニュートン法
• 最適化におけるニュートン法（英語版）
• 準ニュートン法
• BFGS法
• LBFGS法
• SR1法（英語版）
• ネルダー・ミード法

出典[編集]

参考文献[編集]

• Davidon, W. C. (1959). “Variable Metric Method for Minimization”. AEC Research and Development Report ANL-5990. doi:10.2172/4252678. https://digital.library.unt.edu/ark:/67531/metadc1021816/. 
• Fletcher, Roger (1987). Practical methods of optimization (2nd ed.). New York: John Wiley & Sons. ISBN 978-0-471-91547-8. https://archive.org/details/practicalmethods0000flet 
• Kowalik, J.; Osborne, M. R. (1968). Methods for Unconstrained Optimization Problems. New York: Elsevier. pp. 45–48. ISBN 0-444-00041-0. https://archive.org/details/methodsforuncons0000kowa/page/45 
• Nocedal, Jorge; Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. ISBN 0-387-98793-2 
• Walsh, G. R. (1975). Methods of Optimization. London: John Wiley & Sons. pp. 110–120. ISBN 0-471-91922-5 

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）