Abstract
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 socalled sumofsquares 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 sumofsquares approximations are able to capture all copositive matrices. In addition, we show finite convergence of the sumsofsquares approximations for maximum independent sets in graphs based on their continuous copositive reformulations. We also study sumofsquares 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.
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 sumofsquares approximations are able to capture all copositive matrices. In addition, we show finite convergence of the sumsofsquares approximations for maximum independent sets in graphs based on their continuous copositive reformulations. We also study sumofsquares 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.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  3 Nov 2023 
Place of Publication  Tilburg 
Publisher  
Print ISBNs  978 90 5668 721 2 
DOIs  
Publication status  Published  2023 