DFP法

Davidon–Fletcher–Powell法（ダビドン＝フレッチャー＝パウエル法）、略称DFP法は、最適化問題における準ニュートン法の一種です。この方法は、あるセカント方程式を満たす解の中で、現在の推定値に最も近く、かつ曲率条件を満たす解を与える更新式（DFP公式）を用いることで、関数の最小値や最大値を効率的に探索します。

DFP法の名前は、この手法を開発したウィリアム・ダビドン、ロジャー・フレッチャー、マイケル・パウエルの3人の研究者に由来します。DFP法は、セカント法を多次元問題に拡張したものであり、準ニュートン法としては初期に開発された手法の一つです。この公式を用いることで、ヘッセ行列の近似値を更新する際に、その対称性と正定性を保証することが可能となります。

DFP法の理論的背景

対象とする関数 f(x) のテイラー展開は、その勾配 ∇f と、正定値ヘッセ行列 B を用いて、以下のように近似できます。

math
f(x_k + s_k) = f(x_k) +
abla f(x_k)^T s_k + \frac{1}{2} s_k^T B s_k + ...


ここで、x_k は現在の推定値、s_k は探索方向を表します。

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

math

abla f(x_k + s_k) =
abla f(x_k) + B s_k + ...


DFP法では、この関係式を用いてヘッセ行列の近似値 B を更新していきます。DFP公式は、現在の近似値 B_k に対して、対称性と正定性を保ちつつ、最も近い解を与えるように設計されています。

DFP公式

DFP法の更新式は、以下のようになります。

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
y_k =
abla f(x_k + s_k) -
abla f(x_k)


math
\gamma_k = \frac{1}{y_k^T s_k}


であり、I は単位行列です。また、B_k は対称正定値行列です。

対応する逆ヘッセ行列 H_k = B_k^{-1} の近似値は、以下の式で与えられます。

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}

曲率条件

ヘッセ行列 B は正定値行列と仮定されているため、s_k と y_k は以下の曲率条件を満たす必要があります。

math
s_k^T y_k = s_k^T B s_k > 0


この条件は、探索方向 s_k が、関数の減少方向に向かっていることを保証します。

DFP法の限界とBFGS法

DFP法は非常に効果的な手法でしたが、後にその双対（yとsの役割が入れ替わった）であるBFGS法（Broyden–Fletcher–Goldfarb–Shanno法）に取って代わられました。BFGS法は、DFP法よりも数値的安定性が高く、より実用的な手法として広く利用されています。

関連事項

ニュートン法
最適化におけるニュートン法
準ニュートン法
BFGS法
LBFGS法
SR1法
ネルダー・ミード法

参考文献

Davidon, W. C. (1959). “Variable Metric Method for Minimization”. AEC Research and Development Report ANL-5990.
Fletcher, Roger (1987). Practical methods of optimization (2nd ed.). New York: John Wiley & Sons.
Kowalik, J.; Osborne, M. R. (1968). Methods for Unconstrained Optimization Problems. New York: Elsevier.
Nocedal, Jorge; Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag.
Walsh, G. R. (1975). Methods of Optimization. London: John Wiley & Sons.

もう一度検索