BFGS vs método de gradiente conjugado

25

¿Qué consideraciones debo hacer al elegir entre BFGS y el gradiente conjugado para la optimización? La función que estoy tratando de ajustar con estas variables son funciones exponenciales; sin embargo, la función objetivo real implica la integración, entre otras cosas, y es muy costosa si eso ayuda en absoluto.

drjrm3
fuente
3
Bueno, BFGS es ciertamente más costoso en términos de almacenamiento que CG. Uno requiere el mantenimiento de un Hessian aproximado, mientras que el otro solo necesita unos pocos vectores de usted. Por otro lado, ambos requieren el cálculo de un gradiente, pero me dicen que con BFGS, puede usar aproximaciones de diferencias finitas en lugar de tener que escribir una rutina para el gradiente (pero la versión que usa diferencias finitas converge un poco más lento que el que usa gradientes reales, por supuesto). Si tiene una instalación de diferenciación automática, entonces su única preocupación es el almacenamiento.
JM
tener que ajustar solo ~ 7 (definitivamente menos de 10) variables significa que la aproximación de arpillera es solo (como máximo) una matriz de 10x10 correcta? en cuyo caso, ¿es uno más rápido que el otro?
drjrm3
No creo que haya tanta diferencia en la velocidad; en todo caso, creo que la parte de su cálculo que probablemente tomará más tiempo son las cuadraturas que tiene que hacer para evaluar la función. Realmente deberías hacer algunos experimentos tú mismo, si el número de parámetros es tan pequeño como afirmas.
JM

Respuestas:

13

JM tiene razón sobre el almacenamiento. BFGS requiere un Hessian aproximado, pero puede inicializarlo con la matriz de identidad y luego simplemente calcular las actualizaciones de rango dos al Hessian aproximado a medida que avanza, siempre que tenga información de gradiente disponible, preferiblemente analíticamente en lugar de a través de diferencias finitas. BFGS es un método cuasi-Newton, y convergerá en menos pasos que CG, y tiene un poco menos de tendencia a "atascarse" y requiere pequeños ajustes algorítmicos para lograr un descenso significativo para cada iteración.

Por el contrario, CG requiere productos de vectores de matriz, que pueden ser útiles para usted si puede calcular derivadas direccionales (de nuevo, analíticamente o utilizando diferencias finitas). Un cálculo de diferencia finita de una derivada direccional será mucho más barato que un cálculo de diferencia finita de una arpillera, por lo que si elige construir su algoritmo utilizando diferencias finitas, calcule directamente la derivada direccional. Sin embargo, esta observación no se aplica realmente a BFGS, que calculará las Hesse aproximadas utilizando productos internos de información de gradiente.

nn

Compararía los dos algoritmos en un pequeño problema de prueba para su aplicación si sabe que el almacenamiento no será un problema. Sin conocer los detalles específicos de su problema, supongo que BFGS será más rápido, pero realmente debe probar los dos algoritmos para tener una mejor idea de cuál funcionará mejor.

Finalmente, una palabra acerca de la diferenciación automática: teniendo algo de experiencia con un servicio interno de diferenciación automática (AD) para Fortran ( DAEPACK ), puedo decirle que las herramientas de AD a menudo son delicadas. Es posible que no necesariamente puedan diferenciar el código que generan ellos mismos. Hay dos tipos de herramientas AD:

  • herramientas de fuente a fuente de AD
  • operador sobrecargando herramientas AD

Las herramientas de fuente a fuente son compiladores esencialmente modificados que toman el código fuente que ha escrito, lo analizan y generan automáticamente un nuevo código fuente que calcula el gradiente de funciones en su código fuente. Las herramientas de AD de sobrecarga de operadores requieren que use los operadores de AD sobrecargados en su código fuente para poder calcular los derivados, lo que requeriría un esfuerzo adicional de su parte para calcular derivados analíticos con AD.

Geoff Oxberry
fuente
22

mm

En mi experiencia, BFGS con muchas actualizaciones almacena información demasiado lejos de la solución actual para ser realmente útil para aproximarse al jacobiano no rezagado, y en realidad puede perder la convergencia si almacena demasiado. Hay variantes "sin memoria" de BFGS que se parecen mucho a los gradientes conjugados no lineales (vea la actualización final descrita para uno de estos) solo por estas razones. Por lo tanto, si está dispuesto a hacer L-BFGS en lugar de BFGS, los problemas de memoria desaparecen y los métodos están relacionados . La evidencia anecdótica apunta a que reiniciar es un tema complicado, ya que a veces es innecesario y a veces muy necesario.

Su elección entre los dos también depende en gran medida de los problemas que le interesen. Si tiene los recursos, puede intentar ambos problemas y decidir cuál funciona mejor. Por ejemplo, personalmente no hago optimización con estos algoritmos, sino que me importa la solución de sistemas de ecuaciones no lineales. Para estos, he descubierto que NCG funciona mejor y es más fácil realizar un preacondicionamiento no lineal. BFGS es más robusto.

m

Peter Brune
fuente
Me olvidé por completo de L-BFGS. +1 por eso.
JM
15

En dimensiones bajas, un método BFGS bien implementado es generalmente más rápido y más robusto que el CG, especialmente si la función no está muy lejos de ser cuadrática.

Ni BFGS ni CG necesitan ninguna suposición sobre convexidad; solo la aproximación inicial de Hesse (para BFGS) resp. El preacondicionador (para CG) debe ser positivo definido. Pero estos siempre se pueden elegir para ser la matriz de identidad, en bajas dimensiones sin mucho daño. Ver también /scicomp//a/3213/1117

En ausencia de un gradiente programado, es una gran pérdida de esfuerzo utilizar gradientes numéricos, especialmente cuando los valores de las funciones son caros. Más bien, uno debería usar un algoritmo sin derivadas. Ver http://archimedes.cheme.cmu.edu/?q=dfocomp para una encuesta reciente.

Arnold Neumaier
fuente
El enlace me da un "404 no encontrado", ¿podría arreglarlo?
Stiefel
@Stiefel: lo arreglé. El nuevo enlace apunta a una versión mucho mejor.
Arnold Neumaier