A new relaxation technique for polynomial optimization and spectrahedral geometry problems

Die Arbeit „A New Relaxation Technique for Polynomial Optimization and Spectrahedral Geometry Problems“ beschäftigt sich mit zwei Themenkomplexen an der Grenze zwischen den Bereichen der konvexen algebraischen Geometrie und der mathematischen Optimierung. Zunächst wird ein neues Verfahren zum Lösen polynomieller Optimierungsprobleme über semialgebraischen Mengen entwickelt. Aus Sicht der konvexen algebraischen Geometrie werden derartige Probleme üblicherweise mithilfe von Positivstellensätzen aus der reellen algebraischen Geometrie modelliert. Unser Hauptaugenmerk in dieser Arbeit liegt auf dem Fall, dass der Zulässigkeitsbereich ein Polytop ist. In dieser Situation können wir Handelmans Positivstellensatz anwenden. Er besagt, dass ein Polynom genau dann positiv auf einem Polytop ist, wenn es als Positivkombination von Potenzen der das Polytop beschreibenden Ungleichungen dargestellt werden kann. Durch Beschränkung des Grades der Potenzen erhält man ein lineares Programm, für dessen Lösung äußerst effiziente Methoden zur Verfügung stehen. Mit steigender Gradschranke werden die Näherungen immer genauer, die relaxierten Probleme jedoch auch immer komplexer und entsprechend schwerer zu lösen. Um diesem Problem zu begegnen schlagen wir vor, den Zulässigkeitsbereich P aufzuteilen und die resultierenden Unterprobleme auf einer festen Relaxierungsstufe zu lösen. Das resultierende Verfahren vereint die guten Approximationseigenschaften der Positivstellenverfahren mit einem Branch and Bound-Verfahren. Wir entwickeln zunächst eine neue Fehlerschranke für die auf Handelmans Positivstellensatz beruhende Relaxierung. Dabei verallgemeinern wir eine Schranke für die Optimierung eines Polynoms über dem Einheitswürfel von De Klerk und Laurent. Die Schranke wurde explizit so entwickelt, dass sie von der längsten Kante eines um- schließenden Hyperrechtecks abhängt. Dies ermöglicht uns im Folgenden die Konvergenz des auf der Handelman-Relaxierung beruhenden Branch and Bound-Verfahrens zu beweisen. Durch die Anwendung von Positivstellensätzen hat die semidefinite Programmierung in den letzten Jahren stark an Bedeutung für die Approximation polynomieller Optimierungsprobleme gewonnen. Während die Zulässigkeitsbereiche der linearen Programmierung bereits eingehend studiert und weitestgehend verstanden sind, sind die Zulässigkeitsbereiche der semidefiniten Programmierung, sogenannte Spektraeder, ein wichtiger Gegenstand aktueller Forschung. Wir erweitern in dieser Arbeit die bestehenden Klassifikationen zur algorithmischen Komplexität von Polyedern von Gritzmann und Klee auf den Fall von Polyedern und Spektraedern. Insbesondere kann die Frage, ob ein V-Polytop in einem Spektraeder enthalten ist in Polynomialzeit beantwortet werden. Die Frage nach dem Enthaltensein eines Spektraeders in einem H-Polytop kann als semidefinites Lösbarkeitsproblem mit strikten Ungleichungen beschrieben werden. Die übrigen Fälle sind im wesentlichen co-NP-schwer. Dies schließt die Frage nach dem Enthaltensein eines H-Polytops in einem Spektraeder ein, bereits dann, wenn das Spektraeder eine Kugel ist. Zum Beantworten der co-NP-schweren Fälle schlagen wir als Relaxierungsmethode die Verwendung einer Hierarchie von hinreichenden semidefiniten Bedingungen für das Enthaltensein eines Spektraeders in einem zweiten vor. Dazu formulieren wir das Problem zunächst als polynomielles Optimierungsproblem über einem Spektraeder und wenden dann Positivstellensatzrelaxierungen für polynomielle Matrixungleichungen (basierend auf den Arbeiten von Kojima, Hol und Scherer, sowie Henrion und Lasserre) an. Jede Stufe der Hierarchie stellt eine hinreichende Bedingung für die Enthaltenseinsfrage dar. Wir zeigen, dass jede dieser Relaxierungen mindestens so gut ist, wie ein zuvor von Helton, Klep, McCullough sowie von Kellner, Theobald und Trabandt eingeführtes Lösbarkeitskriterium. Dies erlaubt uns, die Exaktheitsaussagen von Kellner, Theobald und Trabandt zu übertragen. Diese gelten insbesondere bereits für die kleinstmögliche Relaxierungsstufe unserer Hierarchie. Unter anderem zeigen wir, dass das Enthaltensein eines Spektraeders in einem Polyeder durch jede Stufe der Relaxierung exakt charakterisiert wird. Wir verdeutlichen die Effektivität der Methode anhand von numerischen Experimenten zu verschiedenen Enthaltenseinsproblemen. Dabei zeigt sich, dass das Verfahren sowohl auf einfachen Testproblemen, als auch auf zufällig generierten Problemen sehr gute Ergebnisse liefert. Üblicherweise wird das Enthaltensein bereits im ersten Relaxierungsschritt zertifiziert. Das bislang beschriebene Verfahren liefert lediglich hinreichende Bedingungen für das Enthaltensein zweier Spektraeder. Wir schlagen ein Verfahren zum Finden von Punkten, die als Zertifikat für das Nicht-Enthaltensein vor. Das Verfahren basiert auf einem Branch and Bound-Verfahren und nutzt Erkenntnisse aus dem Abschnitt über Positivstellensatzverfahren.This work is concerned with two topics at the intersection of convex algebraic geometry and optimization. We develop a new method for the optimization of polynomials over polytopes. From the point of view of convex algebraic geometry the most common method for the approximation of polynomial optimization problems is to solve semidefinite programming relaxations coming from the application of Positivstellensätze. In optimization, non-linear programming problems are often solved using branch and bound methods. We propose a fused method that uses Positivstellensatz-relaxations as lower bounding methods in a branch and bound scheme. By deriving a new error bound for Handelman's Positivstellensatz, we show convergence of the resulting branch and bound method. Through the application of Positivstellensätze, semidefinite programming has gained importance in polynomial optimization in recent years. While it arises to be a powerful tool, the underlying geometry of the feasibility regions (spectrahedra) is not yet well understood. In this work, we study polyhedral and spectrahedral containment problems, in particular we classify their complexity and introduce sufficient criteria to certify the containment of one spectrahedron in another one