デイビッドソン・フレッチャー・パウエル公式

Davidon –Fletcher–Powell 公式(またはDFP ; William C. Davidon、Roger Fletcher、Michael JD Powellにちなんで命名) は、現在の推定値に最も近く、曲率条件を満たす割線方程式の解を求めます。これは、割線法を多次元問題に一般化した最初の準ニュートン法でした。この更新では、ヘッセ行列の対称性と正定値が維持されます。

滑らかな関数が与えられた場合${\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 式は非常に効果的ですが、すぐにその双対であるBroyden–Fletcher–Goldfarb–Shanno 式（ yとsの役割を入れ替えたもの）に取って代わられました。^{[ 1 ]}

行列の漸化式をほどくことで${\displaystyle B_{k}}$DFP式はコンパクトな行列表現で表すことができる。具体的には、

$${\displaystyle S_{k}={\begin{bmatrix}s_{0}&s_{1}&\ldots &s_{k-1}\end{bmatrix}},}$$$${\displaystyle Y_{k}={\begin{bmatrix}y_{0}&y_{1}&\ldots &y_{k-1}\end{bmatrix}},}$$

上三角行列および対角行列

$${\displaystyle {\big (}R_{k}{\big )}_{ij}:={\big (}R_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad {\big (}R_{k}^{\text{YS}}{\big )}_{ij}=y_{i-1}^{T}s_{j-1},\quad (D_{k})_{ii}:={\big (}D_{k}^{\text{SY}}{\big )}_{ii}=s_{i-1}^{T}y_{i-1}\quad \quad {\text{ for }}1\leq i\leq j\leq k}$$

DFP行列は等価な式を持つ

$${\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},}$$

$${\displaystyle J_{k}={\begin{bmatrix}Y_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}}}$$

$${\displaystyle N_{k}={\begin{bmatrix}0_{k\times k}&R_{k}^{\text{YS}}\\{\big (}R_{k}^{\text{YS}}{\big )}^{T}&R_{k}+R_{k}^{T}-(D_{k}+S_{k}^{T}B_{0}S_{k})\end{bmatrix}}}$$

逆コンパクト表現は、シャーマン・モリソン・ウッドベリー逆行列を適用することで見つけることができます。${\displaystyle B_{k}}$コンパクトな表現は、メモリが限られている問題や制約のある問題に特に役立ちます。^{[ 2 ]}

• ニュートン法
• 最適化におけるニュートン法
• 準ニュートン法
• ブロイデン・フレッチャー・ゴールドファーブ・シャノ（BFGS）法
• 限定メモリBFGS法
• 対称ランク1公式
• ネルダー・ミード法
• コンパクトな準ニュートン表現

• Davidon, WC (1959). "最小化のための可変メトリック法" . AEC 研究開発レポート ANL-5990 . doi : 10.2172/4252678 . hdl : 2027/mdp.39015078508226 . OSTI 4252678 . 
• フレッチャー、ロジャー（1987）。最適化の実践的方法（第2 版）。ニューヨーク：ジョン・ワイリー・アンド・サンズ。ISBN 978-0-471-91547-8。
• Kowalik, J.; Osborne, MR (1968).制約なし最適化問題のための方法. ニューヨーク: Elsevier. pp. 45–48 . ISBN  0-444-00041-0。
• ノセダル、ホルヘ；ライト、スティーブン J. (1999).数値最適化. Springer-Verlag. ISBN 0-387-98793-2。
• Walsh, GR (1975).最適化の方法. ロンドン: John Wiley & Sons. pp. 110–120 . ISBN  0-471-91922-5。