https://zoom.us/j/6547746234?pwd=ZENZNWtCbUlQRjVMMVFneWtxZGlzZz09
Speaker: Dr. Cemil Dibek, Princeton University
Abstract: The problem of optimizing over the set of nonnegative polynomials naturally arises in a variety of applications in different areas, such as control theory, statistics, game theory, and combinatorial optimization. While this problem is generally intractable to solve, it is possible to use sum of squares (sos) polynomials 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 thus become increasingly relevant to the field of optimization theory.
In the first part of the talk, we study 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 to convex SPQ polynomials and show 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 of the talk, 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 polynomials that are not sos through graph-theoretic constructions.
