joint work with Monique Laurent
We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre (2011), for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2r with respect to the surface measure. We show that the exact rate of convergence is of order 1/r^2. (Joint work with Monique Laurent.)
joint work with David de Laat, J. Rolfes, F. Vallentin
Let (X,d) be a compact metric space. For a given positive number r we are interested in the minimum number of balls of radius r needed to cover X. We provide a sequence of infinite-dimensional conic programs each of which yields a lower bound for this number and show that the resulting sequence of lower bounds converges in finitely many steps to the minimal number of balls needed. These programs satisfy strong duality and we can derive a finite dimensional semidefinite program to approximate the optimal solution to arbitrary precision.
joint work with Jean-Bernard Lasserre, Mohab Safey El Din
We interpret some wrong results, due to numerical inaccuracies, observed when solving semidefinite programming (SDP) relaxations for polynomial optimization. The SDP solver performs robust optimization and the procedure can be viewed as a max-min problem with two players. Next, we consider the problem of finding exact sums of squares (SOS) decompositions with SDP solvers. We provide a perturbation-compensation algorithm computing exact decompositions for elements in the interior of the SOS cone. We prove that this algorithm has a polynomial boolean running time w.r.t. the input degree.