Sums of Squares and Perfect Graphs

The problem of optimizing over the set of nonnegative polynomials naturally arises in a variety of applications in different areas. These include control theory, statistics, game theory, and combinatorial optimization. While this problem is generally intractable to solve, it is possible to use sums of squares (sos) as surrogates for nonnegative polynomials, and solve an approximation of the problem using semidefinite programming. In recent years, understanding the relationship between nonnegative and sos polynomials has become increasingly relevant to the field of optimization theory.

This talk consists of two parts. The first part studies this relationship for separable plus quadratic (SPQ) polynomials. We provide a complete characterization of the gap between nonnegative and sos polynomials of this structure, based on the degree and dimension. We further extend our study, showing that convex SPQ polynomial optimization problems can be solved by “small” semidefinite programs. Finally, we present applications of SPQ polynomials to upper bounding sparsity of solutions to linear programs, polynomial regression problems in statistics, and a generalization of Newton’s method.

In the second part, we study this relationship in connection with perfect graphs, i.e., graphs for which the clique number and the chromatic number coincide for every induced subgraph. Bringing together a number of interesting results in graph theory and conic optimization, we present an algebraic characterization of perfect graphs. We show that a graph is perfect if and only if certain nonnegative polynomials associated with the graph are sos. As a byproduct, we obtain several infinite families of nonnegative polynomial that are not sos through graph-theoretic constructions.

Share this Event