Optimización de SciPy: Newton-CG vs BFGS vs L-BFGS

Estoy haciendo un problema de optimización con Scipy, donde tomo una red plana de vértices y enlaces de tamaño NNxNN , NNxNN dos lados de ella (es decir, la NNxNN periódica) y minimizo una función de energía, de modo que se enrosque hasta formarla. un cilindro (Vea los enlaces de abajo.)

Dado que tengo la función de energy(xyz-position) y su gradiente, decidí usar los tres métodos recomendados en el manual de Scipy: Newton-CG , BFGS , L-BFGS-B y comparar cómo se desempeñaron.

Llamo a la función de optimización de la siguiente manera, y simplemente sustituyo 'Newton-CG' por 'BFGS' y 'L-BFGS-B' según el caso:

 from scipy.optimize import minimize res = minimize(energy, xyzInit, method='Newton-CG', jac = energy_der, options={'disp': True}) 

Encontré el siguiente comportamiento general (estoy dando los datos de salida para el caso de NN=9 , correspondiente a un espacio de parámetros de 3*9^2=243 ) –

  1. BFGS sistemáticamente no pudo encontrar el mínimo correcto (para NN bajo), y no logró converger para NN grande. Consulte https://plot.ly/~apal90/162/ para obtener el resultado final.

      NN=9 Method: BFGS Warning: Desired error not necessarily achieved due to precision loss. Current function value: 204.465912 Iterations: 1239 Function evaluations: 1520 Gradient evaluations: 1508 Time taken for minimisation: 340.728140116 
  2. Newton-CG encontró el mínimo correcto para NN pequeño (<= 8), pero a partir de NN = 9, obtuvo un mínimo incorrecto (es decir, un cilindro aplastado en un extremo), y para valores más altos se detuvo, incluso convergiendo. Nota: este comportamiento se agravó por alguna razón en las NN impares. Ver https://plot.ly/~apal90/164/

      NN=9 Method: Newton-CG Optimization terminated successfully. Current function value: 7.954412 Iterations: 49 Function evaluations: 58 Gradient evaluations: 1654 Hessian evaluations: 0 Time taken for minimisation: 294.203114033 
  3. L-BFGS-B encontró el mínimo correcto, y eso es increíblemente rápido, para todos los NN que probé (hasta NN=14 ). Ver https://plot.ly/~apal90/160/

      NN=9 Method: L-BFGS-B Time taken for minimisation: 36.3749790192 

Pregunta : ¿Por qué L-BFGS-B superior en este caso a los otros dos métodos? En particular, ¿por qué es tan superior a BFGS , cuando se supone que ambos son métodos casi de Newton que funcionan (a mi entender), exactamente de la misma manera?

Mis pensamientos sobre la situación : Los tres métodos hacen aproximaciones cuadráticas en cada punto x. Para esto, se necesita un gradiente y una arpillera. Si el Hessian no se da, debe ser calculado por el algoritmo. En nuestro caso, donde solo se da explícitamente el gradiente, esto se calcula numéricamente en cada paso mediante el algoritmo. Más específicamente, lo que necesitamos es el inverso de la arpillera, y este es un paso muy costoso, especialmente en dimensiones más altas. Ahora, Newton-CG calcula este Hessian inverso explícitamente, por lo tanto, es un tiempo mayor. Los métodos cuasi-Newton como BFGS y L-BFGS calculan una aproximación a la arpillera (es decir, la curvatura) según el gradiente, que es más barato en el tiempo y que, supuestamente, también es una mejor estimación de la curvatura en un punto. Por lo tanto, para funciones cuadráticas, Newton-CG converge más rápido, mientras que para funciones no cuadráticas, las funciones cuasi-Newton convergen mejor. L-BFGS es una versión de memoria inferior de BFGS que almacena mucha menos memoria en cada paso que la matriz NxN completa, por lo que es más rápida que BFGS.

Esta explicación muestra una divergencia entre Newton-CG y los métodos cuasi-Newton. Lo que no explica es la incapacidad de los algoritmos para encontrar el verdadero mínimo, y especialmente la disparidad entre BFGS y L-BFGS, que se supone que ambos funcionan de la misma manera.

Mi corazonada general sobre los largos tiempos de convergencia es que el sistema no es cuadrático (es decir, plano) sobre el mínimo, y por lo tanto el algoritmo oscila con la convergencia. Más allá de eso, si BFGS y L-BFGS realmente funcionan de la misma manera, creo que debe haber alguna diferencia entre los niveles de tolerancia de convergencia de los algoritmos Scipy. De lo contrario, BFGS y L-BFGS realmente no funcionan de la misma manera, y este último probablemente calcula el Hessian con mucha más precisión.

Referencias –

http://www.scipy-lectures.org/advanced/mathematical_optimization/#newton-and-quasi-newton-methods

https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization

https://en.wikipedia.org/wiki/Quasi-Newton_method

https://docs.scipy.org/doc/scipy-0.18.1/reference/optimize.minimize-bfgs.html#optimize-minimize-bfgs

https://docs.scipy.org/doc/scipy-0.18.1/reference/optimize.minimize-lbfgsb.html#optimize-minimize-lbfgsb

A su pregunta le falta dos datos importantes: la función de energía y la conjetura inicial. La función de energía puede ser convexa / no convexa, suave / por partes, suave / discontinua. Por esta razón, hace que sea difícil responder completamente a su pregunta en su contexto. Sin embargo, puedo explicar algunas diferencias clave entre BFGS y L-BFGS-B.

Ambos métodos son métodos iterativos para resolver problemas de optimización no lineales. Ambos se aproximan al método de Newton utilizando una aproximación del Hessiano de la función en cada iteración. La diferencia clave con el método de Newton es que, en lugar de calcular la arpillera completa en un punto específico, acumulan los gradientes en los puntos anteriores y utilizan la fórmula BFGS para unirlos como una aproximación de la arpillera. No se garantiza que los métodos de Newton y BFGS converjan a menos que la función tenga una expansión cuadrática de Taylor cerca de un óptimo.

El método BFGS original acumula todos los gradientes desde la estimación inicial dada. Hay dos problemas con este método. Primero, la memoria puede boost indefinidamente. En segundo lugar, para problemas no lineales, el Hessiano en la conjetura inicial a menudo no es representativo del Hessiano en la solución. El Hessiano aproximado será sesgado hasta que se acumulen suficientes gradientes cerca de la solución. Esto puede ralentizar la convergencia, pero, en mi experiencia, aún debería converger con un buen algoritmo de búsqueda de líneas para las funciones de energía que tienen un mínimo local único.

L-BFGS es igual que BFGS pero con una memoria limitada, lo que significa que después de algún tiempo, los gradientes antiguos se descartan para dejar más espacio para los gradientes recién calculados. Esto resuelve el problema de la memoria y evita el sesgo del gradiente inicial. Sin embargo, dependiendo del número de gradientes guardados en la memoria, el Hessiano nunca se puede estimar con precisión, y puede ser otra fuente de sesgo. Esto también puede ralentizar la convergencia, pero de nuevo, aún debería converger con un buen algoritmo de búsqueda de líneas para las funciones de energía que tienen un mínimo local único.

L-BFGS-B es igual que L-BFGS pero con restricciones de límite en las variables de entrada. L-BFGS-B dejará de optimizar las variables que se encuentran en el límite del dominio. Como no especificó ninguna restricción, este aspecto del algoritmo no se aplica a su problema.

Mi hipótesis es que está tratando de resolver un problema suave pero no convexo utilizando una suposición inicial que está lejos de la solución y que termina en un mínimo local. Como mencionó que comienza desde una configuración plana, no me sorprendería que comience en una singularidad que conduzca a un Hessiano degenerado, que puede causar problemas para el rest de la optimización. La única diferencia entre BFGS y L-BFGS en su caso es que cada iteración computará un gradiente que sea ligeramente diferente, y que el método L-BFGS terminará siguiendo una ruta que conduce al mínimo global.