Lösen von semidefiniten Programmen in Polynomialzeit

17

Wir wissen, dass lineare Programme (LP) mit der Ellipsoidmethode oder einer Innenpunktmethode wie dem Karmarkar-Algorithmus genau in Polynomzeit gelöst werden können. Einige LPs mit einer überpolynomiellen (exponentiellen) Anzahl von Variablen / Nebenbedingungen können auch in Polynomzeit gelöst werden, vorausgesetzt, wir können ein Polynom-Zeittrennungs-Orakel für sie entwerfen.

Was ist mit semidefiniten Programmen (SDP)? Welche Klassen von SDPs können in der Polynomzeit genau gelöst werden? Wenn ein SDP nicht genau gelöst werden kann, können wir dann immer ein FPTAS / PTAS entwerfen, um es zu lösen? Unter welchen technischen Bedingungen kann dies durchgeführt werden? Können wir ein SDP mit einer exponentiellen Anzahl von Variablen / Nebenbedingungen in Polynomzeit lösen, wenn wir ein Polynom-Zeittrennungs-Orakel dafür entwerfen können?

Können wir die SDPs, die bei kombinatorischen Optimierungsproblemen (MAX-CUT, Graph Coloring) auftreten, effizient lösen? Wenn wir nur innerhalb eines Faktors lösen können , hat dies dann keine Auswirkung auf Algorithmen zur Approximation konstanter Faktoren (wie 0,878 für den Goemans-Williamson MAX-CUT-Algorithmus)?1+ϵ

Jeder gute Hinweis auf diese wird sehr geschätzt.

linear-programming semidefinite-programming convex-optimization Arindam Pal
quelle
3
Tatsächlich funktioniert die Methode für die konvexe Programmierung im Allgemeinen
Suresh Venkat
8
Es gibt mindestens zwei Gründe, warum Sie eine allgemeine SDP in Polynomialzeit nicht lösen können. (1) Es gibt SDPs, deren Lösung exponentiell groß ist. (2) SDPs können das Problem der Summe der Quadratwurzeln codieren, von dem nicht bekannt ist, dass es polynomiell zeitlösbar ist.
Robin Kothari
2
ϵ1/ϵ
8
@SureshVenkat: Angenommen, wir haben eine 2x2-Matrix mit Einträgen [ab; CD]. Setzen Sie voraus, dass dies positiv semidefinit und d = 1 ist. Dies bedeutet b = c und a> = b ^ 2. B ist also die obere Grenze der Quadratwurzel von a. Jetzt können wir die Summe mehrerer solcher b maximieren. Der optimale Wert ist die Summe der Quadratwurzeln der jeweiligen As.
Robin Kothari
2
Es ist nicht multiplikativ, sondern additiv. Auch en.wikipedia.org/wiki/Semidefinite_programming#Algorithms
Suresh Venkat

Antworten:

16

Die Ellipsoidmethode und die Innenpunktmethode können erweitert werden, um auch SDPs zu lösen. Sie können für Details auf Standardtexte zu SDPs verweisen. Hier ist eins:

Semidefinite Programmierung . Vandenberge und Stephen Boyd, 1996.

Jagadisch
quelle
Schöne Referenz Jagadisch.
Arindam Pal
Nizza Hinweis auch! Vielen Dank! Haben Sie sich gefragt, wann Sie SDP mit einem Polynomialzeitalgorithmus lösen? Lösen sich die Algorithmen genau oder ungefähr für die optimale Lösung?
Tim