PGMO Seminars 2020
- Wed 10th June, 2020 - Convergence analysis of approximation hierarchies for polynomial optimization
Monique Laurent (CWI and Tilburg University)
Abstract: Minimizing a polynomial function f over a compact set K is a computationally hard problem. Upper bounds have been introduced by Lasserre (2011), which are obtained by searching for a degree 2r sum-of-squares density function minimizing the expected value of f over K with respect to a given reference measure supported by K. We will discuss several techniques that permit to analyse the performance guarantee of these bounds. This includes an eigenvalue reformulation of the bounds, links to extremal roots of orthogonal polynomials and to cubature rules, and reducing to the univariate case by means of push-forward measures. For simple sets K like the box, the unit ball, the simplex and the unit sphere one can show that the convergence
rate to the global minimum is in O(1/r^2) and that this bound is tight for some classes of polynomials. These results extend to smooth strictly convex bodies satisfying some boundary conditions and, for general convex bodies, one can show a slightly weaker convergence rate in O((log(r)/r)^2). Based on joint works with Etienne de Klerk and Lucas Slot.