Open Access

Sadik Iliman

• The cones of nonnegative polynomials and sums of squares arise as central objects in convex algebraic geometry and have their origin in the seminal work of Hilbert ([Hil88]). Depending on the number of variables n and the degree d of the polynomials, Hilbert famously characterizes all cases of equality between the cone of nonnegative polynomials and the cone of sums of squares. This equality precisely holds for bivariate forms, quadratic forms and ternary quartics ([Hil88]). Since then, a lot of work has been done in understanding the difference between these two cones, which has major consequences for many practical applications such as for polynomial optimization problems. Roughly speaking, minimizing polynomial functions (constrained as well as unconstrained) can be done efficiently whenever certain nonnegative polynomials can be written as sums of squares (see Section 2.3 for the precise relationship). The underlying reason is the fundamental difference that checking nonnegativity of polynomials is an NP-hard problem whenever the degree is greater or equal than four ([BCSS98]), whereas checking whether a polynomial can be written as a sum of squares is a semidefinite feasibility problem (see Section 2.2). Although the complexity status of the semidefinite feasibility problem is still an open problem, it is polynomial for fixed number of variables. Hence, understanding the difference between nonnegative polynomials and sums of squares is highly desirable both from a theoretical and a practical viewpoint.
• Die konvexen Kegel der nichtnegativen Polynome und Summen von Quadraten sind zentrale Objekte in der konvexen algebraischen Geometrie. Ihr Ursprung liegt in der bedeutenden Arbeit von Hilbert ([Hil88]). Darin werden bezüglich der Anzahl der Variablen n und dem Grad d der Polynome alle Fälle charakterisiert, in denen die Kegel übereinstimmen. Diese Übereinstimmung liegt nur für binäre Formen, quadratische Formen und für ternäre Quartiken vor. Seit dieser klassischen Arbeit ist die Frage nach der Differenz zwischen den beiden Kegeln auch heute noch ein sehr wichtiges und aktuelles Problem. Sie ist für viele Anwendungen von zentraler Bedeutung. Das sicherlich prominenteste Anwendungsgebiet liegt in polynomiellen Optimierungsproblemen, deren Lösung äquivalent dazu ist, die Nichtnegativität von Polynomen zu entscheiden. Diese Optimierungsprobleme lassen sich insbesondere dann effizient lösen, wenn sich spezielle nichtnegative Polynome in diesem Rahmen als Summe von Quadraten schreiben lassen. Der Grund hierfür liegt in der Tatsache, dass die Entscheidung, ob ein gegebenes Polynom nichtnegativ ist, im Allgemeinen NP-schwer ist ([BCSS98]). Die Frage, ob ein Polynom aber eine Summe von Quadraten ist, lässt sich mittels eines semideffiniten Zugehörigkeitsproblems lösen. Die Komplexität semideffiniter Zugehörigkeitsprobleme ist zwar im Allgemeinen ungeklärt, sie ist aber polynomiell für eine feste Anzahl an Variablen des Polynoms. Dementsprechend ist eine fundierte Kenntnis über die Differenz des Kegels der nichtnegativen Polynome und des Kegels der Summen von Quadraten sowohl auf der theoretischen als auch auf der praktischen Seite sehr wünschenswert.