Was sind die Vor- und Nachteile der Innenpunktmethode gegenüber der Simplexmethode für die lineare Optimierung?

Nach meinem Verständnis kann, da eine Lösung für ein lineares Programm immer an einem Scheitelpunkt seiner polyedrischen realisierbaren Menge auftritt (wenn eine Lösung existiert und der optimale Zielfunktionswert unter der Annahme eines Minimierungsproblems von unten begrenzt ist), wie eine Suche durch die Innere der machbaren Region besser sein? Konvergiert es schneller? Unter welchen Umständen wäre es vorteilhaft, die Simplex-Methode gegenüber der Innenpunktmethode zu verwenden? Ist einer in einem Code einfacher zu implementieren als der andere?

convex-optimization linear-programming Paul
quelle

Eine Ihrer Aussagen ist falsch. Die Lösung eines konvexen Optimierungsproblems tritt NICHT immer an der Grenze auf. Nehmen wir zum Beispiel , wobei die optimale Lösung bei

auftritt , was sich im Inneren des realisierbaren Bereichs befindet. Außerhalb der linearen Programmierung bezieht sich die Simplex-Methode im Allgemeinen auf die Nelder-Mead-Simplex-Methode, die möglicherweise nicht einmal zu einer optimalen Lösung mit Abmessungen größer als 1 konvergiert. Diese Methode wird für die konvexe Programmierung nicht empfohlen. Bitte bearbeiten Sie Ihre Frage für Klarheit und Richtigkeit.

min_{x \in [- 1, 1]} x^{2}

$\min_{x \in [-1, 1]} x^{2}$

x = 0

$x = 0$

Geoff Oxberry

Wäre es sinnvoller, "lineare Optimierung" statt "konvexe Optimierung" zu sagen?

Paul

Ja, dann ist Ihre Aussage richtig. Vielen Dank, dass Sie Ihre Frage bearbeitet haben.

Geoff Oxberry

Das Problem bei der Simplex-Methode ist, dass sie nicht auf nichtlineare Probleme, dh die Mehrzahl der Probleme der realen Welt, verallgemeinert werden kann.

Antworten:

Aufgrund persönlicher Erfahrungen würde ich sagen, dass Simplex-Methoden nur unwesentlich einfacher zu implementieren sind als Interior-Point-Methoden, basierend auf persönlicher Erfahrung aus der Implementierung sowohl von Primal-Simplex- als auch von Basic-Interior-Point-Methoden in MATLAB im Rahmen einer linearen Programmierklasse . Die Haupthindernisse bei Primal Simplex sind die korrekte Implementierung von Phase I und Phase II sowie die korrekte Implementierung einer Antiradfahrregel. Die Haupthindernisse bei der Implementierung einer Innenpunktmethode für die lineare Programmierung sind in der Regel die korrekte Implementierung der iterativen Methode und die entsprechende Skalierung des Barriereparameters.

Eine ausführlichere Beschreibung der Vor- und Nachteile der einzelnen Algorithmen finden Sie in einem Lehrbuch zur linearen Programmierung, z. B. Einführung in die lineare Optimierung von Bertsimas und Tsitsiklis. ( Haftungsausschluss: Ich habe die lineare Programmierung aus diesem Lehrbuch gelernt und habe die lineare Programmierung am MIT von Bertsimas 'Frau übernommen.) Hier sind einige der Grundlagen:

Vorteile von Simplex:

Gegeben Entscheidungsvariablen, gewöhnlich konvergiert in Operationen mit schwenkt. $n$ $O(n)$ $O(n)$
Nützt die Geometrie des Problems aus: besucht Scheitelpunkte einer möglichen Menge und prüft jeden besuchten Scheitelpunkt auf Optimalität. (Bei Primal Simplex können die reduzierten Kosten für diese Prüfung verwendet werden.)
Gut für kleine Probleme.

Nachteile von Simplex:

Mit Entscheidungsvariablen können Sie immer eine Probleminstanz finden, bei der der Algorithmus -Operationen und Pivots benötigt, um eine Lösung zu finden. $n$ $O(2^{n})$
Nicht so toll für große Probleme, da Schwenkvorgänge teuer werden. Schnittflächenalgorithmen oder Algorithmen zur verzögerten Spaltengenerierung wie Dantzig-Wolfe können diesen Mangel manchmal ausgleichen.

Vorteile der Innenpunktmethoden:

Haben Sie eine asymptotische Polynomzeitkomplexität von , wobei die Anzahl der in den Algorithmus eingegebenen Bits ist. $O(n^{3.5}L^2\log{L}\log\log{L})$ $L$
Besser für große, spärliche Probleme, da die für den Algorithmus erforderliche lineare Algebra schneller ist.

Nachteile der inneren Punktmethoden:

Es ist nicht so intuitiv befriedigend, weil Sie Recht haben. Diese Methoden besuchen keine Eckpunkte. Sie wandern durch die Innenregion und suchen nach einer Lösung, wenn sie erfolgreich sind.
Bei kleinen Problemen ist Simplex wahrscheinlich schneller. (Sie können pathologische Fälle wie den Klee-Minty-Würfel konstruieren.)

Geoff Oxberry
quelle

Eine gute Zusammenfassung. Tatsächlich scheint Klee-Minty so konzipiert zu sein, dass Simplex-LP-Methoden verwechselt werden ...

@JM Ja, genau darum geht es - es handelt sich um eine explizite Konstruktion, die zeigt, dass Simplex-Methoden nicht polynomisch sind (obwohl es Varianten gibt, die interne Punktmethoden zum Weinen bringen).

Christian Clason

Vielen Dank für diesen informativen Beitrag. Ich frage mich, wie viele Variablen das Problem groß machen? Dutzende? Hunderte? Tausende?

KjMag

Der Klee-Minty-Würfel läuft im OpenSource-Solver GLPK 4.65 simplex in <0,1 Sekunden . (Die Werte in und führen dazu, dass sich viele Löser bei D = 100 schlecht verhalten, aber das ist etwas anderes.) Gibt es überhaupt Probleme, für die die Simplex-Methode langsam ausgeführt wird, sagen wir spärlich mit <1M Nonzeros?

5^{D}

$5^D$

A

$A$

x^{*}

$x^*$

Denis

Die Antwort ist einfach. Sie beide (Simplex- und Innenpunktmethode) sind aus algorithmischer Sicht ein ausgereiftes Feld. Sie arbeiten beide sehr gut in der Praxis. Der gute Ruf von IPM (Interior Point Methods) beruht auf seiner Polynomkomplexität im ungünstigsten Fall. Bei Simplex mit kombinatorischer Komplexität ist dies nicht der Fall. Dennoch kommen kombinatorische lineare Programme in der Praxis so gut wie nie vor. Bei sehr großen Problemen scheint IP etwas schneller zu sein, ist aber in der Regel nicht erforderlich. Meiner Meinung nach kann IP leicht zu verstehen und zu implementieren sein, aber sicherlich kann jemand anderes anderer Meinung sein, und das ist in Ordnung. Wenn die Lösung in LP eindeutig ist, befindet sie sich definitiv in einem Scheitelpunkt (sowohl IP als auch Simplex eignen sich auch hier gut). Die Lösung kann sich auch auf einer Fläche des Polyeders oder auf einer Kante befinden. Der benachbarte Scheitelpunkt ist (oder sind Scheitelpunkte) ebenfalls eine Lösung (wiederum sind sowohl IP als auch Simplex gut geeignet). Sie sind also ziemlich gleich.

Carlos Ramirez
quelle

Mir ist klar, dass mein Beispiel kein lineares Programm war. Wenn Sie sich den Revisionsverlauf ansehen, wurde in einer früheren Version dieser Frage gefragt, ob die Simplex-Methode und die Innenpunktmethode für konvexe Optimierungsprobleme verglichen werden sollen. Ich gab ein Gegenbeispiel, um die von mir vorgenommenen Änderungen zu rechtfertigen und das Originalplakat zu ermutigen, seine Frage zu korrigieren, was er auch tat.

Geoff Oxberry