Prueba de métodos de optimización numérica: Rosenbrock vs. funciones de prueba reales

15

Parece que hay dos tipos principales de función de prueba para optimizadores no derivados:

¿Es posible comparar digamos 10d Rosenbrock con algún problema real de 10d?
Se podría comparar de varias maneras: describir la estructura de los mínimos locales,
o ejecutar optimizadores ABC en Rosenbrock y algunos problemas reales;
pero ambos parecen difíciles.

(Tal vez los teóricos y los experimentadores son solo dos culturas bastante diferentes, ¿entonces estoy pidiendo una quimera?)

Ver también:


(Agregado en septiembre de 2014):
la siguiente gráfica compara 3 algoritmos DFO en 14 funciones de prueba en 8d desde 10 puntos de inicio aleatorios: BOBYQA PRAXIS SBPLX de NLOpt 14 funciones de prueba N-dimensionales, Python bajo gist.github de este Matlab por A Hedar 10 puntos de inicio aleatorios uniformes en el cuadro delimitador de cada función.
××
×

En Ackley, por ejemplo, la fila superior muestra que SBPLX es mejor y PRAXIS terrible; en Schwefel, el panel inferior derecho muestra que SBPLX encuentra un mínimo en el 5º punto de inicio aleatorio.

En general, BOBYQA es el mejor en 1, PRAXIS en 5 y SBPLX (~ Nelder-Mead con reinicios) en 7 de 13 funciones de prueba, con Powersum un cambio. YMMV! En particular, Johnson dice: "Le aconsejaría que no utilice valores de función (ftol) o tolerancias de parámetros (xtol) en la optimización global".

Conclusión: no ponga todo su dinero en un caballo o en una función de prueba.

ingrese la descripción de la imagen aquí

denis
fuente

Respuestas:

13

Se utilizan funciones simples como las de Rosenbrock para depurar y probar previamente los algoritmos recién escritos: son rápidos de implementar y ejecutar, y un método que no puede resolver bien los problemas estándar es poco probable que funcione bien en problemas de la vida real.

Para una comparación exhaustiva reciente de métodos sin derivados para funciones costosas, consulte Optimización sin derivados: una revisión de algoritmos y comparación de implementaciones de software . LM Rios, NV Sahinidis - doi 10.1007 / s10898-012-9951-y Journal of Global Optimization, 2012. (Consulte también la página web que lo acompaña: http://archimedes.cheme.cmu.edu/?q=dfocomp )

Arnold Neumaier
fuente
Prof. Neumaier, ¿podría señalar algunos problemas reales, evidencia, para "un método que no puede resolver bien los problemas estándar es poco probable que funcione bien en problemas de la vida real"? Me doy cuenta de que eso no es fácil. (Me interesarían sus comentarios sobre Hooker.) Además, un vistazo rápido a los modelos c de su enlace muestra que princetonlibgloballib requiere AMPL, y en source_convexmodels * .c faltan ";" after fscanf () - trivial but
denis
@Denis: problemas como Rosenbrock surgen de los primeros días de la optimización automatizada, donde las personas aislaron las dificultades típicas en ejemplos representativos simples que pueden estudiarse sin las complejidades numéricas de los problemas de la vida real. Por lo tanto, no son realmente artificiales, sino modelos simplificados de dificultades reales. Por ejemplo, Rosenbrock ilustra el efecto combinado de una fuerte no linealidad y un mal estado leve.
Arnold Neumaier
El sitio AMPL ampl.com ofrece una versión gratuita para estudiantes para AMPL.
Arnold Neumaier
7

La ventaja de los casos de prueba sintéticos como la función de Rosenbrock es que existe literatura existente para comparar, y existe un sentido en la comunidad sobre cómo se comportan los buenos métodos en tales casos de prueba. Si todos usaran su propio caso de prueba, sería mucho más difícil llegar a un consenso sobre qué métodos funcionan y cuáles no.

Wolfgang Bangerth
fuente
1

(Espero que no haya ninguna objeción a que agregue al final de esta discusión. Soy nuevo aquí, ¡así que avíseme si he transgredido!)

Las funciones de prueba para algoritmos evolutivos ahora son mucho más complicadas de lo que eran incluso hace 2 o 3 años, como pueden ver las suites utilizadas en competiciones en conferencias como el (muy reciente) Congreso de Computación Evolutiva de 2015. Ver:

http://www.cec2015.org/

Estas suites de prueba ahora incluyen funciones con varias interacciones no lineales entre variables. El número de variables puede ser tan grande como 1000, y supongo que podría aumentar en el futuro cercano.

Otra innovación muy reciente es una "Competencia de optimización de Black Box". Ver: http://bbcomp.ini.rub.de/

Un algoritmo puede consultar el valor f (x) para un punto x, pero no obtiene información de gradiente y, en particular, no puede hacer suposiciones sobre la forma analítica de la función objetivo.

En cierto sentido, esto podría estar más cerca de lo que usted llamó un "problema real", pero en un entorno organizado y objetivo.

Lisístrata
fuente
1) "sin objeciones": por el contrario, ¡sus buenos enlaces son bienvenidos! 2) ¿hay buenas parcelas allí? Los métodos y los problemas son fractales, por lo que cada vez es más difícil para cualquiera encontrar un problema como el suyo. En particular, ¿conocería los métodos para pronosticar series temporales ?
denis
Las funciones objetivas para la competencia CEC 2015 sobre optimización dinámica de múltiples objetivos se pueden ver en: sites.google.com/site/cec2015dmoocomp/competition-process/… Para otras competiciones, vaya a cec2015.org y haga clic en competiciones, luego haga clic en en competiciones aceptadas. Cada uno tiene sus propias funciones. Los documentos de algunos de ellos tienen gráficos encantadores (para los casos 2D). Los concursos de la conferencia GECCO se pueden encontrar en: sigevo.org/gecco-2015/competitions.html#bbc Los resultados estarán disponibles después del 15 de julio.
Lisistrata
0

Puedes tener lo mejor de los dos mundos. El NIST tiene una serie de problemas para los minimizadores, como ajustar este polinomio de décimo grado , con los resultados e incertidumbres esperados. Por supuesto, demostrar que estos valores son la mejor solución real, o la existencia y las propiedades de otros mínimos locales es más difícil que en una expresión matemática controlada.

Davidmh
fuente
Bueno, los problemas de NIST son pequeños (2 3 1 1 11 7 6 6 6 6 6 params). ¿Existen conjuntos de pruebas que sean "reales" y reproducibles , para cualquier rincón de "real"? Cf. una solicitud de problemas de optimización basados ​​en simulación
denis