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 de la ecuación secante más cercana a la estimación actual y satisface la condición de curvatura. Fue el primer método cuasi-Newton en generalizar el método secante a un problema multidimensional. Esta actualización mantiene la simetría y la definición positiva de la matriz de Hesse .

Dada una función ${\displaystyle f(x)}$, Su gradiente (${\displaystyle \nabla f}$), y matriz hessiana definida positiva ${\displaystyle B}$, la serie de 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 secante)

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

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

La fórmula de 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},}$

donde

${\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 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 positivo-definido, 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 eficaz, pero pronto fue reemplazada por la fórmula Broyden-Fletcher-Goldfarb-Shanno , que es su dual (intercambiando los roles de y y s ). ^[1]

Ver también

• Método de Newton
• El 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 simétrica de rango uno
• Método de Nelder-Mead

Referencias

1. Avriel, Mordecai (1976). Programación no lineal: análisis y métodos . Prentice Hall. págs. 352–353. ISBN 0-13-623603-0.

Lectura adicional

• Davidon, WC (1959). "Método de métrica variable para la minimización" . Informe de investigación y desarrollo de AEC ANL-5990 . doi : 10.2172 / 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.