DFP法

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]。