Estoy buscando ejecutar una optimización de descenso de gradiente para minimizar el costo de una instanciación de variables. Mi programa es muy costoso desde el punto de vista computacional, entonces estoy buscando una biblioteca popular con una implementación rápida de GD. ¿Cuál es la biblioteca/referencia recomendada?Implementación rápida de gradiente y descenso en una biblioteca C++?
GSL es una gran biblioteca (y gratuita) que ya implementa funciones comunes de interés matemático y científico.
Puede leer todo el reference manual online. Parece que this empieza a parecer interesante, pero creo que deberíamos saber más sobre el problema.
Esos algoritmos alternativos enumerados en la referencia de GSL son métodos de gradiente conjugado/biconjunto y deberían proporcionar un mejor rendimiento que el descenso de gradiente, siempre que sus datos se "comporten bien". –
Y si calcula numéricamente sus derivados a partir de los valores de las funciones, probablemente prefiera esto: http://www.gnu.org/software/gsl/manual/html_node/Multimin-Algorithms-without-Derivatives.html –
Esto parece una muy buena respuesta, pero me está costando trabajo hacerlo con VS2010 (exigente, lo sé ...) – Jim
Pruebe CPLEX que está disponible gratis para los estudiantes.
Una de las bibliotecas mejor respetadas para este tipo de trabajo de optimización es NAG libraries. Estos se utilizan en todo el mundo en las universidades y la industria. Están disponibles para C/FORTRAN. Son muy no gratuitos y contienen mucho más que funciones de minimización. Se cubren muchas matemáticas numéricas generales.
De todos modos, sospecho que esta biblioteca es demasiado para lo que necesita. Pero aquí están las partes relacionadas con la minimización: Local Minimisation y Global Minimization.
Esta biblioteca también se ve muy bien, pero la parte "muy no libre" me hace recelarme de usarla – Jim
Parece que eres bastante nuevo en los métodos de minimización. Cada vez que necesito aprender un nuevo conjunto de métodos numéricos, generalmente miro en Numerical Recipes. Es un libro que proporciona una buena visión general de los métodos más comunes en el campo, sus intercambios y (importante) dónde buscar en la literatura para obtener más información. Por lo general, no es donde me detengo, pero a menudo es un punto de partida útil.
Por ejemplo, si su función es costosa, su objetivo es minimizar el número de evaluaciones que deben converger. Si tiene expresiones analíticas para el gradiente, entonces un método basado en gradiente probablemente le resulte ventajoso, suponiendo que la función y su gradiente se comportan bien (carecen de singularidades) en el dominio de interés.
Si no tiene gradientes analíticos, entonces casi siempre es mejor usar un enfoque como downhill simplex que solo evalúa la función (no sus gradientes). Los gradientes numéricos son caros.
También tenga en cuenta que todos estos enfoques convergerán a los mínimos locales, por lo que son bastante sensibles al punto en el que inicialmente inicia el optimizador. La optimización global es una bestia totalmente diferente.
Como reflexión final, casi todo el código que puede encontrar para la minimización será razonablemente eficiente. El costo real de la minimización está en la función de costos. Debe dedicar tiempo a la creación de perfiles y optimizar su función de costos, y seleccione un algoritmo que minimice el número de veces que necesita llamarlo (métodos como downhill simplex, conjugate gradient y BFGS brillan en diferentes tipos de problemas).
En términos de código real, puede encontrar muchas rutinas agradables en NETLIB, además de las otras bibliotecas que se han mencionado. La mayoría de las rutinas están en FORTRAN 77, pero no todas; convertirlos a C, f2c es bastante útil.
Una nota adicional sobre el uso de las funciones fortran es que, por lo general, es bastante fácil vincular el código C y el código fortran. Bibliotecas fortran especialmente bien estructuradas. –
¿Qué sería _fast_? No exacto? Respuestas en caché para consultas anteriores? O algún otro tipo de criterio? – sarnold
@sarnold True. No exacto está bien, no necesito alcanzar el óptimo global.Solo quiero algo que pueda lograr resultados rápidamente que sean mejores que la búsqueda aleatoria :) Me gustaría jugar con el tiempo que le permití correr para ver la compensación de tiempo/mejora. – Jim
¿Por qué es lenta su implementación? – Jacob