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

31

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.

Bart
quelle
6
Der Titel dieser Frage ist viel zu weit gefasst; es scheint, dass Sie wirklich wissen möchten, ob konvexe Programme wirklich in polynomialer Zeit gelöst werden können.
Peter Shor
Abgeordnet. Bart, kannst du die Dinge vielleicht in bestimmte Fragen aufteilen?
Suresh Venkat
Peter und Suresh, danke für diese Vorschläge. Aus dem, was ich geschrieben habe, soll hervorgehen, dass mich nicht nur die Frage interessiert, ob konvexe Programme in Poly-Time gelöst oder angenähert werden können. Ich interessiere mich grundsätzlich für die Grenzen der Ellipsoid- und Innenpunktmethode und hoffe, dass jemand genau weiß, mit welchen Klassen von Abgeordneten er effizient arbeitet. Ich frage dies, weil die aktuelle Literatur darüber (für mich) nicht klar ist.
Bart
Persönlich denke ich, dass es gut wäre, einen schönen Überblick darüber an einem Ort zu haben (als Antwort auf diese Stapelwechsel-Frage). Auch für mich scheint das eine ganz schlüssige Frage zu sein. Da ich jedoch neu in Stackexchannge bin, bin ich mit der Kultur und Ethik hier nicht vertraut. Wenn Sie darauf bestehen, werde ich versuchen, herauszufinden, wie diese Frage in mehrere kleinere Fragen aufgeteilt werden kann.
Bart
1
Ich denke, der Umfang dieser Frage ist viel zu weit gefasst, um eine Antwort zu haben. Die Grenzen der Ellipsoid- und Innenpunktmethoden wären eine gute Frage, und was für konvexe Programme getan werden kann, ist eine gute Frage. Wenn Sie jedoch weder den Algorithmus noch den Programmtyp angeben, fragen Sie sich im Grunde für eine Zusammenfassung des gesamten Bereichs der kontinuierlichen Optimierung in Ihrer Antwort, und das ist so ziemlich unmöglich. Es ist kein kleines Feld. Wenn Sie Ihre Frage jedoch so lassen, wie sie ist, ist es durchaus möglich, dass Sie eine weitere gute Teilantwort erhalten.
Peter Shor

Antworten:

18

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.

Tsuyoshi Ito
quelle
Dies erfordert etwas mehr Sorgfalt, da die Ellipsoidmethode und die Innenpunktmethode zusätzliche Bedingungen benötigen, um in Polynomzeit zu laufen.
Yoshio Okamoto
Danke dafür, Tsuyoshi! Yoshio, könntest du klarstellen, was du damit meinst? Meinen Sie wirklich, dass für das jeweilige SDP Bedingungen erforderlich sind, da sich das SDP ansonsten in Poly-Time nicht so approximieren lässt? Dies ist für mich in diesem Fall eine Überraschung, und ich wäre daran interessiert, über diese Bedingungen Bescheid zu wissen. Vielen Dank.
Bart
@Bart: Wenn Sie sich beispielsweise die Vorlesungsunterlagen von Lovasz cs.elte.hu/~lovasz/semidef.ps ansehen , finden Sie in Satz 3.7 (Seite 19) Erläuterungen zur Laufzeitgrenze der Ellipsoidmethode für die konvexe Minimierung . Dort werden einige technische Annahmen auferlegt.
Yoshio Okamoto
4
rRlogR/r
Vielen Dank dafür. Dies beantwortet einen sehr großen Teil meiner Frage. Es scheint, dass dieses Wissen für theoretische Informatiker ein sehr nützliches Werkzeug sein kann, während es mir dennoch so scheint, dass es überhaupt nicht bekannt ist und fast nirgendwo erwähnt wird. Seltsam.
Bart