Fórmula de Davidon-Fletcher-Powell

La fórmula de Davidon-Fletcher-Powell (o DFP ; llamada así por William C. Davidon , Roger Fletcher y Michael JD Powell ) encuentra la solución a la ecuación secante que es 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 hessiana .

Dada una función , su gradiente ( ) y una matriz hessiana definida positiva , la serie de Taylor es ${\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 ,}$

y la serie de Taylor del propio gradiente (ecuación 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 es una matriz simétrica y definida positiva . ${\displaystyle B_{k}}$

La actualización correspondiente a la aproximación hessiana inversa viene dada por ${\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}$se supone que es definida positiva y los vectores y deben satisfacer la condición de curvatura ${\displaystyle s_{k}^{T}}$ ${\displaystyle y}$

${\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 Broyden–Fletcher–Goldfarb–Shanno , que es su dual (intercambia los roles de y y s ). ^[1]

Representación compacta

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

$${\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 y diagonales superiores

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

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 . La representación compacta es particularmente útil para problemas con restricciones y memoria limitada. ^[2] ${\displaystyle B_{k}}$

Véase también

• El método de Newton
• El método de Newton en optimización
• Método de 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 Nelder-Mead
• Representación compacta cuasi-Newton

Referencias

1. Avriel, Mordecai (1976). Programación no lineal: análisis y métodos . Prentice-Hall. pp. 352–353. ISBN 0-13-623603-0.
2. Brust, JJ (2024). "Representaciones compactas útiles para el ajuste de datos". arXiv : 2403.12206 [math.OC].

Lectura adicional

• Davidon, WC (1959). "Método métrico variable para minimización". Informe de investigación y desarrollo de la AEC ANL-5990 . doi :10.2172/4252678. hdl : 2027/mdp.39015078508226 .
• 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. pp. 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. pp. 110–120. ISBN 0-471-91922-5.