¿Qué algoritmo de optimización utilizar para los problemas con muchos óptimos locales y la costosa función de objetivo?

Question

Tengo un problema de optimización con estas propiedades:

• La función objetivo no es barata de calcular. Puede ser evaluada hasta alrededor de 10^4 veces en la optimización.
• Hay un montón de óptimos locales.
• Los valores altos se agrupan en torno al máximo, por lo que el problema es algo convexo.
• Las soluciones se limitan a una hipercaja conocida.
• El gradiente es desconocido, pero intuitivamente, la función es suave.
• Es una función de hasta 50 variables. Los gráficos de abajo son ejemplos del caso especial 2D.

Nelder-Mead se atasca mucho en el optimo local. Por encima de tres variables, no hay posibilidad de usar la fuerza bruta. He mirado en los algoritmos genéticos, pero parecen requerir muchas evaluaciones de la función objetivo.

¿Qué tipo de algoritmo debería buscar?

Answer 1

En el caso de funciones costosas sin derivados, un marco abstracto útil para la optimización es

Compute the function in few points (it may be a regular grid or even not)
Repeat
    Interpolate data/fit into a stochastic model
    Validate the model through statistical tests
    Find the model’s maximum.
    If it is better that the best one you previously have got, update the maximum
    Put this point in the dataset

Eso también debería encajar bien con la pseudo convexidad que ha mencionado.

Referencias aquí:

Optimización global eficiente de las costosas funciones de la caja negra

Un marco riguroso para la optimización de funciones costosas por parte de los sustitutos