Welche Klassen mathematischer Programme können in polynomialer Zeit genau oder ungefähr gelöst werden?

Ich bin ziemlich verwirrt von der Literatur zur kontinuierlichen Optimierung und der TCS-Literatur darüber, welche Arten von (kontinuierlichen) mathematischen Programmen (MPs) effizient gelöst werden können und welche nicht. Die Community für kontinuierliche Optimierung scheint zu behaupten, dass alle konvexen Programme effizient gelöst werden können, aber ich glaube, dass ihre Definition von "effizient" nicht mit der TCS-Definition übereinstimmt.

Diese Frage hat mich in den letzten Jahren sehr beschäftigt, und ich kann scheinbar keine klare Antwort darauf finden. Ich hoffe, Sie haben mir dabei geholfen, dieses Problem ein für alle Mal zu lösen: Welche Klassen von Abgeordneten lassen sich in der Polynomzeit genau und auf welche Weise lösen? und was ist darüber bekannt, wie man die optimale Lösung von MPs approximiert, die wir in polynomialer Zeit nicht genau lösen können?

Im Folgenden gebe ich eine unvollständige Antwort auf diese Frage, die an einigen Stellen möglicherweise auch falsch ist. Ich hoffe, Sie können mich an den Stellen überprüfen und korrigieren, an denen ich falsch liege. Es gibt auch einige Fragen an, die ich nicht beantworten kann.

Wir alle wissen, dass die lineare Programmierung in Polynomzeit exakt gelöst werden kann, indem die Ellipsoidmethode oder eine Innenpunktmethode ausgeführt wird und anschließend eine Rundungsprozedur ausgeführt wird. Die lineare Programmierung kann sogar zeitpolynomisch in der Anzahl der Variablen gelöst werden, wenn eine Familie von LPs mit einer sehr großen Anzahl linearer Beschränkungen konfrontiert ist, solange man ein "Trennungsorakel" dafür bereitstellen kann: ein Algorithmus, der einen bestimmten Punkt hat bestimmt entweder, ob dieser Punkt machbar ist, oder gibt eine Hyperebene aus, die den Punkt vom Polyeder der machbaren Punkte trennt. In ähnlicher Weise kann eine lineare Programmierung in Zeitpolynomen in Bezug auf die Anzahl der Einschränkungen erfolgen, wenn eine Familie von LPs mit einer sehr großen Anzahl von Variablen konfrontiert wird, wenn man einen Trennungsalgorithmus für die Duals dieser LPs bereitstellt.

Die Ellipsoidmethode ist auch in der Lage, quadratische Programme in Polynomzeit zu lösen, falls die Matrix in der Zielfunktion positiv (semi?) Bestimmt ist. Ich vermute, dass wir dies mit dem Trennungs-Orakel-Trick in einigen Fällen auch tun können, wenn wir mit einer unglaublichen Anzahl von Einschränkungen zu tun haben. Ist das wahr?

In letzter Zeit hat Semidefinite Programming (SDP) in der TCS-Community eine große Popularität erlangt. Man kann sie mit der Innenpunktmethode oder der Ellipsoidmethode bis zu einer willkürlichen Genauigkeit lösen. Ich denke, SDPs können nicht exakt gelöst werden, da die Quadratwurzeln nicht exakt berechnet werden können. (?) Wäre es dann richtig, wenn ich sage, dass es ein FPTAS für SDP gibt? Ich habe das nirgends angegeben gesehen, also ist das wahrscheinlich nicht richtig. Aber wieso?

Wir können LPs und SDPs exakt und mit beliebiger Genauigkeit lösen. Was ist mit anderen Klassen von konischen Programmen? Können wir mit der Ellipsoidmethode Kegelprogramme zweiter Ordnung mit beliebiger Genauigkeit lösen? Ich weiß es nicht.

Bei welchen MP-Klassen können wir die Ellipsoidmethode anwenden? Welche Eigenschaften muss ein solcher MP erfüllen, damit eine Antwort mit beliebiger Genauigkeit gegeben werden kann, und welche zusätzlichen Eigenschaften benötigen wir, um eine exakte Lösung in Polynomzeit zu erhalten? Gleiche Fragen für Innenpunktmethoden.

Oh, und schließlich, was veranlasst kontinuierliche Optimierer zu sagen, dass konvexe Programme effizient gelöst werden können? Stimmt es, dass eine beliebig genaue Antwort auf ein konvexes Programm in polynomialer Zeit gefunden werden kann? Ich glaube nicht, also in welchen Aspekten unterscheidet sich ihre Definition von "effizient" von unserer?

Jeder Beitrag wird geschätzt! Danke im Voraus.

Ich kann diesen Teil beantworten:

Wäre es dann richtig, wenn ich sage, dass es ein FPTAS für SDP gibt? Ich habe das nirgends angegeben gesehen, also ist das wahrscheinlich nicht richtig. Aber wieso?

Die Aussage ist richtig, aber wir sehen sie nicht oft, weil eine stärkere Aussage gilt und wichtiger ist als diese schwächere Aussage.

Ein FPTAS ist ein Polynom-Zeit-Algorithmus, der bei gegebenem Problem und einem Genauigkeitsparameter 1 ^k eine (1 + 1 / k ) -approximale Lösung ausgibt .

Für SDP liefern die Ellipsoidmethode und die Innenpunktmethode jedoch Polynomzeitalgorithmen, die bei gegebenem Problem und einem Genauigkeitsparameter 1 ^k eine (1 + 2 ^{- k} ) -approximale Lösung ausgeben . Beachten Sie, dass der Approximationsfaktor viel besser ist als für ein FPTAS erforderlich.

Ich weiß nicht, ob alle konvexen Probleme in P sind, aber ich kann eine verwandte Frage beantworten: Nichtkonvexe Optimierung ist NP-schwer. Siehe "Quadratische Programmierung mit einem negativen Eigenwert ist NP-hart" .