Inaugural lecture of the French Seminar of Optimization
coorganized by GDR MOA, PGMO and SMAI MODE
Monique Laurent (CWI and Tilburg University)
https://homepages.cwi.nl/~monique/
Wed 10th June, 2020, at 17h30, Paris time, in videoconference
Participate to the zoom meeting:
https://zoom.us/j/4624711880?pwd=Y1ZNenRBamlhSnpZc2RoczZUbkR3QT09
ID de réunion : 462 471 1880
Mot de passe : 778210
Title: Convergence analysis of approximation hierarchies for polynomial
optimization.
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.
Organizers of the seminar:
S. Adly, J. Bolte, A. Chambolle, S. Charousset-Brignol, S.
Gaubert, F. Santambrogio