Zusammenfassung - Ein unbedingter unterer Schwellenwert für die aktive-Set-Methode in konvexer quadratischer Maximierung

Ein unbedingter unterer Schwellenwert für die aktive-Set-Methode in konvexer quadratischer Maximierung

2025-07-22 14:46:07

{"Eleon Bach","Yann Disser","Sophie Huiberts","Nils Mosis"}

{cs.DM,cs.CC,cs.DS,math.CO}

Das Papier beweist, dass die aktive-Set-Methode im schlimmsten Fall eine exponentielle Anzahl von Iterationen benötigt, um eine konvexe quadratische Funktion unter linearen约束条件下最大化，unabhängig davon, welche Pivot-Regel verwendet wird. Dieses Ergebnis verbessert den bisher besten bekannten unteren Schranke erheblich und löst eine offene Frage darüber, ob eine konstante Ordnung ausreichend ist. Die wichtigsten Beiträge des Papiers umfassen: - Der Beweis einer exponentiellen unteren Schranke für die konvexe quadratische Maximierung, der den vorherigen Schranke von ω(log d) Polynomgraden für eine superpolynomiale Schranke und Ω(d) Polynomgraden für eine exponentielle Schranke verbessert. - Die Beantwortung einer offenen Frage darüber, ob eine konstante Ordnung für die konvexe quadratische Maximierung ausreichend ist. - Die Konstruktion einer neuen erweiterten Formulierung durch Verformte Produkte, die möglicherweise ein Interesse im eigenen Recht haben. - Eine bedingungslose untere Schranke für die aktive-Set-Methode bereitzustellen, was ein wichtiger Beitrag zum Verständnis der Komplexität von linearen Programmieralgorithmen ist. Die erweiterte Formulierung des Papiers wird durch wiederholte Anwendung verformter Produkte auf zwei Polygone definiert durch die Funktion x^2 - x konstruiert. Ein wesentliches Merkmal dieser erweiterten Formulierung ist, dass ihre Projektion auf eine Ebene eine polygonale Näherung einer Parabel ergibt, während alle ihrer exponentiellen Vielecken erhalten bleiben. Das Papier zeigt dann, dass die aktive-Set-Methode eine exponentielle Anzahl von Iterationen benötigt, um eine konvexe quadratische Funktion über die erweiterte Formulierung zu maximieren. Dies wird durch die Konstruktion einer konvexen quadratischen Zielfunktion erreicht, die die aktive-Set-Methode zwingt, der Parabelkante der Projektion zu folgen, ohne kürzeste Wege entlang der Kanten der erweiterten Formulierung zu erlauben. Insgesamt bietet das Papier bedeutende Einblicke in die Komplexität der aktiven-Set-Methode und leistet einen wichtigen Beitrag zum Verständnis der Komplexität von linearen Programmieralgorithmen.