Gibt es einen hochwertigen nichtlinearen Programmierlöser für Python?

Ich habe mehrere herausfordernde nicht konvexe globale Optimierungsprobleme zu lösen. Derzeit verwende ich die Optimization Toolbox von MATLAB (speziell fmincon()mit algorithm = 'sqp'), was sehr effektiv ist . Der größte Teil meines Codes ist jedoch in Python, und ich würde die Optimierung gerne auch in Python durchführen. Gibt es einen NLP-Löser mit Python-Bindungen, der mithalten kann fmincon()? Es muss

• in der Lage sein, nichtlineare Gleichheits- und Ungleichheitsbeschränkungen zu handhaben
• Es ist nicht erforderlich, dass der Benutzer einen Jacobian bereitstellt.

Es ist in Ordnung, wenn es kein globales Optimum garantiert ( fmincon()nicht). Ich bin auf der Suche nach etwas, das auch bei herausfordernden Problemen und selbst wenn es etwas langsamer ist, stabil gegen ein lokales Optimum konvergiert fmincon().

Ich habe mehrere der über OpenOpt verfügbaren Löser ausprobiert und festgestellt, dass sie MATLABs unterlegen sind fmincon/sqp.

Nur zur Verdeutlichung habe ich bereits eine handhabbare Formulierung und einen guten Löser. Mein Ziel ist es lediglich, die Sprache zu ändern, um einen optimierten Workflow zu erzielen.

Geoff weist darauf hin, dass einige Merkmale des Problems relevant sein können. Sie sind:

• 10-400 Entscheidungsvariablen
• 4-100 polynomiale Gleichheitsbedingungen (Polynomgrad reicht von 1 bis ca. 8)
• Eine Anzahl von rationalen Ungleichungsbeschränkungen entspricht ungefähr der doppelten Anzahl von Entscheidungsvariablen
• Die Zielfunktion ist eine der Entscheidungsvariablen

Der Jacobian der Gleichheitsbeschränkungen ist dicht, ebenso wie der Jacobian der Ungleichheitsbeschränkungen.

fmincon()Wie Sie bereits erwähnt haben, werden mehrere in der nichtlinearen Optimierung bekannte Strategien angewendet, die versuchen, ein lokales Minimum zu finden, ohne zu berücksichtigen, ob das globale Optimum gefunden wurde. Wenn Sie damit einverstanden sind, haben Sie die Frage meines Erachtens richtig formuliert (nichtlineare Optimierung).

Das beste mir bekannte Paket für die allgemeine nichtlineare Optimierung ist IPOPT [1]. Anscheinend unterhält Matthew Xu eine Reihe von Python-Bindungen an IPOPT , daher könnte dies ein Anfang sein.

[1]: Andreas Wachter ist ein persönlicher Freund, daher bin ich vielleicht ein bisschen voreingenommen.

Ich arbeite in einem Labor, das globale Optimierungen von gemischt-ganzzahligen und nicht-konvexen Problemen durchführt. Meine Erfahrung mit Open-Source-Optimierungslösern hat gezeigt, dass die besseren in der Regel in einer kompilierten Sprache geschrieben sind und im Vergleich zu kommerziellen Optimierungspaketen schlecht abschneiden.

Wenn Sie Ihr Problem als explizites Gleichungssystem formulieren können und einen freien Löser benötigen, ist IPOPT Ihre beste Wahl, wie Aron sagte. Weitere kostenlose Löser finden Sie auf der COIN-OR -Website. Meines Wissens verfügen die nichtlinearen Löser nicht über Python-Bindungen, die von den Entwicklern bereitgestellt wurden. Alle Bindungen, die Sie finden, sind von Drittanbietern. Um gute Lösungen zu erhalten, müssen Sie auch jeden nichtlinearen, konvexen Solver einschließen, den Sie in einer geeigneten stochastischen globalen Optimierungsheuristik oder in einem deterministischen globalen Optimierungsalgorithmus wie branch-and-bound gefunden haben. Alternativ können Sie Bonmin oder Couenne verwenden. Beide sind deterministische nichtkonvexe Optimierungslöser, die im Vergleich zum aktuellen Löser BARON eine gute Leistung erbringen .

Wenn Sie einen kommerziellen Optimierungslöser erwerben können, sollten Sie sich die GAMS- Modellierungssprache ansehen , die mehrere nichtlineare Optimierungslöser enthält. Besonders hervorzuheben sind die Schnittstellen zu den Lösern CONOPT, SNOPT und BARON. (CONOPT und SNOPT sind konvexe Löser.) Eine kluge Lösung, die ich in der Vergangenheit verwendet habe, besteht darin, die Sprachbindungen von Fortran (oder Matlab) für GAMS zu verwenden, um eine GAMS-Datei zu schreiben und GAMS aus Fortran (oder Matlab) aufzurufen, um die zu berechnen Lösung eines Optimierungsproblems. GAMS verfügt über Python-Sprachbindungen und einen sehr reaktionsschnellen Support, der bereit ist, bei Problemen zu helfen. (Haftungsausschluss: Ich bin nicht mit GAMS verbunden, mein Labor besitzt jedoch eine GAMS-Lizenz.) Die kommerziellen Löser sollten nicht schlechter sein alsfmincon; Tatsächlich wäre ich überrascht, wenn sie nicht viel besser wären. Wenn Ihre Probleme ausreichend klein sind, müssen Sie möglicherweise nicht einmal eine GAMS-Lizenz und Lizenzen für Löser erwerben, da eine Testversion von GAMS von deren Website heruntergeladen werden kann. Andernfalls möchten Sie wahrscheinlich entscheiden, welche Löser in Verbindung mit einer GAMS-Lizenz erworben werden sollen. Es ist erwähnenswert, dass BARON einen linearen Programmierlöser mit gemischten Ganzzahlen benötigt und dass die Lizenzen für die beiden besten linearen Programmierlöser mit gemischten Ganzzahlen, CPLEX und GUROBI, für Akademiker kostenlos sind, sodass Sie möglicherweise nicht nur die GAMS-Schnittstellen erwerben müssen als die Schnittstellen und die Löser-Lizenzen, die Sie viel Geld sparen können.

Dieser Punkt muss wiederholt werden: Für jeden der oben erwähnten deterministischen nichtkonvexen Optimierungslöser müssen Sie in der Lage sein, das Modell als expliziten Satz von Gleichungen zu formulieren. Andernfalls funktionieren die nichtkonvexen Optimierungsalgorithmen nicht, da alle auf einer symbolischen Analyse beruhen, um konvexe Relaxationen für verzweigungs- und gebundene Algorithmen zu konstruieren.

UPDATE: Ein Gedanke, der mir anfangs nicht in den Sinn kam , war, dass Sie das Toolkit für Advanced Optimization ( TAO ) und PETSc auch mit tao4py und petsc4py aufrufen können , was den potenziellen zusätzlichen Vorteil einer einfacheren Parallelisierung und der Nutzung der Vertrautheit mit PETSc hätte und die ACTS- Tools.

UPDATE 2: Aufgrund der von Ihnen erwähnten zusätzlichen Informationen sind Methoden der sequentiellen quadratischen Programmierung (SQP) die beste Wahl. SQP-Methoden gelten im Allgemeinen als robuster als interne Punktmethoden, haben jedoch den Nachteil, dass dichte lineare Lösungen erforderlich sind. Da Ihnen Robustheit wichtiger ist als Geschwindigkeit, ist SQP die beste Wahl. Ich kann keinen guten SQP-Solver finden, der in Python geschrieben wurde (und Sven Leyffer in Argonne in diesem technischen Bericht anscheinend auch nicht ). Ich vermute, dass die in Paketen wie SciPy und OpenOpt implementierten Algorithmen das Grundgerüst einiger SQP-Algorithmen aufweisen, jedoch ohne die speziellen Heuristiken, die fortgeschrittenere Codes zur Überwindung von Konvergenzproblemen verwenden. Sie könnten NLopt versuchen, geschrieben von Steven Johnson am MIT. Ich habe keine großen Hoffnungen, weil es keinen Ruf hat, den ich kenne, aber Steven Johnson ist ein brillanter Typ, der gute Software schreibt (schließlich hat er FFTW mitgeschrieben). Es implementiert eine Version von SQP. Wenn es eine gute Software ist, lass es mich wissen.

Ich hatte gehofft, dass TAO einen eingeschränkten Optimierungslöser darstellen würde, aber das ist nicht der Fall. Sie könnten sicherlich das gebrauchen, was sie brauchen, um einen aufzubauen; Sie haben viele der Komponenten dort. Sie haben jedoch darauf hingewiesen, dass es viel mehr Arbeit für Sie bedeutet, und wenn Sie in solche Schwierigkeiten geraten, können Sie auch ein TAO-Entwickler sein.

Mit diesen zusätzlichen Informationen erzielen Sie mit größerer Wahrscheinlichkeit bessere Ergebnisse beim Aufrufen von GAMS über Python (falls dies überhaupt eine Option ist) oder beim Versuch, die IPOPT-Python-Oberfläche zu patchen. Da IPOPT eine Innenpunktmethode verwendet, ist sie nicht so robust, aber vielleicht ist die Implementierung einer Innenpunktmethode durch Andreas erheblich besser als die Implementierung von SQP durch Matlab. In diesem Fall müssen Sie möglicherweise überhaupt keine Einbußen bei der Robustheit hinnehmen. Sie müssten einige Fallstudien durchführen, um sicherzugehen.

Sie kennen bereits den Trick, die rationalen Ungleichungsbeschränkungen in polynomiale Ungleichungsbeschränkungen umzuformulieren (das steht in Ihrem Buch). Der Grund, warum dies BARON und einigen anderen nicht konvexen Lösern helfen würde, besteht darin, dass sie Termanalyse verwenden können, um zusätzliche gültige Ungleichungen zu generieren, die sie als Kürzungen verwenden können, um die Konvergenz von Lösern zu verbessern und zu beschleunigen.

Ohne die GAMS-Python-Bindungen und die Python-Schnittstelle zu IPOPT lautet die Antwort: Nein, es gibt noch keine hochwertigen nichtlinearen Programmierlöser für Python. Vielleicht wird @Dominique das mit NLPy ändern.

UPDATE Nr. 3: Mehr wilde Versuche , einen Python-basierten Löser zu finden, führten zu PyGMO , einer Reihe von Python-Bindungen zu PaGMO, einem C ++ -basierten globalen Multiobjektiv-Optimierungslöser. Obwohl es für die multiobjektive Optimierung entwickelt wurde, kann es auch zur nichtlinearen Einzelzielprogrammierung verwendet werden und verfügt unter anderem über Python-Schnittstellen zu IPOPT und SNOPT. Es wurde innerhalb der Europäischen Weltraumorganisation entwickelt , also steht hoffentlich eine Community dahinter. Es wurde auch vor relativ kurzer Zeit (24. November 2011) veröffentlicht.

Update: Siehe das neue GEKKO-Paket , das wir gerade veröffentlicht haben.

APM Python ist eine kostenlose Optimierungs-Toolbox mit Schnittstellen zu APOPT, BPOPT, IPOPT und anderen Solvern. Es stellt den Lösern erste (Jacobian) und zweite (Hessian) Informationen zur Verfügung und bietet eine optionale Webschnittstelle zum Anzeigen der Ergebnisse. Der APM Python-Client wird mit pip installiert:

 pip install APMonitor

Es kann auch in einem Python-Skript installiert werden mit:

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

Wir haben einige Benchmark-Tests durchgeführt und festgestellt, dass die Kombination von APOPT (Active-Set-Methode) und IPOPT (Interior-Point-Methode) einen großen Prozentsatz der Benchmark-Probleme lösen kann. Es gibt eine Reihe von Beispielproblemen, die in der ZIP-Downloaddatei enthalten sind. Das, mit dem Sie wahrscheinlich beginnen möchten, ist das Hock Schittkowski # 71-Problem. Es ist das einfachste Beispiel und zeigt, wie eingeschränkte Optimierungsprobleme gelöst werden können.

Es gibt eine Browser-Oberfläche und eine API für Python / MATLAB. Die API für Python ist ein einzelnes Skript (apm.py), das auf der apmonitor.com-Homepage zum Download zur Verfügung steht. Sobald das Skript in einen Python-Code geladen wurde, können folgende Probleme gelöst werden:

• Nichtlineare Gleichungen
• Gemischte ganzzahlige nichtlineare Programmierung
• Differential- und algebraische Gleichungen
• Modell mit kleinsten Quadraten
• Schätzung des Bewegungshorizonts
• Vorhersagesteuerung nach nichtlinearem Modell
• usw.

Für den neuen Benutzer verfügt die APM Python-Software über ein Google Groups-Forum, in dem ein Benutzer Fragen stellen kann. Es gibt Webinare, die Optimierungsprobleme in der Betriebsforschung und im Engineering aufzeigen.

Unten sehen Sie ein Beispiel für ein Optimierungsproblem (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

Das Optimierungsproblem wird mit dem folgenden Python-Skript gelöst:

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 ist ein kostenloser Webdienst zur Optimierung. Die Optimierungsprobleme werden auf Remoteservern behoben und die Ergebnisse an das lokale Python-Skript zurückgegeben. Ein lokaler APMonitor-Server kann ebenfalls heruntergeladen werden, sodass keine Internetverbindung erforderlich ist ( Download-Server ). Wir haben kürzlich die Unterstützung für Parallelverarbeitung für MATLAB und Python hinzugefügt. Das Python-Modul ist mit Python 2.7 oder Python 3+ kompatibel.

Obwohl dies Ihre Frage nicht vollständig beantwortet, erstelle ich ein Python-Paket für nichtlineare Programmierung mit dem Namen NLPy. Die neueste Version kann von https://github.com/dpo/nlpy abgerufen werden

Ich muss betonen, dass NLPy für die Forschung geeignet ist und die enthaltenen Löser keineswegs so robust sind wie erfahrene Codes wie IPOPT. Darüber hinaus verlangen sie derzeit die Bereitstellung von Jakobinern. Abgesehen davon besteht der Sinn von NLPy darin, die Tools bereitzustellen, die Forscher benötigen, um benutzerdefinierte Löser zusammenzustellen, wenn dies erforderlich ist. Ich würde mich auf jeden Fall freuen, wenn Sie Ihre Kommentare offline hören, wenn Sie es versuchen. Möglicherweise sind auch die zugehörigen Pakete https://github.com/dpo/pykrylov und https://github.com/dpo/pyorder hilfreich. Derzeit fehlt definitiv die Dokumentation von NLPy. Die anderen beiden sollten vernünftig sein.

pyomo ist eine vollständige GAMS / AMPL-ähnliche Modellierungsumgebung zur Optimierung in Python. Es ist extrem leistungsfähig, verfügt über Schnittstellen zu allen von AMPL unterstützten Solvern und generiert Jacobianer usw. automatisch. Da es jedoch in einer "virtuellen Python-Umgebung" ausgeführt wird, ist es möglicherweise nicht einfach, es mit vorhandenem Code zu verknüpfen.

Wir haben kürzlich (2018) das GEKKO Python-Paket veröffentlichtfür nichtlineare Programmierung mit Solvern wie IPOPT, APOPT, BPOPT, MINOS und SNOPT mit aktiven Mengen- und Innenpunktmethoden. Eines der Probleme bei der Verwendung dieser Solver besteht darin, dass Sie normalerweise mindestens erste Derivate und optional zweite Derivate bereitstellen müssen. Es gibt mehrere nette Modellierungssprachen, die dies für Sie tun können, wie bei anderen Antworten erwähnt. GEKKO kompiliert die Gleichungen in Byte-Code, so dass Sie das Modell hinsichtlich der Geschwindigkeit in Fortran oder C ++ geschrieben haben. Durch die automatische Differenzierung werden die 1. und 2. Ableitung in spärlicher Form für die gradientenbasierten Löser bereitgestellt. Wir haben GEKKO für optimale Steuerungsprobleme entwickelt, aber es kann auch ähnliche Probleme wie fmincon lösen. Im Folgenden finden Sie ein kurzes Beispiel für ein nichtlineares Programmierproblem mit Einschränkungen für Gleichheit und Ungleichheit. Zuerst Du'

pip install gekko

Das Hock-Schittkowski-Problem Nr. 71 ist nachstehend als Beispiel für eine objektive Funktion, eine Ungleichheitsbedingung, eine Gleichheitsbedingung und vier Variablen mit oberen und unteren Schranken dargestellt.

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 funktioniert auf allen Plattformen (Windows-, MacOS-, Linux-, ARM-Prozessoren) und mit Python 2.7 und 3+. Eine vollständig lokale Option ist ohne Internetverbindung verfügbar, indem die Option "remote = False" festgelegt wird. Die lokale Option ist derzeit nur für Windows verfügbar und wir arbeiten an anderen Versionen wie Linux-, MacOS- und ARM-Prozessoren, die lokal ohne Internetverbindung ausgeführt werden können. Die lokale Version enthält nur kostenlose Löser, für die keine Lizenz erforderlich ist. Standardmäßig wird das Problem an einen öffentlichen Server gesendet, auf dem die Lösung berechnet und an Python zurückgegeben wird.

Obwohl es in dieser Frage speziell um das Lösen nichtlinearer Programmierung in Python geht, werde ich auch einige andere Arten von Problemen hervorheben, die GEKKO lösen kann, sowie einige Ressourcen für die Lernoptimierung. GEKKO löst auch algebraische Gleichungen mit gemischten Ganzzahlen und Differentialen und verfügt über mehrere vorprogrammierte Objekte für erweiterte Steuerungen (ähnlich wie DMC, RMPCT usw.). Die Betriebsmodi umfassen Datenabgleich, Echtzeitoptimierung, dynamische Simulation und nichtlineare prädiktive Steuerung.

Ich unterrichte zwei Kurse zum Thema Optimierung ( Designoptimierung und dynamische Optimierung ) und habe das Kursmaterial online gestellt. Der dynamische Optimierungskurs wird jedes Jahr ab Januar angeboten und wir verwenden das GEKKO Python-Paket (und MATLAB) für den Kurs. GEKKO ist eine Erweiterung der APMonitor Optimization Suite, hat jedoch die Modellierung und Lösungsvisualisierung direkt in Python integriert. APMonitor- und GEKKO-Referenzen geben ein Beispiel für die Arten von Anwendungen, die mit diesem Paket gelöst werden können. GEKKO wurde im Rahmen des National Science Foundation Research Grant # 1547110 entwickelt .

Was ist mit scipy.fmin_slsqp?

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

PyGMO enthält mehrere Solver, die dieselbe Schnittstelle zu ihnen bereitstellen. IPOPT und scipy slsqp sind enthalten, falls Sie den Code kompilieren und den Code eines Drittanbieters unabhängig herunterladen / installieren.

Als Bonus wird die parallele Verwendung des Solvers durch die Archipelklasse sehr einfach (Multistart) gemacht!

Es gibt cvxmod , einen Python-Wrapper für Stephen Boyds Software zur konvexen Optimierung. Es ist Teil des Sage- Pakets.

fmincon kann jetzt von Python aus über das OpenOpt-Framework verwendet werden, optional mit automatischer Differenzierung mit hoher Dichte / geringer Dichte durch FuncDesigner http://openopt.org/fmincon

$\to$ $\to$

Ist Beckenhüpfen über Scipy für Ihre Bedürfnisse ausreichend? Wenn eine lokale und keine globale Minute zurückgegeben wird, können Sie die Anzahl der Iterationen ändern und / oder Begrenzungen anwenden.

Wie wäre es mit CMA-ES? Es hat Python-Bindungen und ist gut für nicht konvexe, nichtlineare Optimierungsprobleme geeignet. Ich habe es ziemlich oft verwendet: https://www.lri.fr/~hansen/cmaesintro.html

Installation durch Rohrleitung:

pip install cma

Hier ist ein Beispielcode von ihrer Website:

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

Da MATLAB einen JIT-Compiler hat, während CPython dies noch nicht tut (zumindest bis pypy volle Numpy-Unterstützung bekommt). Anscheinend möchten Sie einen freien Löser, der die kommerziell hergestellten übertrifft fmincon. Ist es nicht zu viel?

IIRC unter den kommerziellen NLP-Solvern hat bisher nur snopt eine Python-API bereitgestellt (obwohl sie ziemlich hässlich ist).

Welche OpenOpt-Löser haben Sie ausprobiert? Wie viele Variablen und Einschränkungen haben Sie in Ihrer nicht konvexen Aufgabe?

Sie können IPOPT über die OpenOpt / Funcdesigner-API testen, ohne es auf dem OpenOpt Sage-Server zu installieren (achten Sie auf das Bild "Wechsel von Salbei zu Python").

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

Bei globalen Problemen können Sie sich für http://openopt.org/interalg und andere globale openopt-Löser (http://openopt.org/GLP) interessieren. Für die lokale Optimierung bietet openopt auch verschiedene Löser: http://openopt.org / NLP

An dieser Stelle ist zu erwähnen, dass der Google Ceres-Löser tatsächlich ein sehr leistungsfähiger nichtlinearer Optimierer ist, der in vielen Projekten verwendet wird.

Es gibt auch einen Python-Wrapper, der hier verfügbar ist: https://github.com/rll/cyres

KNITRO verfügt unter anderem über Python- und MATLAB-Schnittstellen. Stellen Sie sich das als FMINCON-Ersatz vor, aber viel leistungsfähiger und teurer. https://www.artelys.com/de/optimization-tools/knitro#doc-tab .

Ich bin ein Benutzer von KNITRO, aber nicht anderweitig mit dem Produkt verbunden.