published on December 8, 2023
Beyond Painlevé: The need for computational tools to reveal hidden structure
By Nicholas Witte
Sums of squares approximations in polynomial optimization: performance analysis and degree bounds
Appears in collection : 2023 - T3 - WS2 - Geometry of polynomial system solving, optimization and topology
Polynomial optimization deals with optimizing a polynomial function over a feasible region defined by polynomial inequalities, thus modeling a broad range of hard nonlinear nonconvex optimization problems. Hierarchies of tractable semidefinite relaxations have been introduced that are based on using sums of squares of polynomials as a ``proxy” for global nonnegativity. These hierarchies give bounds on the global minimum of the original problem with asymptotic convergence (under a minor compactness assumption). In this lecture we discuss recent results on the performance analysis of these hierarchies and related effective degree bounds for dedicated sums of squares representations of positive polynomials on some classes of compact semi-algebraic sets (including the hypercube, the sphere or the ball).
