DFP法
出典: フリー百科事典『ウィキペディア(Wikipedia)』
この項目「DFP法」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。(原文:Davidon–Fletcher–Powell formula)
修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。(2022年9月)
修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。(2022年9月)
Davidon–Fletcher–Powell法(ダビドン=フレッチャー=パウエル法)またはDFP法とは、あるセカント方程式を満たす解のうち、現在の推定値に最も近く、曲率条件を満たす解を与える式(DFP公式)を用いる準ニュートン法である。名称はウィリアム・ダビドン (英語版)、ロジャー・フレッチャー、マイケル・パウエル (英語版)に因む。セカント法を多次元問題に一般化したものであり、準ニュートン法としては初めての解法だった。この公式によりヘッセ行列を更新すれば、対称性と正定性が保証される。
所与の関数{\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] 。
脚注
[編集 ][脚注の使い方]
- ^ 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
