Fórmula de Davidon-Fletcher-Powell

La fórmula de Davidon-Fletcher-Powell (o DFP ; nombrada en honor a William C. Davidon , Roger Fletcher y Michael JD Powell ) encuentra la solución a la ecuación de la secante que más se aproxima a la estimación actual y satisface la condición de curvatura. Fue el primer método cuasi-Newton que generalizó el método de la secante a un problema multidimensional. Esta actualización mantiene la simetría y la positividad definida de la matriz hessiana .

Dada una función suave${\displaystyle f(x)}$, su gradiente (${\displaystyle \nabla f}$), y matriz hessiana definida positiva${\displaystyle B}$, la serie Taylor es

${\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 ,}$

y la serie de Taylor del gradiente mismo (ecuación de la secante)

${\displaystyle \nabla f(x_{k}+s_{k})=\nabla f(x_{k})+Bs_{k}+\dots }$

se utiliza para actualizar${\displaystyle B}$.

La fórmula DFP encuentra una solución que es simétrica, definida positiva y más cercana al valor aproximado actual de${\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},}$

dónde

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

${\displaystyle \gamma _{k}={\frac {1}{y_{k}^{T}s_{k}}},}$

y${\displaystyle B_{k}}$es una matriz simétrica y definida positiva .

La actualización correspondiente a la aproximación de la matriz hessiana inversa${\displaystyle H_{k}=B_{k}^{-1}}$es dado por

${\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}$Se supone que es definida positiva, y los vectores${\displaystyle s_{k}^{T}}$y${\displaystyle y}$debe satisfacer la condición de curvatura

${\displaystyle s_{k}^{T}y_{k}=s_{k}^{T}Bs_{k}>0.}$

La fórmula DFP es bastante efectiva, pero pronto fue reemplazada por la fórmula de Broyden-Fletcher-Goldfarb-Shanno , que es su dual (intercambiando los roles de y y s ). ^{[ 1 ]}

Al desenrollar la recurrencia de la matriz para${\displaystyle B_{k}}$, la fórmula DFP se puede expresar como una representación matricial compacta . Específicamente, definiendo

$${\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}},}$$

y matrices triangulares superiores y diagonales

$${\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{ para }}1\leq i\leq j\leq k}$$

La matriz DFP tiene la fórmula equivalente.

$${\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}}}$$

La representación compacta inversa se puede encontrar aplicando la inversa de Sherman-Morrison-Woodbury a${\displaystyle B_{k}}$La representación compacta es particularmente útil para problemas con memoria limitada y restricciones. ^{[ 2 ]}

• El método de Newton
• Método de Newton en optimización
• Método cuasi-Newton
• Método de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
• Método BFGS de memoria limitada
• Fórmula de rango uno simétrica
• Método de Nelder-Mead
• Representación cuasi-Newton compacta

• Davidon, WC (1959). "Método de métrica variable para minimización" . Informe de investigación y desarrollo de la AEC ANL-5990 . doi : 10.2172/4252678 . hdl : 2027/mdp.39015078508226 . OSTI 4252678 . 
• Fletcher, Roger (1987). Métodos prácticos de optimización (2.ª  ed.). Nueva York: John Wiley & Sons. ISBN 978-0-471-91547-8.
• Kowalik, J.; Osborne, MR (1968). Métodos para problemas de optimización sin restricciones . Nueva York: Elsevier. págs. 45–48 . ISBN  0-444-00041-0.
• Nocedal, Jorge; Wright, Stephen J. (1999). Optimización numérica . Springer-Verlag. ISBN 0-387-98793-2.
• Walsh, GR (1975). Métodos de optimización . Londres: John Wiley & Sons. págs. 110–120 . ISBN  0-471-91922-5.