Betrachten Sie ein konvexes Optimierungsproblem im Formular
wobei konvexe Funktionen sind. Ohne Verlust der Allgemeinheit können wir annehmen, dass linear ist.
Nesterov und Nemirovskii erwähnen in ihrem Buch "Interior Point Polynomial Algorithmen in der konvexen Programmierung", dass es einen Algorithmus gibt, der jedes konvexe Programm in der Polynomzeit im folgenden Sinne lösen kann. Wir wollen eine Lösung mit einer relativen Genauigkeit auf Kosten von Berechnungen der Werte und Berechnungen der Subgradienten. Dann wird für die Ellipsoidmethode behauptet, dass
Auf den ersten Blick scheint dies zu implizieren, dass ein konvexes Optimierungsproblem in Polynomzeit mit der Ellipsoidmethode gelöst werden kann (nehmen wir der Einfachheit halber an, dass die Orakel zur Berechnung der Werte und der Subgradienten -Zeit für die betrachtete Klasse von benötigen konvexe Optimierungsprobleme).
Ich verstehe jedoch überhaupt nicht, ob die Ausdrücke (\ cdot) irgendwie von den Funktionen abhängen , z. B. von ihren Hessen, oder nicht. In diesem Fall kann die Komplexität aufgrund der Krümmungseigenschaften der Funktionen ein exponentielles Aufblasen aufweisen. Darüber hinaus wird auf mysteriöse Weise behauptet, dass "die Ellipsoidmethode in der Praxis nicht gut funktioniert". Im Internet scheint es keinen Konsens zu geben, ob die Antwort auf meine Frage positiv oder negativ ist, siehe z. B. diese Diskussion zu MathOverflow.
Ich habe in jedem Buch über konvexe Optimierung gesucht, das ich finden konnte, und ich habe den Eindruck gewonnen, dass dieses zwar vom Problem abhängt, aber keine eindeutige Bestätigung dieser Vermutung finden konnte. Meine einzige Hoffnung ist es also, Leute, die auf diesem Gebiet forschen, direkt zu fragen.
Später entwickelte innere Punktmethoden scheinen die Krümmung explizit unter Verwendung des Begriffs selbstkonkordanter Barrieren zu berücksichtigen. Wenn die Leute jedoch sagen, dass diese Methoden in der Praxis effizient sind, spezifizieren sie dies normalerweise nicht auf der Ebene der Komplexität.
quelle
Antworten:
Im Jahr 1998 hielt Michel X. Goemans einen ICM-Vortrag, in dem er sich mit diesem Thema befasste: "Semidefinite Programme können in Polynomzeit mit einer bestimmten Genauigkeit entweder durch den Ellipsoid-Algorithmus oder effizienter durch gelöst (oder genauer angenähert) werden Innenpunktalgorithmen ... Die obigen Algorithmen liefern eine streng realisierbare Lösung (oder für einige Versionen des Ellipsoidalgorithmus leicht nicht realisierbar), und tatsächlich ist das Problem der Entscheidung, ob ein semidefinites Programm (genau) realisierbar ist, noch offen. A. Ein Sonderfall der Durchführbarkeit der semidefiniten Programmierung ist das Quadratwurzelsummenproblem. Die Komplexität dieses Problems ist noch offen. " http://garden.irmacs.sfu.ca/op/complexity_of_square_root_sum
1976 konnten Ron Graham, Michael Garey und David Johnson einige geometrische Optimierungsprobleme nicht aufzeigen, z. B. ob das Problem des euklidischen reisenden Verkäufers NP-vollständig ist (sie können nur zeigen, dass das Problem NP-schwer ist). Der Grund dafür ist, dass sie dies nicht konnten Zeigen Sie, ob das Quadratwurzelsummenproblem polynomial lösbar ist oder nicht. https://rjlipton.wordpress.com/2009/03/04/ron-graham-gives-a-talk/
Das Quadratwurzel-Summen-Problem ist ein lange offenes Problem, das Wissenschaftler aus den Bereichen Computergeometrie, Optimierung, Rechenkomplexität, Spieltheorie und einigen anderen Bereichen verwirrt, da sie alle irgendwann herausfinden, dass das Haupthindernis für ihre Probleme darin besteht, es zu lösen das Quadratwurzel-Summen-Problem.
Der bemerkenswerteste Fortschritt in Richtung dieses Problems ist von Eric Allender und seinen Co-Autoren. 2003 zeigten sie, dass dieses Problem in der 4. Ebene der Zählhierarchie liegt. http://ftp.cs.rutgers.edu/pub/allender/slp.pdf
Basierend auf den obigen Fakten kann man das Problem der konvexen Optimierung in (wahrer) Polynomzeit mit der Ellipsoid-Methode und der Interior Point-Methode nicht lösen.
Die große O-Notation besteht darin, die Laufzeit des Algorithmus im schlimmsten Fall zu messen. In der Praxis kann der schlimmste Fall jedoch ein sehr seltenes Ereignis sein. Deshalb können Sie ihn nicht zur Messung der praktischen Leistung verwenden.
quelle