Research portal

Research output: Scientific - peer-review › Article

We consider the problem of minimizing a continuous function f over a compact set K. We analyze a hierarchy of upper bounds proposed by Lasserre (SIAM J Optim 21(3):864–885, 2011), obtained by searching for an optimal probability density function h on K which is a sum of squares of polynomials, so that the expectation ∫Kf(x)h(x)dx is minimized. We show that the rate of convergence is no worse than O(1/√r), where 2r is the degree bound on the density function. This analysis applies to the case when f is Lipschitz continuous and K is a full-dimensional compact set satisfying some boundary condition (which is satisfied, e.g., for convex bodies). The rth upper bound in the hierarchy may be computed using semidefinite programming if f is a polynomial of degree d, and if all moments of order up to 2r+d of the Lebesgue measure on K are known, which holds, for example, if K is a simplex, hypercube, or a Euclidean ball.

Original language | English |
---|---|

Pages (from-to) | 363-392 |

Journal | Mathematical Programming |

Volume | 162 |

Issue number | 1 |

DOIs | |

State | Published - Mar 2017 |

- polynomial optimization, semidefinite optimization, Lasserre hierarchy

- 10.1007/s10107-016-1043-1
Final published version