DFP法
Davidon–Fletcher–Powell法またはDFP法とは、あるセカント方程式を満たす解のうち、現在の推定値に最も近く、曲率条件を満たす解を与える式(DFP公式)を用いる準ニュートン法である。名称はWilliam C. Davidon、Roger Fletcher、Michael JD Powellに因む。セカント法を多次元問題に一般化したものであり、準ニュートン法としては初めての解法だった。この公式によりヘッセ行列を更新すれば、対称性と正定性が保証される。
所与の関数 のテイラー展開は、その勾配( )、正定値ヘッセ行列 、を用いて以下のように書ける。
また、勾配自体のテイラー展開(セカント方程式)は以下のように書ける。
これをの更新に用いる。
下に示すDFP公式は、対称かつ正定値であり、現在の近似値に最も近い解を与える。
ここで、
とし、は対称正定値行列とした。
対応する逆ヘッセ行列の近似値は、以下の式により与えられる。
は正定値行列と仮定されるため、とは以下の曲率条件を満たす必要がある。
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 .
- Fletcher, Roger (1987). Practical methods of optimization (2nd ed.). New York: John Wiley & Sons. ISBN 978-0-471-91547-8
- Kowalik, J.; Osborne, M. R. (1968). Methods for Unconstrained Optimization Problems. New York: Elsevier. pp. 45–48. ISBN 0-444-00041-0
- 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
非線形(無制約) |
| |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
非線形(制約付き) |
| |||||||||||||
凸最適化 |
| |||||||||||||
組合せ最適化 |
| |||||||||||||
メタヒューリスティクス | ||||||||||||||
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.