Motivación intuitiva para la actualización de BFGS

15

¡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 )JkJk1Fro2Jk(xkxk1)=f(xk)f(xk1)

¡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?

Justin Solomon
fuente
44
Si permites una actualización arbitraria, entonces puedes usar el Hessian completo en el método de Newton. Una gran ventaja computacional de una actualización de bajo rango es que le permite actualizar la factorización del Hessian aproximado muy rápidamente.
Brian Borchers

Respuestas:

12

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)minxRn.
Digamos que hay una solución aproximada xk . Luego, se aproxima el mínimo de f por el mínimo de la expansión de Taylor truncada
f(xk+p)f(xk)+f(xk)Tp+12pTH(xk)p.()
Es decir, uno busca p tal que () es mínimo y establece xk+1:=xk+p . Calcular el gradiente de () - "con respecto a p " - y ponerlo a cero da la relación
H(xk)[xk+1xk]=f(xk+1)f(xk),
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 Hk+11 minimiza

Hk1H1W
en una norma de Frobenius ponderada elegida de forma inteligente, sujeto a
  1. H[xk+1xk]=f(xk+1)f(xk) - esto es lo que uno está buscando - y
  2. HT=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 / 2F G : = 1 0 H ( x k + τ p ) d τ alpha k = 1WHW:=W1/2HW1/2F G:=01H(xk+τp)dτα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

ene
fuente
Muchas gracias, esto es genial (y más o menos lo que esperaba basado en la discusión en Nocedal & Wright). La única pregunta que tengo es: ¿por qué elegimos y la norma como lo hacemos? Entiendo que tiene que ver con unidades, pero hay muchas opciones potenciales de y normas que hacen esto. WWW
Justin Solomon
Si verdad. Bueno, no lo se. Una respuesta es que proporciona la fórmula de actualización simple de calcular y que funciona bien. Históricamente, este enfoque de la actualización, minimizando la diferencia en la actualización, fue el de Shanno. Fue un árbitro (Goldfarb) quien descubrió que una elección particular de los pesos lleva a la fórmula de Broyden y Fletcher. Ver esta tesis doctoral Desarrollo histórico del método secante BFGS ... para las intuiciones de los desarrolladores de BFGS. Sin embargo, los 3 enfoques son bastante abstractos.
Jan
1
Interesante, gracias por la orientación! Mi redacción actual (con algunos errores matemáticos que necesitan ayuda) está aquí: graphics.stanford.edu/courses/cs205a-13-fall/assets/notes/… (si desea crédito por su ayuda, me complace proporcionarla - por favor envíeme un correo electrónico con la información de contacto adecuada)
Justin Solomon
@jan ¿Por qué es tu ecuación y no ¿No es la condición secante dada por , donde . ¡Gracias!
H(xk)[xk+1xk]=f(xk+1)f(xk)
H(xk+1)[xk+1xk]=f(xk+1)f(xk)?
s k = x k + 1 - x k , y k = f k + 1 - f kHk+1sk=yksk=xk+1xk,yk=fk+1fk
Jeff Faraci