DFP法

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

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

f ( x k + s k ) = f ( x k ) + ∇ f ( x k ) T s k + 1 2 s k T B s k + … , {\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 ,}

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

∇ f ( x k + s k ) = ∇ f ( x k ) + B s k + … {\displaystyle \nabla f(x_{k}+s_{k})=\nabla f(x_{k})+Bs_{k}+\dots }

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

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

B k + 1 = ( I − γ k y k s k T ) B k ( I − γ k s k y k T ) + γ k y k y k T , {\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},}

ここで、

y k = ∇ f ( x k + s k ) − ∇ f ( x k ) {\displaystyle y_{k}=\nabla f(x_{k}+s_{k})-\nabla f(x_{k})}
γ k = 1 y k T s k {\displaystyle \gamma _{k}={\frac {1}{y_{k}^{T}s_{k}}}}

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

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

H k + 1 = H k − H k y k y k T H k y k T H k y k + s k s k T y k T s k . {\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}}}.}

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

s k T y k = s k T B s k > 0 {\displaystyle s_{k}^{T}y_{k}=s_{k}^{T}Bs_{k}>0}

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

関連項目

出典

  1. ^ Avriel, Mordecai (1976). Nonlinear Programming: Analysis and Methods. Prentice-Hall. pp. 352–353. ISBN 0-13-623603-0 

参考文献

  • 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 
  • 表
  • 話
  • 編
  • 歴
非線形(無制約)
… 関数　
勾配法
収束性
準ニュートン法
その他の求解法
… ヘッセ行列
  • 最適化におけるニュートン法（英語版）
The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.
Optimization computes maxima and minima.
非線形(制約付き)
一般
微分可能
凸最適化
凸縮小化
  • 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版）
  • 簡約勾配法
  • 劣勾配法（英語版）
線型 および
二次
内点法
ベイズ-交換
  • 単体法
  • 改訂シンプレックス法（英語版）
  • 十字法（英語版）
  • レムケの主ピボット操作法（英語版）
組合せ最適化
系列範例
(Paradigms)
グラフ理論
最小全域木
最大フロー問題
メタヒューリスティクス
  • カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）