Was kann mit semidefiniter Programmierung gelöst werden, was mit linearer Programmierung nicht gelöst werden kann?

9

Ich bin mit linearen Programmen vertraut, da sie Probleme mit linearen Zielfunktionen und linearen Einschränkungen lösen können. Aber was kann semidefinite Programmierung lösen, was lineare Programmierung nicht kann? Ich weiß bereits, dass semidefinite Programme eine Verallgemeinerung linearer Programme sind.

Wie erkennt man ein Problem, das mit semidefiniter Programmierung gelöst werden kann? Was ist ein typisches Problem, für das semidefinite Programmierung verwendet wird und das nicht über lineare Programmierung gelöst werden kann?

Vielen Dank für jede Antwort.

linear-programming convex-optimization semidefinite-programming user11094
quelle
2
Vielleicht können Sie Ihre Frage präzisieren? Immerhin ist die lineare Programmierung vollständig. P.
Kristoffer Arnsfelt Hansen
5
@KristofferArnsfeltHansen Ich frage mich immer wieder, warum die Leute diese Tatsache in ähnlichen Diskussionen immer wieder zur Sprache bringen. Die P-Vollständigkeit ist irrelevant, es sei denn, wir sprechen über die Trennung von P von L oder NC - wenn wir über Polytime sprechen, ist alles in P "P-vollständig". Um eine Antwort auf OP vorzuschlagen: Wenn Sie eine lineare Codierung eines Problems behoben haben (dh als Optimierung einer linearen Funktion über ein Polytop schreiben), ist es durchaus sinnvoll zu fragen, ob ein polysize LP / SDP das Problem lösen kann.
Sasho Nikolov

Antworten:

18

Ein typisches Problem ist MaxCut: Geben Sie einen Schnitt in einem Diagramm aus, der (ungefähr) die Anzahl der geschnittenen Kanten maximiert. Goemans und Williamson zeigten, dass ein SDP den Wert von MaxCut auf einen Faktor von mindestens 0,878 annähert. Kürzlich haben Chan, Lee, Raghavendra und Steurer gezeigt, dass für eine natürliche lineare Codierung des MaxCut-Problems alle LPs mit Polynomgröße eine Annäherung von nicht besser als 0,5 erreichen.

Es ist schwer zu sagen, welche Probleme normalerweise von einem SDP profitieren. Ein systematischer Ansatz zur Konstruktion von SDP-Relaxationen sind Hierarchien, von denen die Lasserre-Hierarchie die mächtigste ist: Eine schöne Einführung finden Sie in Rothvoß's Umfrage . Inzwischen gibt es zu viele Beispiele für Erfolge von SDPs bei der Optimierung, um sie aufzulisten. Außerdem hat Raghavendra gezeigt, dass ein bestimmtes SDP die beste Annäherung an alle MaxCSP-Probleme bietet, wenn die Vermutung von Unique Games wahr ist.

Überprüfen Sie die Bücher von Gaertner und Matousek , Kapitel 6 und 13 von Willimson und Shmoys 'Buch , Lovasz' Umfrage .

Sasho Nikolov
quelle
12

Bei vielen kombinatorischen Optimierungsproblemen (zum Beispiel Max-Cut) ergibt die semidefinite Programmierung viel stärkere Relaxationen als die LP-Relaxation von IP-Formulierungen. Dies ermöglicht den Entwurf von Approximationsalgorithmen und von exakten Algorithmen, die aufgrund der besseren Qualität der Grenzen effizienter sind als ihre linearen Gegenstücke. Beispiele finden Sie in Christoph Helmbergs Habilitationsarbeit , dieser Umfrage und dieser Kursseite .

Eine weitere neue Folge spektakulärer Ergebnisse, die semidefinite Programmierung verwenden, ist die Anwendung von Razborovs Flaggenalgebren , um Ergebnisse zu Problemen vom Typ Turan zu beweisen (siehe diese Umfrage und das flagmatische Projekt ).

Thomas Kalinowski
quelle