Asymptotic analysis of semidefinite bounds for polynomial optimization and independent sets in geometric hypergraphs

Lucas Slot

Research output: ThesisDoctoral Thesis

94 Downloads (Pure)

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 measure-based hierarchy in a wide variety of settings (Part 1). We establish error bounds for the moment-SOS 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 languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Tilburg University
Supervisors/Advisors
  • Laurent, Monique, Promotor
  • de Klerk, Etienne, Promotor
Award date30 Sept 2022
Place of PublicationTilburg
Publisher
Print ISBNs 978 905668 689 5
DOIs
Publication statusPublished - 2022

Fingerprint

Dive into the research topics of 'Asymptotic analysis of semidefinite bounds for polynomial optimization and independent sets in geometric hypergraphs'. Together they form a unique fingerprint.

Cite this