Algoritmos de optimización paralelos para un problema con una función objetivo muy costosa

15

Estoy optimizando una función de 10-20 variables. La mala noticia es que cada evaluación de la función es costosa, aproximadamente 30 minutos de cálculo en serie. La buena noticia es que tengo un clúster con unas pocas docenas de nodos computacionales a mi disposición.

Por lo tanto, la pregunta: ¿hay algoritmos de optimización disponibles que me permitan utilizar toda esa potencia de cálculo de manera eficiente?

En un lado del espectro habría una búsqueda exhaustiva: subdividir todo el espacio de búsqueda en una cuadrícula fina y calcular la función en cada punto de la cuadrícula de forma independiente. Este es ciertamente un cálculo muy paralelo, pero el algoritmo es terriblemente ineficiente.

En el otro lado del espectro estarían los algoritmos cuasi-Newton: actualizar de manera inteligente la próxima estimación de los parámetros en función de la historia previa. Este es un algoritmo eficiente, pero no sé cómo hacerlo paralelo: el concepto de "estimación de los parámetros basados ​​en el historial anterior" suena como un cálculo en serie.

Los algoritmos cuadráticos parecen estar en algún punto intermedio: se puede construir el "modelo sustituto" inicial calculando un conjunto de valores en paralelo, pero no sé si las iteraciones restantes son paralelizables.

¿Alguna sugerencia sobre qué tipo de métodos de optimización sin gradiente funcionarían bien en un clúster? Además, ¿hay implementaciones paralelas de algoritmos de optimización disponibles actualmente?

Miguel
fuente
1
Siempre puede calcular el gradiente en paralelo (para métodos cuasi-Newton utilizando diferencias finitas) y obtener una aceleración proporcional al número de parámetros, es decir, 10x-20x.
stali
@stali: Necesitas el Hessian para los métodos cuasi-Newton en la optimización. Calcular el Hessian a través de diferencias finitas de evaluaciones de funciones no es realmente una buena idea. Calcular las aproximaciones por diferencias finitas del gradiente para la optimización tampoco suele ser una buena idea.
Geoff Oxberry
Muchos métodos cuasi-Newton como BFGS no requieren el hessiano explícitamente. Creo que al usar gradientes, en combinación con L-BFGS, el OP puede lograr rápidamente lo que quiere.
stali
@stali: Señalé por qué usar una aproximación de diferencia finita al gradiente sería una mala idea en mi respuesta. Se degradará la convergencia al introducir el error en el lado derecho de la iteración cuasi-Newton. Además, desperdicia evaluaciones de funciones porque no hay oportunidad de reutilizar evaluaciones antiguas (a diferencia de los métodos sustitutos). El uso de BFGS solo aborda la mitad de los problemas con su enfoque propuesto.
Geoff Oxberry
Esto es más apropiadamente un comentario, no una respuesta. Pero no tengo otra opción, ya que no tengo suficiente representante para publicar un comentario. Michael, tengo un tipo de problema muy similar: costosas evaluaciones de funciones que implican simulaciones complejas que se ejecutan en un clúster. ¿Alguna vez encontró un código apropiado para ejecutar la optimización cuando la evaluación de la función involucra una simulación en un clúster?
MoonMan

Respuestas:

16

Como dice Paul, sin más información, es difícil dar consejos sin suposiciones.

Con 10-20 variables y costosas evaluaciones de funciones, la tendencia es recomendar algoritmos de optimización sin derivados. Voy a estar en total desacuerdo con el consejo de Paul: generalmente necesita un gradiente de precisión mecánica a menos que esté utilizando algún tipo de método especial (por ejemplo, el descenso de gradiente estocástico en el aprendizaje automático explotará la forma del objetivo para llegar a un nivel razonable estimaciones de gradiente).

Cada paso cuasi-Newton tendrá la forma:

H~(Xk)rek=-F(Xk),

donde es una aproximación de la matriz de Hesse, d k es la dirección de búsqueda, x k es el valor de las variables de decisión en la iteración actual, f es su función objetivo y f es el gradiente de su objetivo, y el las variables de decisión se actualizan como x k + 1 = x k + α k d k , donde α kH~rekXkFFXk+1=Xk+αkrekαkes un tamaño de paso determinado de alguna manera (como una búsqueda de línea). Puede salirse con la aproximación de la arpillera de ciertas maneras y sus iteraciones convergerán, aunque si usa algo como aproximaciones de diferencia finita de la arpillera a través de gradientes exactos, puede sufrir problemas debido al mal acondicionamiento. Típicamente, el Hessian se aproxima usando el gradiente (por ejemplo, métodos de tipo BFGS con actualizaciones de rango 1 al Hessian).

Aproximar el hessiano y el gradiente a través de diferencias finitas es una mala idea por varias razones:

  • tendrá un error en el gradiente, por lo que el método cuasi-Newton que está aplicando es similar a encontrar la raíz de una función ruidosa
  • Si las evaluaciones de funciones son costosas y está intentando evaluar un gradiente con respecto a variables, le costará N evaluaciones de funciones por iteraciónnortenorte
  • Si tiene un error en el gradiente, tendrá más errores en su Hesse, lo cual es un gran problema en términos del condicionamiento del sistema lineal.
  • ... y le costará evaluaciones de la función por iteraciónnorte2

Entonces, para obtener una mala iteración de cuasi-Newton, estás haciendo algo así como hasta 420 evaluaciones de funciones en 30 minutos por evaluación, lo que significa que estarás esperando un tiempo para cada iteración, o vas a necesita un gran clúster solo para las evaluaciones de funciones. Las soluciones lineales reales serán de 20 por 20 matrices (¡a lo sumo!), Por lo que no hay razón para paralelizarlas. Si puede obtener información de gradiente, por ejemplo, resolviendo un problema adjunto, entonces podría valer más la pena, en cuyo caso, podría valer la pena mirar un libro como Nocedal & Wright.

Si va a hacer muchas evaluaciones de funciones en paralelo, debería considerar los enfoques de modelado sustituto o generar métodos de búsqueda establecidos antes de considerar los enfoques cuasi-Newton. Los artículos de revisión clásicos son los de Rios y Sahinidis sobre métodos sin derivados , que se publicó en 2012 y ofrece una comparación amplia y realmente buena; el artículo de evaluación comparativa de More and Wild de 2009; el libro de texto de 2009 "Introducción a la optimización sin derivados" de Conn, Scheinberg y Vicente; y el artículo de revisión sobre métodos de búsqueda de grupos electrógenos de Kolda, Lewis y Torczon de 2003.

Como se vincula anteriormente, el paquete de software DAKOTA implementará algunos de esos métodos, y también NLOPT , que implementa DIRECT, y algunos de los métodos de modelado sustitutos de Powell. También puede echar un vistazo a MCS ; está escrito en MATLAB, pero tal vez pueda portar la implementación de MATLAB al idioma que elija. DAKOTA es esencialmente una colección de scripts que puede usar para ejecutar su costosa simulación y recopilar datos para algoritmos de optimización, y NLOPT tiene interfaces en una gran cantidad de idiomas, por lo que la elección del lenguaje de programación no debería ser un gran problema al usar cualquiera de los paquetes de software; Sin embargo, DAKOTA lleva un tiempo aprender y tiene una gran cantidad de documentación para examinar.

Geoff Oxberry
fuente
2
Es un placer para mí estar completamente equivocado y aprender algo nuevo y útil en el proceso :).
Paul
¡Gracias! Solo una aclaración más: ¿cuál de esos algoritmos es capaz de realizar evaluaciones de funciones en paralelo? Por ejemplo, en la cuadrícula de k-way que realiza iteraciones n + 1, ..., n + k basándose solo en la información obtenida de las iteraciones 1, ..., n?
Michael
k
3

Quizás los algoritmos de optimización basados ​​en sustitutos son lo que está buscando. Estos algoritmos utilizan modelos sustitutos para reemplazar los modelos reales computacionalmente caros durante el proceso de optimización e intentan obtener una solución adecuada utilizando tan pocas evaluaciones de los modelos computacionalmente costosos como sea posible.

Creo que el método de Muestreo de persecución en modo puede usarse para resolver su problema. Este algoritmo utiliza el modelo sustituto de RBF para aproximar la costosa función objetivo y puede manejar restricciones no lineales. Más importante aún, selecciona múltiples candidatos para realizar las costosas evaluaciones de funciones para que pueda distribuir estos candidatos para la computación paralela para acelerar aún más el proceso de búsqueda. El código es de código abierto y está escrito en MATLAB.

Referencia

Wang, L., Shan, S. y Wang, GG (2004). Método de muestreo de búsqueda de modo para la optimización global en costosas funciones de caja negra. Optimización de ingeniería, 36 (4), 419-438.

Zhan Dawei
fuente
2

No estoy seguro de que un algoritmo paralelo sea realmente lo que estás buscando. Sus evaluaciones de funciones son muy costosas. Lo que desea hacer es paralelizar la función en sí, no necesariamente el algoritmo de optimización.

Si no puede hacer eso, entonces hay un punto medio entre la búsqueda exhaustiva y el algoritmo de Newton, son los métodos de Monte Carlo. Puede, en un montón de núcleos / nodos diferentes, iniciar el mismo algoritmo que es propenso a caer en óptimos locales (digamos algoritmos cuasi-Newton), pero todos con condiciones iniciales aleatorias. Su mejor conjetura para el verdadero óptimo es el mínimo de los mínimos. Esto es trivial para paralelizar y puede usarse para extender cualquier método. Si bien no es perfectamente eficiente, si tiene suficiente potencia informática a su disposición, definitivamente puede ganar la batalla de la productividad de la programación frente al rendimiento del algoritmo (si tiene mucha potencia informática, esto puede terminar antes de que haya terminado de hacer un algoritmo más sofisticado).

Chris Rackauckas
fuente
0

La elección del algoritmo de optimización (y, por lo tanto, su paralelización) depende en gran medida de las propiedades de la función objetivo y las restricciones. Sin saber más sobre el problema, es difícil dar algún tipo de consejo significativo.

Pero a partir de sus consideraciones sobre los métodos newton, infiero que su función objetivo es diferenciable. Si es posible, su problema se beneficiaría enormemente de la paralelización de la evaluación de la función. Si no es posible, entonces también puede considerar un método inexacto de newton que reemplaza los gradientes / arpillera exactos por aproximaciones de diferencias finitas. Luego, puede utilizar todos los procesadores a su disposición para calcular cada elemento distinto de cero del jacobiano, como sugiere @stali.

Para obtener más información, lea la Optimización numérica de Nocedal & Wright, Capítulo 7 . Hay muchos paquetes de software de optimización que implementan esto en paralelo. Entre los programas gratuitos más utilizados se encuentra el paquete de software DAKOTA (Sandia National Labs) .

Paul
fuente
55
norte
-2

Aquí hay una solución a su problema.

La descripción de un método matemático se proporciona en este documento .

Pablo
fuente
3
Bienvenido a SciComp.SE. ¿Puede proporcionar detalles sobre el enfoque descrito en el documento e implementado en el software? ¿Cuál es el método usado? ¿Por qué es bueno? ¿Qué se proporciona en este enfoque que las otras respuestas no cubren?
nicoguaro
2
Además, parece que este es tu propio trabajo. Si eso es cierto, indíquelo explícitamente en su respuesta.
nicoguaro
@nicoguaro: gracias, pero sé cómo hacer clic en los enlaces.
Michael
2
@Michael, no es para ti. La filosofía de este sitio es ser una colección de respuestas. Estás obteniendo tu respuesta hoy, pero en el futuro alguien más puede necesitar la misma ayuda. Es por eso que hay estándares de facto de lo que es una buena respuesta.
nicoguaro