{
  "id": "1411.6867",
  "version": "v1",
  "published": "2014-11-25T13:44:21.000Z",
  "updated": "2014-11-25T13:44:21.000Z",
  "title": "Convergence analysis for Lasserre's measure--based hierarchy of upper bounds for polynomial optimization",
  "authors": [
    "Etienne de Klerk",
    "Monique Laurent",
    "Zhao Sun"
  ],
  "comment": "21 pages, 2 figures, 6 tables",
  "categories": [
    "math.OC"
  ],
  "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 $\\int_{K}f(x)h(x)dx$ is minimized. We show that the rate of convergence is $O(1/\\sqrt{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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-11-25T13:44:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C22",
      "90C26",
      "90C30"
    ],
    "keywords": [
      "lasserres measure-based hierarchy",
      "polynomial optimization",
      "convergence analysis",
      "optimal probability density function",
      "euclidean ball"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1411.6867D"
    }
  }
}