¿Optimizar una función desconocida que solo se puede evaluar?

Dada una función desconocida , podemos evaluar su valor en cualquier punto de su dominio, pero no tenemos su expresión. En otras palabras, es como una caja negra para nosotros. $f:\mathbb R^d \to \mathbb R$ $f$

¿Cuál es el nombre del problema de encontrar el minimizador de ? ¿Cuáles son algunos métodos por ahí? $f$

¿Cuál es el nombre del problema de encontrar la solución a la ecuación ? ¿Cuáles son algunos métodos por ahí? $f(x)=0$

En los dos problemas anteriores, ¿es una buena idea interpolar o ajustar algunas evaluaciones de f: usando una función con forma y parámetro conocidos por determinar, y luego minimizar o encontrar su raíz? $(x_i, f(x_i)), i=1, \dots, n$ $g_\theta$ $\theta$ $g_\theta$

¡Gracias y saludos!

optimization Tim
fuente

¿Puedes evaluar su gradiente en un punto dado?

chaohuang

@chaohuang: Hay dos casos: puede o no evaluar su gradiente, dependiendo de los supuestos.

Tim

Si el gradiente está disponible, las tareas que está solicitando se pueden realizar mediante algoritmos basados en gradiente. Por ejemplo, el mínimo, o al menos un mínimo local, puede calcularse mediante el método de descenso más pronunciado, y las raíces pueden encontrarse mediante el método de Newton.

chaohuang

Y si se desconoce el gradiente, existen métodos metaheurísticos , que también se denominan métodos sin derivado o de caja negra y generalmente en forma de optimización estocástica.

chaohuang

¿Sabes si la función es suave (incluso si no puedes evaluar el gradiente)? ¿Sabes si la función es convexa? Si no es convexo, ¿sabe si es o no al menos continuo Lipschitz? Si la función es completamente general, entonces este es un problema inútil.

Brian Borchers

Respuestas:

Los métodos que está buscando, es decir, que solo utilizan evaluaciones de funciones pero no derivados, se denominan métodos de optimización sin derivación . Existe una gran cantidad de literatura sobre ellos, y puede encontrar un capítulo sobre tales métodos en la mayoría de los libros sobre optimización. Los enfoques típicos incluyen

Aproximando el gradiente por diferencias finitas si se puede esperar razonablemente que la función sea suave y, posiblemente, convexa;
Métodos de Monte Carlo como el recocido simulado;
Algoritmos genéticos.

Wolfgang Bangerth
fuente

¿Puedo agregar "Modelado sustituto" a esa lista? Son muy aplicables para la optimización de caja negra, en particular si la función es costosa de evaluar.

OscarB

Sí, puedes :-) Sin duda, una gran adición.

Wolfgang Bangerth

También se podría usar el método Nelder-Mead si se conocen buenas estimaciones de los valores óptimos.

Sí, podría usar Nelder-Mead, pero es un algoritmo terrible en comparación con la mayoría de los demás.

Wolfgang Bangerth

@WolfgangBangerth: tu comentario sobre Nelder-Mead solo es válido en la dimensión d> 2. En dos dimensiones, en muchos problemas es un método excelente y muy difícil de superar.

Arnold Neumaier el

Creo que debería comenzar con: Taller de GECCO sobre Benchmarking de optimización de caja negra de parámetros reales (BBOB 2016) http://numbbo.github.io/workshops/index.html

Encontrará muchos algoritmos diferentes que se han utilizado en competiciones anteriores y que se han comparado de forma común. Si comienza en otro lugar, pronto se ahogará en los cientos de documentos que afirman que sus métodos y algoritmos funcionan mejor que otros con poca evidencia real de esas afirmaciones.

Hasta hace poco, era, para ser franco, una situación vergonzosa y todo el poder para INRIA, GECCO y muchos otros por el esfuerzo que han realizado para establecer un marco para las comparaciones racionales.

Lisístrata
fuente

-1

Solo agregaría que una de las claves aquí es poder escalar el método de optimización en CPU multinúcleo . Si puede realizar varias evaluaciones de funciones simultáneamente, le proporciona una aceleración igual a una cantidad de núcleos involucrados. Compare esto con solo usar un modelo de respuesta un poco más preciso, que lo hace un 10% más eficiente más o menos.

Recomiendo mirar este código , puede ser útil para las personas que tienen acceso a muchos núcleos. Una matemática detrás de esto se describe en este artículo .

Pablo
fuente

Esta respuesta es demasiado corta para ser útil (y seguir siendo útil, ya que los enlaces pueden desaparecer en cualquier momento). Además, mencione que usted es el autor de este software .

Christian Clason