Convergence Analysis for Lasserre's Measure-based Hierarchy of Upper Bounds for Polynomial Optimization

Research output: Book/ReportReportProfessional

Abstract

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 in [SIAM J. Optim. 21(3) (2011), pp. 864--885], obtained by searching for an optimal probability density function h on K which is a sum of squares of polynomials, so that the expectation ∫ K f(x)h(x)dx is minimized. We show that the rate of convergence is 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 polytopes and the Euclidean ball). The r-th 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 languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages23
Volume1411.6867
Publication statusPublished - 1 Dec 2014

Publication series

NamePreprint at arXiv
Volume1411.6867v3

Keywords

  • polynomial optimization
  • semidefinite optimization
  • Lasserre hierarchy

Fingerprint Dive into the research topics of 'Convergence Analysis for Lasserre's Measure-based Hierarchy of Upper Bounds for Polynomial Optimization'. Together they form a unique fingerprint.

  • Cite this