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

77

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.

David Ketcheson
quelle
2
David, das ist jetzt leider eine ganz andere Frage :) Der Unterschied zwischen lokalem Minimum und global ist das Thema einer potenziell unendlichen Anzahl von Doktorarbeiten, und nach dem No-Free-Lunch-Theorem ist jeder Löser, der für ein allgemeines globales Optimierungsproblem geeignet ist, der richtige nachweislich schlecht für einen anderen. Ich könnte vorschlagen, dass Sie mit der Prüfung der Formulierungsoptionen beginnen (Gibt es eine gemischte Ganzzahlform? Gibt es eine konvexe Annäherung?)
Aron Ahmadia
David, Aron macht einen guten Punkt. Die Formulierung ist definitiv der Schlüssel, um numerische Lösungen von nicht konvexen NLPs zu erhalten, geschweige denn, um gute Lösungen schnell zu erhalten. Es kann sich lohnen, alternative Formulierungen in Betracht zu ziehen und dann die Struktur dieser Formulierungen zu verwenden, um Ihre Wahl des Lösers zu leiten. Die Verwendung eines Lösers, der eine beliebige Struktur ausnutzt (z. B. Sparsamkeit, mehrstufige stochastische Programmierung, Verwendung von Einschränkungen zum Erzeugen von Schnitten), die Sie in Ihrem Problem induzieren können, ist der Schlüssel, um gute Lösungen zu erhalten.
Geoff Oxberry
@DavidKetcheson: Da Sie eine Formulierung haben, die Sie verwenden möchten, können Sie zumindest die Eigenschaften Ihrer Formulierung kommentieren? Ist der Jakobianer des Lagrange dicht oder spärlich? Wie viele Variablen hat es ungefähr? Es nützt uns nichts, Software zu empfehlen, die für Ihr Problem ungeeignete Lösungsmethoden implementiert, und nur deshalb wird überhaupt über Formulierungen gesprochen.
Geoff Oxberry
coopr bindet ipopt mit asl: ipopt
denfromufa

Antworten:

32

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.

Aron Ahmadia
quelle
Andreas leistet gute Arbeit, aber sein Löser benötigt auch Jacobi-Matrix-Informationen (oder zumindest Sparsity-Informationen für die Jacobi-Matrix). Wenn Sie sagen, Sie möchten einen Solver, für den keine Jacobi-Matrix erforderlich ist, dann möchten Sie einen Solver, für den Sie die Jacobi-Matrix nicht analytisch bereitstellen müssen (damit eine Berechnung mit endlichen Differenzen ausreicht), oder Sie möchten ein Solver, der überhaupt keine Jacobi-Matrix-Informationen benötigt (was Sie auf ableitungsfreie Optimierungsmethoden beschränken würde)?
Geoff Oxberry
Guter Fang. Ich meine das erstere; Ich habe die Frage aktualisiert.
David Ketcheson
Mit sage.openopt.org konnte ich endlich IPOPT auf mein Problem anwenden . Es ist toll!
David Ketcheson
4
Heute (2017) können Sie IPOPT auch in Python durch Pyomo verwenden . Sie erhalten eine algebrische Modellierungssprache und ein Auto-Diff für das jacobianische und das hessische.
Antonello
@ Antonello der korrigierte Link ist pyomo.org
Moonwalker
37

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.

Geoff Oxberry
quelle
Bitte beachten Sie, dass PaGMO GPL-lizenziert ist
denfromufa
14

APM Python

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.

John Hedengren
quelle
2
John, ich sehe, dass APM Python frei verfügbar ist, aber ich kann nicht anhand des Pakets herausfinden, ob es lokal verwendete Löser enthält oder ob für die Berechnung eine Verbindung zur AP Monitor-Website erforderlich ist. Ich bin gespannt auf welche.
Aron Ahmadia
3
Aron, die MATLAB- oder Python-Skripte erfordern eine Internetverbindung zu den APM-Servern, um die Optimierungsprobleme zu lösen. Dies hat eine Reihe von Vor- und Nachteilen. Positiv zu vermerken ist, dass ein Webservice zur Optimierung die plattformübergreifende Kompatibilität, den freien Zugriff auf einige kommerzielle Löser und für den Benutzer transparente Software-Upgrades ermöglicht. Auf der anderen Seite ist APM nicht so flexibel wie einige Open-Source-Alternativen, sondern wurde für industrielle Anwender entwickelt, die eine schlüsselfertige Lösung für Optimierungsanwendungen bevorzugen.
John Hedengren
@JohnHedengren Ich habe in MATLAB bestimmte Vorberechnungen unter Verwendung einer anderen Bibliothek, um das Optimierungsproblem selbst zu konstruieren. Insbesondere die Einschränkungen betreffen diese externen Aufrufe. Denken Sie, dass APM für diesen Zweck noch geeignet ist?
Gpavanb
Ich denke, der übliche Begriff dafür ist Blackbox-Optimierung.
Gpavanb
@gpavanb Für das APMonitor-Paket müssen die Gleichungen in der Modellierungssprache geschrieben sein. Eine Möglichkeit, externen Code zu laden, besteht darin, ein Objekt zu erstellen, das Residuen und mindestens die analytischen ersten Ableitungen bereitstellt. Wir codieren diese Objekte normalerweise in F90, um die hier aufgeführte Geschwindigkeit zu gewährleisten : apmonitor.com/wiki/index.php/Main/Objects Ich glaube nicht, dass APMonitor die beste Option für eine Anwendung mit Blackbox-Optimierung ist.
John Hedengren
7

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.

Dominique
quelle
7

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.

Hans
quelle
5

GEKKO Python

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 .

John Hedengren
quelle
Könnten Sie Ihre Antwort bearbeiten, um zu erläutern, wie Ihre Software die im Beitrag genannten spezifischen Anforderungen erfüllt? Andernfalls ähnelt dies eher einem pauschalen Werbepost als einer Antwort auf die Frage (und wird wahrscheinlich geschlossen).
Christian Clason
Christian, ich habe die Antwort bearbeitet, um sie spezifischer auf die Frage abzustimmen. Ich habe die zusätzlichen Informationen zu GEKKO und den Online-Kursen an das Ende verschoben, kann sie jedoch bei Bedarf entfernen.
John Hedengren
4

Was ist mit scipy.fmin_slsqp?

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

Alejandro
quelle
1
Danke, aber das ist eine, die ich ausprobiert habe (über OpenOpt, das eine zusätzliche Schnittstelle bietet). Es war nie besser als fmincon / sqp und schlug in vielen Fällen fehl, in denen letzteres erfolgreich war.
David Ketcheson
1
Update: Ich habe es direkt bei SciPy ausprobiert. Es scheitert sogar bei Problemen, bei denen fmincon in wenigen Sekunden durchgehend das globale Optimum finden kann.
David Ketcheson
4

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!

Dario Izzo
quelle
3

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

John D. Cook
quelle
Das OP fragt jedoch nach einem nicht konvexen Optimierungsproblem.
Alejandro
1
Das OP fragt nach einem nicht-konvexen Optimierungsproblem, aber für alle bisher genannten Löser wird nur garantiert, dass sie epsilon-optimale Lösungen für konvexe Optimierungsprobleme ohne zusätzliche Metaheuristiken finden (multistart oder andere stochastische globale Optimierungsalgorithmen, die deterministisch sind, nichtlineare, konvexe Optimierungslöser) oder branch-and-bound-ähnliche Algorithmen (wie branch-and-bound, branch-and-cut und branch-and-reduction), die eine Lockerung der Zielfunktion und der Einschränkungen erfordern. Diese Antwort ist nicht schlechter als die anderen, die am 11. Dezember erwähnt wurden.
Geoff Oxberry
Geoff, wie kann ich cvxmod auf ein nicht konvexes Problem anwenden?
David Ketcheson
Ich habe die Software nicht verwendet, aber theoretisch würden Sie sie wie jeden anderen Konvexlöser verwenden, um lokal optimale Lösungen zu finden, ähnlich wie Sie jetzt fmincon verwenden (das auch ein Konvexlöser ist). Eine Möglichkeit wäre Multistart. Erstellen Sie eine Liste mit Punkten, die als erste Ratschläge für Ihren Konvexlöser verwendet werden sollen. Notieren Sie für jeden als Vermutung verwendeten Punkt die vom Löser zurückgegebene Lösung. Der Punkt, der dem minimalen Zielfunktionswert über alle zurückgegebenen Lösungen entspricht, ist die beste Annäherung an das globale Optimum.
Geoff Oxberry
1
@Geoff: Ja, ich benutze Multistart. CVXMOD akzeptiert nur Probleme, die in Bezug auf disziplinierte konvexe Programmierung formuliert werden können. Allgemeine nichtlineare Programmierprobleme können dies nicht. Wie Sie sagen, könnte ich nach aufeinanderfolgenden konvexen Relaxationen suchen, die sich meinem Problem annähern, aber das ganze Ziel ist, dass ich weniger Arbeit mache.
David Ketcheson
3

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

user871016
quelle
Dies scheint nicht mehr zu existieren.
Feetwet
3





denis
quelle
Ab Release 2014b wird dies nun direkt von Matlab unterstützt. Siehe mathworks.de/help/matlab/matlab-engine-for-python.html
Christian Clason,
@Christian Clason, das scheint überhaupt nichts mit Matlab zu tun zu haben? wie Python-Matlab-Bridge. (Ich habe es aber nicht benutzt.)
Denis
Nicht direkt (es scheint eine benutzerdefinierte Matlab-Array-Klasse zu haben), aber es gibt eine Möglichkeit, zwischen dem und Numpy zu konvertieren. Durch das Kopieren von Daten entsteht natürlich ein gewisser Overhead, aber bei den vom OP erwähnten Problemgrößen ist dies wahrscheinlich weniger ein Problem. (Habe es selbst nicht benutzt; dachte nur, ich würde auf die Option hinweisen.)
Christian Clason
3

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.

MPath
quelle
2

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
Brian
quelle
Dieser Optimierer ist weit davon entfernt, was das OP verlangt. Beispielsweise gibt es keine eindeutige Methode, wie mit CMA-ES mit Gleichheits- oder Ungleichheitsbeschränkungen umgegangen werden kann.
ares
1

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").

10300(x0.1)2+10300(y0.2)2(x,y)=(1,1)

Dmitrey
quelle
2
Wenn Sie sorgfältig lesen, bitte ich Sie nur um etwas mit einer ähnlichen Robustheit wie fmincon. Es muss nicht besser sein, und es kann sogar langsamer sein.
David Ketcheson
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

asd
quelle
Ja, ich habe einige davon ausprobiert, aber keine hat mit fmincon gerechnet.
David Ketcheson
1

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

Tolga Birdal
quelle
Ist es nicht Levenbeg-Marquardt? Das ist zwar nett, aber weit davon entfernt, was die OP will
denis
Ceres ist zwar ein wirklich guter Löser, unterstützt jedoch überhaupt keine Gleichheitsbeschränkungen und unterstützt nur Ungleichheitsbeschränkungen als Ober- / Untergrenze der Parameter (ab der aktuellen Version 1.12).
Orzechow