Softwarepaket für eingeschränkte Optimierung?

21

Ich versuche, ein Problem der eingeschränkten Optimierung zu lösen, bei dem ich die Grenzen einiger Variablen kenne (insbesondere eine umrahmte Einschränkung).

\arg min_{u} f (u, x)

$\arg \min_u f(u,x)$

unterliegen

c (u, x) = 0

$c(u,x) = 0$

a \leq d (u, x) \leq b

$a \le d(u,x) \le b$

wobei $u$ ein Vektor von Entwurfsvariablen ist, $x$ ein Vektor von Zustandsvariablen ist und $c(u,x)$ eine Gleichheitsbedingung ist (normalerweise eine PDE). Die unteren und oberen Randbedingungen $a$ und $b$ können räumlich variabel sein.

Welche Pakete können mit Systemen dieser Form umgehen?

pde optimization nonlinear-programming Sean Farley
quelle

1

Die bearbeitete Version sieht nicht wie ein Optimierungsproblem aus, bei dem die Box eingeschränkt ist. Ein Optimierungsproblem mit Box-Einschränkungen würde

a \leq u \leq b

$a \leq u \leq b$ als Einschränkung haben. Sollst

u

$u$ eine Funktion von

x

$x$ ? Ist

c

$c$ linear in

u

$u$ ? Wenn nicht, ist es doppelt differenzierbar? Ist

f

$f$ konvex in

u

$u$ ? Ist es in

doppelt differenzierbar

u

$u$ ? Schließlich bezeichnet

\arg min_{u}

$\arg \min_{u}$ die Menge von Punkten in

u

$u$ bei denen der Minimalwert von

f

$f$ erreicht wird. Wollen Sie damit sagen

min_{u}

$\min_{u}$ statt?

Geoff Oxberry

d (u, x) = u

$d(u,x) = u$ ist ein Sonderfall, aber diese allgemeinere Form ist in der Praxis tatsächlich üblich. Sie können immer zusätzliche Variablen einfügen, wenn Ihre Methode Einschränkungen nur direkt für

u

$u$ . Uns interessiert in der Regel mehr der Wert

u

$u$ bei dem ein Minimum erreicht wird, als der Minimalwert von

f

$f$ . Sean hat das [pde] -Tag hinzugefügt, damit Sie ein wenig Regelmäßigkeit davon haben. Er gab nicht an, ob das System hyperbolisch war oder nicht, also lasst uns nicht annehmen. Nehmen wir nicht an, dass

f

$f$ konvex ist, da dies häufig nicht der

ist.

Jed Brown

Es ist durchaus üblich, dass

f

$f$ eine

L^{1}

$L^1$ oder

W^{1, 1}

$W^{1,1}$ -Regularisierung beinhaltet, daher sollten wir keine zwei Ableitungen annehmen.

Jed Brown

@JedBrown: Das macht Sinn; Es war verwirrend, die erwähnte "Box-Einschränkung" ohne eine explizite Box-Einschränkung zu sehen. Für die Arten von Problemen, von denen Sie sprechen (Entwurfsprobleme, Steuerungsprobleme), ist

u

$u$ definitiv interessanter, aber Optimierungsprobleme werden normalerweise mit der

m i n

$min$ Notation angegeben, und ihre Lösungssätze werden mit der

\arg min

$\arg \min$ Notation beschrieben.

Geoff Oxberry

Es kann nützlich sein, anzugeben, in welcher Sprache / Umgebung Sie die PDEs modellieren. Dies kann die Auswahl der Optimierer einschränken.

Dominique

18

Ich habe mich entschieden, meine Antwort basierend auf einigen Kommentaren radikal zu bearbeiten.

Ich habe TAO nicht benutzt. Aus Durchsicht die Dokumentation, wie es scheint , die einzige Möglichkeit , dass TAO erzwungener Optimierungsprobleme behandeln kann ( mit Ausnahme des Sonderfalls nur Box Einschränkungen) ist das Problem in eine Variationsungleichung mit den konvertieren Karush-Kuhn-Tucker (KKT) Bedingungen , die sind unter der Einschränkungsqualifikation erforderlich (der Typ, den ich normalerweise sehe, ist die Slater-Punkt-Bedingung ) und ausreichend unter der Konvexität des Ziels und der Einschränkungen (allgemeiner Typ 1-Invexität). Wenn $f$ ist nicht konvex, die Variationsungleichungsformulierung unter Verwendung der KKT-Bedingungen entspricht NICHT dem ursprünglichen Optimierungsproblem. Wenn Sie also ein globales Optimum für das Optimierungsproblem wünschen, sollten Sie es nicht als Variationsungleichung ausdrücken. Es ist ohnehin schwierig, ein globales Optimum für die PDE-beschränkte Optimierung zu finden (siehe unten). Vielleicht ist es in Ordnung, dieses Detail zu ignorieren. Angesichts dessen, was Wolfgang gesagt hat, wäre ich skeptisch, TAO einzusetzen. Ich bin bereits skeptisch, weil es keine Methoden zum Lösen nichtlinearer Programme (NLPs) als NLPs implementiert, sondern Variationsungleichungen.

Ich bin kein Experte für PDE-beschränkte Optimierung. Mitarbeiter und Mitarbeiter von mir arbeiten an ODE-beschränkten Optimierungsproblemen. Ich weiß, dass Larry Biegler (und andere) für aufdringliche Formulierungen Kollokationsmethoden verwenden wird, um die PDE zu diskretisieren und sie zu einem sehr großen, spärlichen NLP zu machen, und dann wird er sie mithilfe von Innenpunktmethoden lösen. Um das Problem der globalen Optimalität wirklich zu lösen, müssten Sie auch konvexe Relaxationen erzeugen, aber meines Wissens wird dieser Ansatz nicht gewählt, da Optimierungsprobleme aufgrund von PDE zu so großen NLPs führen, dass es schwierig ist, sie zu lösen globale Optimalität. Ich erwähne diese Details nur, weil die Problemformulierung die Wahl des Lösungspakets stark beeinflusst. Bei nichtintrusiven Formulierungen ergeben wiederholte PDE-Lösungen Gradienteninformationen für Optimierungsalgorithmen.

Einige Personen, die ODE-beschränkte Optimierungsprobleme untersuchen, verwenden einen ähnlichen Ansatz zur Diskretisierung des Problems mithilfe der Kollokation und einer numerischen Methode. Anschließend wird der resultierende NLP gelockert, um eine konvexe Formulierung zu erhalten, die in einem globalen Optimierungsalgorithmus verwendet wird. Ein alternativer Ansatz für die ODE-beschränkte Optimierung besteht darin, das Problem zu lösen und dann die ODE zu diskretisieren. Dies ist der Ansatz, den ich in meinem Labor gewählt habe. Es könnte möglich sein, bestimmte Klassen von Optimierungsproblemen mit PDE-Einschränkungen zu lockern, aber ich kenne keine noch ausstehenden Arbeiten, die an diesem Problem vorgenommen wurden. (Es war einmal ein potentielles Projekt in meinem Labor.)

Entscheidend ist letztendlich nicht die Differenzierbarkeit der ursprünglichen PDE, sondern die Differenzierbarkeit der Diskretisierung in Bezug auf die Entscheidungsvariablen.

Wenn das diskretisierte Problem in Bezug auf die Entscheidungsvariablen doppelt differenzierbar ist, berechnen die folgenden Pakete eine lokale Lösung:

IPOPT ist ein Open Source- Innenpunktlöser, der von Andreas Wächter bei IBM entwickelt wurde. Es ist ein sehr hochwertiger Code. Als Innerer-Punkt-Löser ist es besser für objektive Funktionen mit großen, spärlichen Jacobi-Matrizen und für die PDE-beschränkte Optimierung geeignet
SNOPT ist ein kommerzieller Löser für sequentielle quadratische Programmierung, bei dem es sich ebenfalls um einen hochwertigen Code handelt. Es ist besser für objektive Funktionen mit kleinen, dichten Jacobi-Matrizen, daher würde ich nicht erwarten, dass es für die PDE-beschränkte Optimierung nützlich ist, aber Sie könnten es versuchen.
NLopt ist ein kleiner Open-Source-Code, der von Steven Johnson am MIT geschrieben wurde und grundlegende Implementierungen einer Reihe nichtlinearer Optimierungsalgorithmen enthält. Alle Algorithmen sollten für die Lösung von Problemen mit beschränkten Bedingungen geeignet sein.
fmincon in Matlab implementiert eine Reihe von Algorithmen (einschließlich Innenpunkt- und sequentieller quadratischer Programmierung) für die nichtlineare Optimierung
GAMS und AMPL sind beide kommerzielle Modellierungssprachen zur Formulierung von Optimierungsproblemen und enthalten Schnittstellen zu einer großen Anzahl nichtlinearer Programmierlöser. Ich weiß, dass GAMS eine Testversion hat, die für kleinere Probleme verwendet werden kann. Probleminstanzen können auch zur Lösung an den NEOS-Server gesendet werden.

Es ist jedoch möglich, dass die Diskretisierung in Bezug auf die Entscheidungsvariablen nur einmal differenzierbar ist. In diesem Fall sollten Sie bei der Berechnung einer lokalen Lösung den projizierten steilsten Abstieg oder eine andere Optimierungsmethode erster Ordnung verwenden. Da sich viele Studien auf Probleme konzentrieren, bei denen Methoden zweiter Ordnung verwendet werden können (und wenn Sie sie verwenden können, sind sie aufgrund ihrer überlegenen Konvergenzeigenschaften eine bessere Wahl), konnte ich nicht viele Implementierungen steilster Abstammung finden, die keine Lösungen waren zu Hausaufgabenproblemen. Die GNU Scientific Library hat eine Implementierung, die jedoch nur zu Demonstrationszwecken dient. Sie müssten wahrscheinlich Ihre eigene Implementierung programmieren.

Wenn das Problem nur in Bezug auf die Entscheidungsvariablen kontinuierlich ist, können Sie es lokal mit direkten Methoden lösen. Es gibt eine hervorragende Übersicht über direkte Methoden von Kolda, Lewis und Torczon . Die bekannteste dieser Methoden ist der Nelder-Mead-Simplex-Algorithmus . Es ist nicht garantiert, dass es in mehreren Dimensionen zu einem lokalen Minimum konvergiert, aber es hat trotzdem beträchtlichen praktischen Nutzen gefunden.

Die Wahl des Pakets hängt wirklich von der Sprache ab, die Sie zur Lösung des Problems verwenden möchten. Wenn die Lösung des Problems mit gebundenen Bedingungen nur ein Teil eines Algorithmus ist, den Sie implementieren möchten (oder wenn dies der einzige Schritt in Ihrem Algorithmus ist, in diesem Fall Modellierungssprachen) werden für den Produktionscode praktikabler), die Art und Größe des Problems und wenn Sie Parallelität benötigen.

Geoff Oxberry
quelle

4

Wir haben TAO ausprobiert, fanden es jedoch nicht sehr nützlich für ungleichheitsbezogene Probleme. Außerdem ist es seit mindestens 2003 im Wesentlichen nur im Wartungsmodus und es gibt keine wirklichen neuen Funktionen außer Aktualisierungen zum Nachverfolgen von Änderungen in PETSc, auf denen es basiert.

Wolfgang Bangerth
quelle

3

Eine andere Alternative ist OPT ++ . Es unterstützt lineare und nichtlineare Abhängigkeiten mit einem effizienten nichtlinearen Innenpunktlöser, bietet Kontrolle über die Funktionsgenauigkeit (wenn numerische Differenzierung erforderlich ist), Kontrolle über Schrittgrößen usw. Ich optimiere normalerweise große implizite Funktionen (z. B. FEM), bei denen diese Arten von Kontrollen können nützlich sein.

Barron
quelle

Können Sie erläutern, warum OPT ++ ein gutes Paket ist? Haben Sie (oder Ihre Kollegen) irgendwelche Erfahrungen damit?

Geoff Oxberry

Um es klar auszudrücken, ich habe keinen Grund zu sagen, dass OPT ++ besser ist als alle anderen, die Sie zuvor aufgelistet haben, da ich keine Erfahrung mit diesen habe (obwohl ich einige von ihnen als Lesezeichen zum Auschecken gesetzt habe). Aber ich habe Erfahrung mit OPT ++ und fand es passend für meine Bedürfnisse. Es unterstützt lineare und nichtlineare Abhängigkeiten mit einem effizienten nichtlinearen Innenpunktlöser, bietet Kontrolle über die Funktionsgenauigkeit (wenn numerische Differenzierung erforderlich ist), Kontrolle über Schrittgrößen usw. Ich optimiere normalerweise große implizite Funktionen (z. B. FEM), bei denen diese Arten von Kontrollen können nützlich sein.

Barron

2

@Barron: Das hättest du als erstes in deine Antwort schreiben sollen. :)

JM

2

Wenn das Problem als Komplementaritätsproblem formuliert ist, können Sie TAO (Toolkit for Advanced Optimization) verwenden. Einige der Methoden in TAO, wie z. B. die Methode mit reduziertem Speicherplatz (eine Variante der Methode mit aktivem Satz), sind derzeit als Teil von SNES in PETSc ( SNESVI ) verfügbar .

Jungho Lee
quelle

1

Das MINUTE- Modul von CERNLIB (seit langem auf ROOT portiert ) verwendet eine Transformation für den Eingabebereich , um Box-Einschränkungen in einen Bereich zu rendern, in dem sie ausgeführt werden und somit ohne Sonderfälle (auf Kosten) behandelt werden können von einer gewissen Geschwindigkeit natürlich). $[-\infty,+\infty]$

Ich denke nicht, dass MINUTE gut für Ihre Bedürfnisse geeignet ist, aber die Transformation kann erfolgen, wenn Sie gezwungen sind, den Code ganz oder teilweise selbst zu schreiben.

dmckee
quelle

Diese Transformation sieht fies aus; Kein Wunder, dass es von ein paar Absätzen begleitet wird.

Geoff Oxberry

1

Wie @Geoff Oxberry hervorhob, können Sie mit mehreren Paketen eine lokale Lösung finden. Wenn Sie diese verschiedenen NLP-Löser für ein und dasselbe Problem vergleichen möchten, können Sie RobOptim verwenden .

Obwohl RobOptim ursprünglich mit Blick auf Optimierungsprobleme in der Robotik entwickelt wurde, eignet es sich für alle nichtlinearen Optimierungsprobleme. Es bietet eine einfache C ++ - Schnittstelle mit Plugins für mehrere NLP-Löser (z. B. Ipopt, NAG). Wenn Sie keine Gradienten angeben können, kann die Berechnung der endlichen Differenz automatisch durchgeführt werden.

Es ist Open Source, so dass Sie den Quellcode auf GitHub überprüfen können: https://github.com/roboptim/

Hinweis: Ich bin einer der Entwickler dieses Projekts.

BenC
quelle

1

Sollte darauf hinweisen, dass andere Antworten Löser beschreiben , keine Frameworks. Es ist einfacher, ein akzeptables Framework ( Treiber ) als einen guten Löser zu finden,

Deer Hunter

@DeerHunter Wenn Sie nach einem Löser suchen, um ein bestimmtes Problem zu lösen, ist es oft schwierig, a priori zu wissen, welcher Löser die beste Lösung berechnet und / oder der schnellste ist. Sie sprechen von einem "guten Löser", aber das hängt wirklich davon ab, was Sie lösen: Es gibt keinen einzigen "besten Gesamtlöser". Darüber hinaus sind Solver-APIs in der Regel sehr unterschiedlich. Daher kann die Verwendung eines guten Frameworks, mit dem Sie problemlos von einem Solver zu einem anderen wechseln können, sehr hilfreich sein. Die Frage lautete "Softwarepakete für eingeschränkte Optimierung", und Frameworks fallen ebenfalls in diese Kategorie.

BenC

1

Hier ist eine unvollständige Liste der Optimierungspakete mit eingeschränkter PDE.

Dolfin Adjoint ist Teil von FEniCS FEM:

http://dolfin-adjoint.org/

ROL, MOOCHO, Sundance sind Teile von Trilinos:

https://github.com/trilinos/trilinos/tree/master/packages/rol/

https://github.com/trilinos/trilinos/tree/master/packages/Sundance/

http://trilinos.org/packages/moocho/

PYOMO-Beispiel für die PDE-beschränkte Optimierung:

https://software.sandia.gov/trac/pyomo/browser/pyomo/trunk/examples/dae

Das TAO-Handbuch enthält Beispiele für die Lösung von Optimierungsproblemen mit PDE-Einschränkungen:

http://www.mcs.anl.gov/petsc/petsc-3.5/docs/tao_manual.pdf

denfromufa
quelle

1

Willkommen bei SciComp.SE! Nur einen Link anzugeben (so nützlich es auch sein mag), ist keine wirklich gute Antwort. Siehe meta.stackexchange.com/questions/8231 . Könnten Sie dies etwas näher erläutern (Computersprache, welche Einschränkungen können behandelt werden, welche Methoden sind implementiert usw.)?

Christian Clason

Ich bin mit @ChristianClason einverstanden. Solver für Optimierungssoftware mit PDE-Einschränkungen wurden erheblich weiterentwickelt. Diese Antwort liefert jedoch im Wesentlichen keinen Hintergrund darüber, welche Algorithmen diese Pakete tatsächlich implementieren.

Geoff Oxberry

0

Mit den APM MATLAB- und APM Python- Paketen können große (über 100.000 Variablen) von Differentialalgebraischen Gleichungssystemen mit gemischten Ganzzahlen gelöst werden. Die Software ist als Webdienst für kommerzielle oder akademische Zwecke verfügbar. Wenn Sie ein PDE-System lösen, können Sie es einmal diskretisieren, um es in DAE- oder ODE-Form zu bringen und in die APMonitor-Modellierungssprache zu übertragen. Die Modellierungssprache verwendet die Solver APOPT , BPOPT, IPOPT, SNOPT und MINOS.

John Hedengren
quelle

1

Bitte offenbaren Sie Ihre Zugehörigkeit als APMonitor-Entwickler in diesen und zukünftigen Antworten, in denen Ihre Software erwähnt wird. Weitere Informationen zu unseren Veröffentlichungsrichtlinien finden Sie in den FAQ.

Geoff Oxberry

Geoff, danke für den Tipp. Ich habe 2004 als Doktorand an der University of Texas in Austin mit der Arbeit an der APMonitor-Plattform begonnen. Wir verwenden es jetzt in unserer Forschungsgruppe an der Brigham Young University für die Prozesskontrolle und -optimierung ( apm.byu.edu/prism ) von biologischen, chemischen, Luft- und Raumfahrt- und anderen Anwendungen. Ich stelle es kommerziellen oder akademischen Nutzern frei zur Verfügung.

John Hedengren

Softwarepaket für eingeschränkte Optimierung?

Antworten: