Abstract
The goal of a mathematical optimization problem is to maximize an objective (or minimize a cost) under a given set of rules, called constraints. Optimization has many applications, both in other areas of mathematics and in the real world. Unfortunately, some of the most interesting problems are also very hard to solve numerically. To work around this issue, one often considers relaxations: approximations of the original problem that are much easier to solve. Naturally, it is then important to understand how (in)accurate these relaxations are.
This thesis consists of three parts, each covering a different method that uses semidefinite programming to approximate hard optimization problems.
In Part 1 and Part 2, we consider two hierarchies of relaxations for polynomial optimization problems based on sums of squares. We show improved guarantees on the quality of Lasserre's measurebased hierarchy in a wide variety of settings (Part 1). We establish error bounds for the momentSOS hierarchy in certain fundamental special cases. These bounds are much stronger than the ones obtained from existing, general results (Part 2).
In Part 3, we generalize the celebrated Lovász theta number to (geometric) hypergraphs. We apply our generalization to formulate relaxations for a type of independent set problem in the hypersphere. These relaxations allow us to improve some results in Euclidean Ramsey theory.
This thesis consists of three parts, each covering a different method that uses semidefinite programming to approximate hard optimization problems.
In Part 1 and Part 2, we consider two hierarchies of relaxations for polynomial optimization problems based on sums of squares. We show improved guarantees on the quality of Lasserre's measurebased hierarchy in a wide variety of settings (Part 1). We establish error bounds for the momentSOS hierarchy in certain fundamental special cases. These bounds are much stronger than the ones obtained from existing, general results (Part 2).
In Part 3, we generalize the celebrated Lovász theta number to (geometric) hypergraphs. We apply our generalization to formulate relaxations for a type of independent set problem in the hypersphere. These relaxations allow us to improve some results in Euclidean Ramsey theory.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  30 Sept 2022 
Place of Publication  Tilburg 
Publisher  
Print ISBNs  978 905668 689 5 
DOIs  
Publication status  Published  2022 