DFP法

テンプレート:翻訳直後 Davidon–Fletcher–Powell法（ダビドン＝フレッチャー＝パウエル法）またはDFP法とは、あるセカント方程式を満たす解のうち、現在の推定値に最も近く、曲率条件を満たす解を与える式（DFP公式）を用いる準ニュートン法である。名称はテンプレート:仮リンク、ロジャー・フレッチャー、テンプレート:仮リンクに因む。セカント法を多次元問題に一般化したものであり、準ニュートン法としては初めての解法だった。この公式によりヘッセ行列を更新すれば、対称性と正定性が保証される。

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

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,

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

\nabla f (x_{k} + s_{k}) = \nabla f (x_{k}) + B s_{k} + \dots

これを $B$ の更新に用いる。

下に示すDFP公式は、対称かつ正定値であり、現在の近似値 $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},

ここで、

y_{k} = \nabla f (x_{k} + s_{k}) - \nabla f (x_{k})

γ_{k} = \frac{1}{y_{k}^{T} s_{k}}

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

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

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$ は正定値行列と仮定されるため、 $s_{k}^{T}$ と $y$ は以下の曲率条件を満たす必要がある。

s_{k}^{T} y_{k} = s_{k}^{T} B s_{k} > 0

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

脚注