PhD Defense D. Brosch

Mathematical optimization is a central computational tool for a wide variety of problems, ranging from logistics and healthcare to quantum computing. Often it is hopeless to try to solve these problems exactly, which motivates the search for convex relaxations. Convex relaxations are usually more computationally tractable and can be a crucial step towards solving the original problems.

Often, problems coming from computer science, physics, algebra and geometry exhibit symmetries, which can be exploited to further reduce the time needed to solve the problems. This dissertation explores different approaches to and applications of symmetry reduction in convex optimization. Using tools from semidefinite programming, representation theory and algebraic combinatorics, hard combinatorial problems are solved or bounded. The first chapters consider the Jordan reduction method, extend the method to optimization over the doubly nonnegative cone, and apply it to quadratic assignment problems and energy minimization on a discrete torus. The following chapter uses symmetry reduction as a proving tool, to approach a problem from queuing theory with redundancy scheduling. The final chapters propose generalizations and reductions of flag algebras, a powerful tool for problems coming from extremal combinatorics.

Daniel Brosch will defend his thesis with the title ‘’Symmetry Reduction in Convex Optimization with Applications in Combinatorics’’ at Tilburg University on Wednesday October 19, 2022.