DFP法のソースを表示

{{翻訳直後|[[:en:Special:Redirect/revision/994242340|Davidon–Fletcher–Powell formula]]|date=2022年9月}}
'''Davidon–Fletcher–Powell法'''（ダビドン＝フレッチャー＝パウエル法）または'''DFP法'''とは、あるセカント方程式を満たす解のうち、現在の推定値に最も近く、曲率条件を満たす解を与える式（'''DFP公式'''）を用いる[[準ニュートン法]]である。名称は{{仮リンク|ウィリアム・ダビドン|en|William C. Davidon}}、[[ロジャー・フレッチャー (数学者)|ロジャー・フレッチャー]]、{{仮リンク|マイケル・J・D・パウエル|en|Michael J. D. Powell|label=マイケル・パウエル}}に因む。[[割線法|セカント法]]を多次元問題に一般化したものであり、準ニュートン法としては初めての解法だった。この公式により[[ヘッセ行列]]を更新すれば、[[対称行列|対称性]]と[[行列の定値性|正定性]]が保証される。

所与の関数<math>f(x)</math> の[[テイラー展開]]は、その[[勾配 (ベクトル解析)|勾配]]( <math>\nabla f</math> )、[[行列の定値性|正定値]][[ヘッセ行列]]<math>B</math> 、を用いて以下のように書ける。

: <math>f(x_k+s_k) = f(x_k) + \nabla f(x_k)^T s_k + \frac{1}{2} s^T_k {B} s_k + \dots,</math>

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

: <math>\nabla f(x_k+s_k) = \nabla f(x_k) + B s_k + \dots</math>

これを<math>B</math>の更新に用いる。

下に示すDFP公式は、対称かつ正定値であり、現在の近似値<math>B_k</math>に最も近い解を与える。

: <math>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,</math>

ここで、

: <math>y_k = \nabla f(x_k+s_k) - \nabla f(x_k)</math>
: <math>\gamma_k = \frac{1}{y_k^T s_k}</math>

とし、<math>B_k</math>は対称[[行列の定値性|正定値行列]]とした。

対応する逆ヘッセ行列<math>H_k = B_k^{-1}</math>の近似値は、以下の式により与えられる。

: <math>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}.</math>

<math>B</math>は正定値行列と仮定されるため、<math>s_k^T</math>と<math>y</math>は以下の曲率条件を満たす必要がある。

: <math>s_k^T y_k = s_k^T B s_k > 0</math>

DFP法は非常に効果的だったものの、すぐにその[[双対]]である（{{Mvar|y}}と''{{Mvar|s}}の''役割が入れ替わっている）[[BFGS法]]に置き換えられた<ref>{{Cite book|first=Mordecai|last=Avriel|title=Nonlinear Programming: Analysis and Methods|publisher=Prentice-Hall|year=1976|isbn=0-13-623603-0|pages=352–353}}</ref>。

== 脚注 ==
{{脚注ヘルプ}}
<references responsive="1"></references>

== 参考文献 ==
* {{Cite journal|last=Davidon|first=W. C.|date=1959|title=Variable Metric Method for Minimization|url=https://digital.library.unt.edu/ark:/67531/metadc1021816/|journal=AEC Research and Development Report ANL-5990|DOI=10.2172/4252678}}
* {{Cite book|last=Fletcher|first=Roger|title=Practical methods of optimization|publisher=John Wiley & Sons|location=New York|edition=2nd|isbn=978-0-471-91547-8|year=1987|url=https://archive.org/details/practicalmethods0000flet}}
* {{Cite book|last=Kowalik|first=J.|last2=Osborne|first2=M. R.|title=Methods for Unconstrained Optimization Problems|location=New York|publisher=Elsevier|year=1968|isbn=0-444-00041-0|pages=[https://archive.org/details/methodsforuncons0000kowa/page/45 45–48]|url=https://archive.org/details/methodsforuncons0000kowa/page/45}}
* {{Cite book|last=Nocedal|first=Jorge|last2=Wright|first2=Stephen J.|year=1999|title=Numerical Optimization|publisher=Springer-Verlag|isbn=0-387-98793-2}}
* {{Cite book|last=Walsh|first=G. R.|title=Methods of Optimization|location=London|publisher=John Wiley & Sons|year=1975|isbn=0-471-91922-5|pages=110–120}}

== 関連項目 ==
* [[ニュートン法]]
* [[最適化におけるニュートン法]]
* [[準ニュートン法]]
* [[BFGS法]]
* [[L-BFGS法]]
* [[SR1法]]
* [[ネルダー–ミード法|ネルダー・ミード法]]

{{最適化アルゴリズム}}

{{DEFAULTSORT:DFPほう}}
[[Category:最適化アルゴリズムとメソッド]]