Sum-of-squares representations for copositive matrices and independent sets in graphs

A polynomial optimization problem asks for minimizing a polynomial function (cost) given a set of constraints (rules) represented by polynomial inequalities and equations. Many hard problems in combinatorial optimization and applications in operations research can be naturally encoded as polynomial optimization problems. A common approach for addressing such computationally hard problems is by considering variations of the original problem that give an approximate solution, and that can be solved efficiently. One such approach for attacking hard combinatorial problems and, more generally, polynomial optimization problems, is given by the so-called sum-of-squares approximations. This thesis focuses on studying whether these approximations find the optimal solution of the original problem.

We investigate this question in two main settings: 1) Copositive programs and 2) parameters dealing with independent sets in graphs. Among our main new results, we characterize the matrix sizes for which sum-of-squares approximations are able to capture all copositive matrices. In addition, we show finite convergence of the sums-of-squares approximations for maximum independent sets in graphs based on their continuous copositive reformulations. We also study sum-of-squares approximations for parameters asking for maximum balanced independent sets in bipartite graphs. In particular, we find connections with the Lovász theta number and we design eigenvalue bounds for several related parameters when the graphs satisfy some symmetry properties.