Motivación intuitiva para la actualización de BFGS

¡Estoy enseñando una clase de encuesta de análisis numérico y estoy buscando motivación para el método BFGS para estudiantes con experiencia / intuición limitada en optimización!

J k ( → x k - → x k - 1 ) = f ( → x k ) - f ( → x k - 1$\|J_k-J_{k-1}\|^2_{\textrm{Fro}}$$J_k(\vec x_k-\vec x_{k-1})=f(\vec x_k)-f(\vec x_{k-1})$

¡Las derivaciones de las actualizaciones de BFGS parecen mucho más complicadas y turbias! En particular, me gustaría no asumir a priori que la actualización debe ser de rango 2 o tomar una forma particular. ¿Existe una breve motivación de aspecto variado para la actualización de BFGS Hessian como la de Broyden?

La derivación del BFGS es más intuitiva cuando se consideran (estrictamente) los costos convexos funcionales:

Sin embargo, es necesaria cierta información de fondo : supongamos que se quiere minimizar una función convexa

$$f(x) \to \min_{x\in \mathbb R^n}.$$ Digamos que hay una solución aproximada $x_k$ . Luego, se aproxima el mínimo de $f$ por el mínimo de la expansión de Taylor truncada $$f(x_k+p) \approx f(x_k) +\nabla f(x_k)^Tp + \frac{1}{2}p^T H(x_k)p. \quad(*)$$ Es decir, uno busca $p$ tal que $(*)$ es mínimo y establece $x_{k+1} := x_k + p$ . Calcular el gradiente de $(*)$ - "con respecto a $p$ " - y ponerlo a cero da la relación $$H(x_k)[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k),$$ donde $H$ es el 'jacobiano del gradiente' o la matriz de Hesse.

Dado que el cálculo y la inversión del hessiano son caros ...

---

... una respuesta corta

(véase la actualización de Broyden) podría ser que la actualización BFGS $H_{k+1}^{-1}$ minimiza

$$\|H_k^{-1} - H^{-1}\|_W$$ en una norma de Frobenius ponderada elegida de forma inteligente, sujeto a

1. $H[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)$ - esto es lo que uno está buscando - y
2. $H^T = H$ , porque el hessiano es simétrico.

---

Luego, la elección del peso en como la inversa de la arpillera promedio , cf. aquí para la declaración pero sin pruebas, da la fórmula de actualización BFGS (con ).‖ H ‖ W : = ‖ W 1 / 2 H W 1 / 2 ‖ F G : = ∫ 1 0 H ( x k + τ p ) d τ alpha k = $W$$\|H\|_W := \|W^{1/2}HW^{1/2}\|_F$ $G:=\int_0^1 H(x_k + \tau p) d\tau$$\alpha_k = 1$

Los puntos principales son:

• Uno intenta aproximar la solución para los costos reales mediante la solución para una aproximación cuadrática
• El cálculo de la arpillera, y su inverso, es costoso. Uno prefiere actualizaciones simples.
• La actualización se elige óptima para el inverso en lugar del real de Hesse.
• El hecho de que sea una actualización de rango 2 es una consecuencia de la elección particular de los pesos en la norma Frobenius.

Una respuesta más larga debe incluir cómo elegir los pesos, cómo hacer que esto funcione para problemas no convexos (donde aparece una condición de curvatura que requiere una escala de la dirección de búsqueda ), y cómo derivar la fórmula real para la actualización. Una referencia está aquí (en alemán).$p$