Biblioteca C ++ para minimización restringida no lineal

Actualmente estoy tratando de resolver el problema de minimización restringida no lineal implementado en la función matlab "fmincon". Mis expectativas son, minimizar (fun1, x0, uB, lB, fun2) donde x0 es el estado inicial, fun1 es una función que debe minimizarse, uB son límites superiores, lB son límites inferiores y fun2 es una función que proporciona vectores de igualdades no lineales / desigualdades como se describe en http://www.mathworks.com/help/optim/ug/fmincon.htmlcomo no noncon Estos vectores también están cambiando a través de iteraciones (no dependen linealmente de x_n, n-ésima iteración del vector solución). En la implementación de matlab están en una forma c (x) <= 0. Este es el último fragmento de código que necesita ser portado de matlab a c ++ y he estado luchando mucho mientras trataba de encontrar la biblioteca de c ++ apropiada que contenga este algoritmo. Es por eso que estoy buscando ayuda aquí y agradecería mucho si pudiera proporcionar su experiencia.

Un buen ejemplo de lo que quiero hacer es el primero en esta página http://www.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-examples.html#f10960?s_tid=doc_12b La única diferencia es que yo necesita límites también ...

Gracias por adelantado.

Peter

c++ nonlinear-programming Peter Kottas
fuente

Existe la posibilidad de usar NLOPT ab-initio.mit.edu/wiki/index.php/NLopt_C-plus-plus_Reference pero necesitaría calcular diferencias finitas usando múltiples llamadas a la evaluación de función "minimizada" de la función objetivo y fui amable de esperar que eso se solucione por algoritmo para mejorar el rendimiento. Mi función minimizada es realmente costosa de calcular. Solo para aclarar, la función minimizada es la probabilidad logarítmica del modelo estimado con datos originales en la estimación del modelo de cambio de Markov de series temporales.

Peter Kottas

¿Has mirado las respuestas a esta pregunta ? Si sus requisitos no se abordan suficientemente allí, debe editar su pregunta para señalarlos y obtener recomendaciones útiles.

Christian Clason

Gracias, hay información útil allí. Actualmente estoy hasta los codos en la biblioteca NLOPT desde que descubrí que también podría adaptarse a mi problema. Mantendré este tema publicado y proporcionaré una solución cuando se me ocurra uno. Todavía se agradece cualquier ayuda que pueda acelerar el proceso. Implementación real, por ejemplo, etc.

Peter Kottas

Varias preguntas: 1. ¿Es su problema convexo? 2. ¿Son diferenciables el objetivo y las limitaciones? Si es así, ¿cuántas veces? ¿Una vez? ¿Dos veces? 3. ¿Puedes calcular esas derivadas fácilmente, si existen? ¿Serían fáciles de calcular las aproximaciones de diferencias finitas si no tiene esos derivados fácilmente disponibles? 4. ¿Cuántas variables de decisión tienes? (es decir, ¿sobre cuántas variables intenta minimizar?) Sería suficiente una estimación aproximada. 5. ¿Son caras las evaluaciones de funciones? Sería útil tener toda esta información para darle una mejor respuesta.

Geoff Oxberry

¡Hola! En primer lugar, gracias por responder. 1. Difícil de decir pero muy probablemente no, porque la función minimizada es la probabilidad logarítmica entre la estimación del modelo de conmutación de Markov de series temporales en aplicaciones financieras y, por su naturaleza, supongo una especie de salida ruidosa. 2.no 3.solo usando diferencias finitas 4. el vector de solución consiste en n variables donde n depende de los parámetros deseados de los modelos, en general de 12 a 30 30 5. la probabilidad de registro entre el modelo y los datos originales es costosa, desigualdades no lineales adicionales son baratos de calcular

Peter Kottas

Respuestas:

Si su función no es diferenciable, debe tener cuidado con la forma en que usa las diferencias finitas. Si desea utilizar información derivada, su mejor opción es probablemente algún tipo de método de tipo Newton semi-liso. Un conjunto de notas que describen tales métodos se puede encontrar aquí .

De doce a treinta variables probablemente se encuentren en el extremo superior de lo que se puede hacer con los métodos de búsqueda de patrones (también llamados búsqueda directa). Aquí se puede encontrar un artículo de revisión reciente de Rios y Sahinidis en Journal of Global Optimization sobre métodos de optimización sin derivados (como los métodos de búsqueda de patrones) , junto con una página web complementaria . Aquí se puede encontrar un artículo de revisión menos reciente sobre estos métodos por Kolda, Lewis y Torczon en SIAM Review . Estos métodos funcionan bastante bien con evaluaciones de funciones costosas y no requieren necesariamente diferenciabilidad o información derivada.

Muchos de estos métodos requieren algún tipo de convexidad para garantizar la convergencia al óptimo global, por lo tanto, si tuviera que resolver su problema rigurosamente, es posible que necesite unir estos métodos anteriormente con una estrategia de bifurcación. Sin embargo, si no te importa el rigor, un enfoque como el de MATLABfmincon podría funcionar lo suficientemente bien (ya no hay garantías). Es muy probable que las diferencias finitas le brinden un miembro del subdireccional de su función no diferenciable, lo que podría ser suficiente para que su instancia de problema y datos de entrada particulares devuelvan un resultado suficientemente preciso para sus propósitos. En ese caso, probablemente debería mirar las bibliotecas mencionadas en las respuestas a la pregunta que Christian enlazó en su comentario.

Geoff Oxberry
fuente

Si todo lo que necesita es una biblioteca C ++ para resolver problemas de optimización no lineal, puede usar RobOptim . Aunque RobOptim se desarrolló inicialmente teniendo en cuenta los problemas de optimización robótica, es adecuado para cualquier problema de optimización no lineal. Proporciona una interfaz C ++ simple con complementos para múltiples solucionadores no lineales ( Ipopt , NAG , etc.). El uso de ese tipo de envoltorios facilita el uso de otro solucionador de PNL. Si no puede proporcionar gradientes, el cálculo de diferencias finitas se puede hacer automáticamente.

Es de código abierto, por lo que puede consultar el código fuente en GitHub: https://github.com/roboptim/

El análisis realizado por @Geoff Oxberry es esencial para la elección del solucionador no lineal que llamará RobOptim. Tenga en cuenta que cuando se trata con ese tipo de solucionadores, el ajuste de parámetros puede tener un gran impacto en el rendimiento y aún puede quedar atrapado en las minimas locales (realmente depende del tipo de problema con el que esté lidiando).

Nota: Soy uno de los desarrolladores de este proyecto.

BenC
fuente