¿Existe un solucionador de programación no lineal de alta calidad para Python?

Tengo que resolver varios problemas desafiantes de optimización global no convexo. Actualmente uso la Caja de herramientas de optimización de MATLAB (específicamente, fmincon()con algoritmo = 'sqp'), que es bastante eficaz . Sin embargo, la mayor parte de mi código está en Python, y me encantaría hacer la optimización también en Python. ¿Existe un solucionador de PNL con enlaces de Python con el que pueda competir fmincon()? Debería

• ser capaz de manejar restricciones no lineales de igualdad y desigualdad
• no requiere que el usuario proporcione un jacobiano.

Está bien si no garantiza un óptimo global ( fmincon()no lo hace). Estoy buscando algo que converja de manera sólida con un óptimo local, incluso para problemas desafiantes, e incluso si es un poco más lento que fmincon().

He probado varios de los solucionadores disponibles a través de OpenOpt y he encontrado que son inferiores a los de MATLAB fmincon/sqp.

Solo para enfatizar , ya tengo una formulación manejable y un buen solucionador. Mi objetivo es simplemente cambiar los idiomas para tener un flujo de trabajo más ágil.

Geoff señala que algunas características del problema pueden ser relevantes. Son:

• 10-400 variables de decisión
• 4-100 restricciones de igualdad polinomial (el grado polinomial varía de 1 a aproximadamente 8)
• Un número de restricciones de desigualdad racional igual a aproximadamente el doble del número de variables de decisión
• La función objetivo es una de las variables de decisión.

El jacobiano de las restricciones de igualdad es denso, al igual que el jacobiano de las restricciones de desigualdad.

fmincon(), como mencionó, emplea varias estrategias que son bien conocidas en la optimización no lineal que intentan encontrar un mínimo local sin tener en cuenta si se ha encontrado el óptimo global. Si está de acuerdo con esto, entonces creo que ha formulado la pregunta correctamente (optimización no lineal).

El mejor paquete que conozco para la optimización no lineal general es IPOPT [1]. Aparentemente, Matthew Xu mantiene un conjunto de enlaces de Python a IPOPT , por lo que este podría ser un lugar para comenzar.

[1]: Andreas Wachter es un amigo personal, por lo que puedo ser un poco parcial.

Trabajo en un laboratorio que hace la optimización global de problemas de enteros mixtos y no convexos. Mi experiencia con los solucionadores de optimización de código abierto ha sido que los mejores suelen estar escritos en un lenguaje compilado, y tienen un rendimiento pobre en comparación con los paquetes de optimización comercial.

Si puede formular su problema como un sistema explícito de ecuaciones y necesita un solucionador gratuito, su mejor opción es probablemente IPOPT, como dijo Aron. Se pueden encontrar otros solucionadores gratuitos en el sitio web COIN-OR . Que yo sepa, los solucionadores no lineales no tienen enlaces Python proporcionados por los desarrolladores; cualquier enlace que encuentre sería de terceros. Para obtener buenas soluciones, también deberá envolver cualquier solucionador convexo no lineal que haya encontrado en las heurísticas estocásticas de optimización global apropiadas, o en un algoritmo de optimización global determinista como ramificar y vincular. Alternativamente, podría usar Bonmin o Couenne, los cuales son solucionadores de optimización no convexos deterministas que funcionan muy bien en comparación con el solucionador de vanguardia, BARON .

Si puede comprar un solucionador de optimización comercial, puede considerar mirar el lenguaje de modelado GAMS , que incluye varios solucionadores de optimización no lineales. De particular mención son las interfaces para los solucionadores CONOPT, SNOPT y BARON. (CONOPT y SNOPT son solucionadores convexos). Una solución kludgey que he usado en el pasado es usar los enlaces de lenguaje Fortran (o Matlab) a GAMS para escribir un archivo GAMS y llamar a GAMS desde Fortran (o Matlab) para calcular el Solución de un problema de optimización. GAMS tiene enlaces de lenguaje Python y un personal de soporte muy receptivo dispuesto a ayudar si hay algún problema. (Descargo de responsabilidad: no estoy afiliado a GAMS, pero mi laboratorio posee una licencia de GAMS). Los solucionadores comerciales no deberían ser peores quefmincon; De hecho, me sorprendería que no fueran mucho mejores. Si sus problemas son lo suficientemente pequeños, entonces es posible que ni siquiera necesite comprar una licencia GAMS y licencias para solucionadores, porque se puede descargar una copia de evaluación de GAMS de su sitio web. De lo contrario, es probable que desee decidir qué solucionadores comprar junto con una licencia GAMS. Vale la pena señalar que BARON requiere un solucionador de programación lineal de enteros mixtos, y que las licencias para los dos mejores solucionadores de programación lineal de enteros mixtos CPLEX y GUROBI son gratuitos para académicos, por lo que es posible que pueda salirse con la compra de las interfaces GAMS. que las interfaces y las licencias de solucionador, que pueden ahorrarle bastante dinero.

Este punto vale la pena repetir: para cualquiera de los solucionadores de optimización deterministas no convexos que he mencionado anteriormente, debe poder formular el modelo como un conjunto explícito de ecuaciones. De lo contrario, los algoritmos de optimización no convexos no funcionarán, porque todos ellos se basan en análisis simbólicos para construir relajaciones convexas para algoritmos similares a ramas y límites.

ACTUALIZACIÓN: Un pensamiento que no se me había ocurrido al principio era que también podría llamar al Kit de herramientas para la optimización avanzada ( TAO ) y PETSc usando tao4py y petsc4py , lo que tendría el beneficio adicional de una paralelización más fácil y una mayor familiaridad con PETSc y las herramientas ACTS .

ACTUALIZACIÓN # 2: Según la información adicional que mencionó, los métodos de programación cuadrática secuencial (SQP) serán su mejor opción. Los métodos SQP generalmente se consideran más robustos que los métodos de punto interior, pero tienen el inconveniente de requerir soluciones lineales densas. Como te importa más la robustez que la velocidad, SQP será tu mejor opción. No puedo encontrar un buen solucionador de SQP por ahí escrito en Python (y aparentemente, tampoco podría Sven Leyffer en Argonne en este informe técnico ). Supongo que los algoritmos implementados en paquetes como SciPy y OpenOpt tienen implementado el esqueleto básico de algunos algoritmos SQP, pero sin la heurística especializada que utilizan los códigos más avanzados para superar los problemas de convergencia. Podrías probar NLopt, escrito por Steven Johnson en el MIT. No tengo muchas esperanzas porque no tengo ninguna reputación que yo sepa, pero Steven Johnson es un tipo brillante que escribe un buen software (después de todo, coescribió FFTW). Implementa una versión de SQP; si es un buen software, hágamelo saber.

Esperaba que TAO tuviera algo en el camino de un solucionador de optimización restringido, pero no lo tiene. Ciertamente podrías usar lo que tienen para construir uno; Tienen muchos componentes allí. Sin embargo, como señaló, sería mucho más trabajo para usted hacer eso, y si tiene ese tipo de problemas, también podría ser un desarrollador de TAO.

Con esa información adicional, es más probable que obtenga mejores resultados llamando a GAMS desde Python (si es que es una opción), o tratando de parchear la interfaz IPOPT Python. Dado que IPOPT utiliza un método de punto interior, no será tan robusto, pero tal vez la implementación de Andreas de un método de punto interior es considerablemente mejor que la implementación de SQP de Matlab, en cuyo caso, es posible que no esté sacrificando la robustez en absoluto. Tendría que ejecutar algunos estudios de caso para saber con certeza.

Ya conoces el truco para reformular las restricciones de desigualdad racional como restricciones de desigualdad polinomiales (está en tu libro); La razón por la que esto ayudaría a BARON y a otros solucionadores no convexos es que puede usar el análisis de términos para generar desigualdades válidas adicionales que puede usar como cortes para mejorar y acelerar la convergencia del solucionador.

Excluyendo los enlaces Python de GAMS y la interfaz de Python a IPOPT, la respuesta es no, todavía no hay solucionadores de programación no lineal de alta calidad para Python. Quizás @Dominique cambie eso con NLPy.

ACTUALIZACIÓN # 3: Más puñaladas salvajes para encontrar un solucionador basado en Python produjeron PyGMO , que es un conjunto de enlaces de Python a PaGMO, un solucionador de optimización multiobjetivo global basado en C ++. Aunque fue creado para la optimización multiobjetivo, también se puede utilizar para la programación no lineal de un solo objetivo, y tiene interfaces Python para IPOPT y SNOPT, entre otros solucionadores. Fue desarrollado dentro de la Agencia Espacial Europea , por lo que es de esperar que haya una comunidad detrás. También fue lanzado relativamente recientemente (24 de noviembre de 2011).

Actualización: vea el nuevo paquete GEKKO que acabamos de lanzar.

APM Python es una caja de herramientas de optimización gratuita que tiene interfaces para APOPT, BPOPT, IPOPT y otros solucionadores. Proporciona primera información (jacobiana) y segunda (hessiana) a los solucionadores y proporciona una interfaz web opcional para ver los resultados. El cliente APM Python se instala con pip:

 pip install APMonitor

También se puede instalar en un script de Python con:

try:
    from APMonitor.apm import *
except:
    # Automatically install APMonitor
    import pip
    pip.main(['install','APMonitor'])
    from APMonitor.apm import *

Hemos realizado un par de pruebas de referencia y descubrimos que la combinación de APOPT (método de ajuste activo) e IPOPT (método de punto interior) puede resolver un gran porcentaje de problemas de referencia. Hay una serie de problemas de ejemplo que se incluyen con el archivo zip de descarga. Con el que probablemente querrás comenzar es con el problema Hock Schittkowski # 71. Es el ejemplo más simple y demuestra cómo resolver problemas de optimización restringidos.

Hay una interfaz de navegador y una API para Python / MATLAB. La API para Python es un script único (apm.py) que está disponible para descargar desde la página de inicio de apmonitor.com. Una vez que el script se carga en un código Python, le da la capacidad de resolver problemas de:

• Ecuaciones no lineales
• Programación no lineal entera mixta
• Ecuaciones diferenciales y algebraicas
• Ajuste del modelo de mínimos cuadrados
• Estimación del horizonte móvil
• Control predictivo del modelo no lineal.
• etc.

Para el nuevo usuario, el software APM Python tiene un foro de Grupos de Google donde un usuario puede publicar preguntas. Hay seminarios web que muestran problemas de optimización en la investigación y la ingeniería de operaciones.

A continuación se muestra un ejemplo de un problema de optimización (hs71.apm).

Model
  Variables
    x[1] = 1, >=1, <=5
    x[2] = 5, >=1, <=5
    x[3] = 5, >=1, <=5
    x[4] = 1, >=1, <=5
  End Variables

  Equations
    x[1] * x[2] * x[3] * x[4] > 25
    x[1]^2 + x[2]^2 + x[3]^2 + x[4]^2 = 40

    minimize  x[1] * x[4] * (x[1]+x[2]+x[3]) + x[3]
  End Equations
End Model

El problema de optimización se resuelve con el siguiente script de Python:

from APMonitor.apm import *
server = 'http://byu.apmonitor.com'

# Application name
app = 'eqn'

# Clear previous application
apm(server,app,'clear all')

# Load model file
apm_load(server,app,'hs71.apm')

# Option to select solver (1=APOPT, 2=BPOPT, 3=IPOPT)
apm_option(server,app,'nlc.solver',3)

# Solve on APM server
solver_output = apm(server,app,'solve')

# Display solver output
print(solver_output)

# Retrieve results
results = apm_sol(server,app)

# Display results
print('--- Results of the Optimization Problem ---')
print(results)

# Display Results in Web Viewer 
url = apm_var(server,app)
print("Opened Web Viewer: " + url)

APM Python es un servicio web gratuito para la optimización. Los problemas de optimización se resuelven en servidores remotos y los resultados se devuelven al script local de Python. También se puede descargar un servidor local APMonitor para que no se requiera una conexión a Internet ( servidor de descarga ). Recientemente agregamos soporte de procesamiento paralelo para MATLAB y Python. El módulo Python es compatible con Python 2.7 o Python 3+.

Aunque esto no responde completamente a su pregunta, creo un paquete de Python para programación no lineal llamado NLPy. La versión más reciente se puede recuperar de https://github.com/dpo/nlpy

Debo enfatizar que NLPy es de grado de investigación y que los solucionadores incluidos no son tan robustos como los códigos más experimentados como IPOPT. Además, actualmente requieren que se proporcionen jacobianos. Dicho esto, el objetivo de NLPy es proporcionar las herramientas necesarias para que los investigadores ensamblen solucionadores personalizados si es necesario. En cualquier caso, me interesaría escuchar sus comentarios fuera de línea si lo intenta. También puede encontrar útiles los paquetes relacionados https://github.com/dpo/pykrylov y https://github.com/dpo/pyorder . Actualmente, definitivamente falta la documentación de NLPy. Los otros dos deberían ser razonables.

pyomo es un entorno de modelado completo similar a GAMS / AMPL para la optimización en python. Es extremadamente potente, tiene interfaces para todos los solucionadores que son compatibles con AMPL y genera jacobianos, etc. de forma automática. Sin embargo, debido a que se ejecuta en un 'entorno virtual de Python', puede que no sea trivial vincularlo al código existente.

Recientemente lanzamos (2018) el paquete Python de GEKKOpara programación no lineal con solucionadores como IPOPT, APOPT, BPOPT, MINOS y SNOPT con métodos activos de puntos fijos e interiores. Uno de los problemas con el uso de estos solucionadores es que normalmente necesita proporcionar al menos primeras derivadas y opcionalmente segundas derivadas. Hay varios buenos lenguajes de modelado que pueden hacer esto por usted, como se menciona con otras respuestas. GEKKO compila las ecuaciones en código de bytes para que sea como si hubiera escrito el modelo en Fortran o C ++ en términos de velocidad. La diferenciación automática proporciona las derivadas primera y segunda en forma dispersa a los solucionadores basados ​​en gradiente. Diseñamos GEKKO para problemas de control óptimos, pero también puede resolver problemas similares a fmincon. A continuación se muestra un ejemplo rápido de un problema de programación no lineal con restricciones de igualdad y desigualdad. Primero tú'

pip install gekko

El problema Hock Schittkowski # 71 se muestra a continuación como un ejemplo de una función objetivo, restricción de desigualdad, restricción de igualdad y cuatro variables con límites superior e inferior.

from gekko import GEKKO
m = GEKKO() # Initialize gekko
# Initialize variables
x1 = m.Var(value=1,lb=1,ub=5)
x2 = m.Var(value=5,lb=1,ub=5)
x3 = m.Var(value=5,lb=1,ub=5)
x4 = m.Var(value=1,lb=1,ub=5)
# Equations
m.Equation(x1*x2*x3*x4>=25)
m.Equation(x1**2+x2**2+x3**2+x4**2==40)
m.Obj(x1*x4*(x1+x2+x3)+x3) # Objective
m.options.IMODE = 3 # Steady state optimization
m.solve() # Solve
print('Results')
print('x1: ' + str(x1.value))
print('x2: ' + str(x2.value))
print('x3: ' + str(x3.value))
print('x4: ' + str(x4.value))    

GEKKO funciona en todas las plataformas (Windows, MacOS, Linux, procesadores ARM) y con Python 2.7 y 3+. Una opción totalmente local está disponible sin conexión a Internet configurando la opción "remoto = Falso". La opción local actualmente solo está disponible para Windows y estamos trabajando en otras versiones como procesadores Linux, MacOS, ARM para que se ejecuten localmente sin conexión a Internet. La versión local incluye solo solucionadores gratuitos que no requieren una licencia. Por defecto, el problema se envía a un servidor público donde se calcula la solución y se devuelve a Python.

Aunque esta pregunta trata específicamente sobre la resolución de la programación no lineal en Python, también destacaré algunos otros tipos de problemas que GEKKO puede resolver y algunos recursos para la optimización del aprendizaje. GEKKO también resuelve ecuaciones algebraicas de enteros mixtos y diferenciales y tiene varios objetos preprogramados para controles avanzados (similares a DMC, RMPCT, etc.). Los modos de operación incluyen reconciliación de datos, optimización en tiempo real, simulación dinámica y control predictivo no lineal.

Enseño dos cursos sobre optimización (optimización de diseño y optimización dinámica ) y he publicado el material del curso en línea. El curso de optimización dinámica se ofrece cada año a partir de enero y utilizamos el paquete GEKKO Python (y MATLAB) para el curso. GEKKO es una extensión de APMonitor Optimization Suite, pero ha integrado el modelado y la visualización de soluciones directamente en Python. Las referencias APMonitor y GEKKO ofrecen una muestra de los tipos de aplicaciones que se pueden resolver con este paquete. GEKKO se desarrolla bajo la National Science Foundation Research Grant # 1547110 .

¿Qué pasa con scipy.fmin_slsqp?

http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fmin_slsqp.html

PyGMO contiene varios solucionadores, proporcionándoles la misma interfaz. IPOPT y scipy slsqp se incluyen en caso de que compile el código y descargue / instale el código de terceros de forma independiente.

Como beneficio adicional, el uso paralelo del solucionador se hace realmente fácil (multistart) a través de la clase archipiélago.

Hay cvxmod , una envoltura de Python alrededor del software de optimización convexa de Stephen Boyd. Es parte del paquete Sage .

fmincon ahora se puede usar desde Python a través del marco OpenOpt, opcionalmente con una diferenciación automática densa / dispersa por FuncDesigner http://openopt.org/fmincon

$\to$ $\to$

¿El salto de cuenca a través de Scipy es suficiente para sus necesidades? Si devuelve un mínimo local y no un mínimo global, puede cambiar el número de iteraciones y / o aplicar límites.

¿Qué tal CMA-ES? Tiene enlaces de Python y se adapta bien a problemas de optimización no lineales y no convexos y lo he usado bastante: https://www.lri.fr/~hansen/cmaesintro.html

Instalación a través de pip:

pip install cma

Aquí hay un código de muestra de su sitio web:

import cma
help(cma)  # "this" help message, use cma? in ipython
help(cma.fmin)
help(cma.CMAEvolutionStrategy)
help(cma.CMAOptions)
cma.CMAOptions('tol')  # display 'tolerance' termination options
cma.CMAOptions('verb') # display verbosity options
res = cma.fmin(cma.Fcts.tablet, 15 * [1], 1)
res[0]  # best evaluated solution
res[5]  # mean solution, presumably better with noise

Dado que MATLAB tiene un compilador JIT mientras que CPython aún no lo tiene (al menos, hasta que pypy obtenga soporte completo). Parece que quiere un solucionador gratuito que supere a los producidos comercialmente fmincon. ¿No es demasiado?

IIRC entre los solucionadores comerciales de PNL, solo snopt ha proporcionado una API de Python hasta ahora (aunque es bastante feo).

¿Qué solucionadores de OpenOpt has probado? ¿Cuántas variables y restricciones tienes en tu tarea no convexa?

Puede probar IPOPT a través de la API OpenOpt / Funcdesigner sin instalación en el servidor OpenOpt Sage (preste atención a la imagen "cambiar de sabio a python").

$10^{300}(x-0.1)^2 + 10^{-300}(y-0.2)^2$$(x,y) = (1,1)$

para problemas globales, podría estar interesado en http://openopt.org/interalg y otros solucionadores globales de openopt (http://openopt.org/GLP) para la optimización local. openopt también ofrece una variedad de solucionadores: http://openopt.org / PNL

Es bueno mencionar aquí que el solucionador Google Ceres es en realidad un optimizador no lineal muy poderoso, utilizado en muchos proyectos.

También hay un contenedor de python disponible aquí: https://github.com/rll/cyres

KNITRO tiene interfaces Python y MATLAB, entre otras. Piense en ello como un reemplazo de FMINCON, pero con un rendimiento mucho mejor y más costoso. https://www.artelys.com/en/optimization-tools/knitro#doc-tab .

Soy usuario de KNITRO, pero no estoy afiliado al producto.