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

Fingerprint

Convergence Analysis
Compact Set
Euclidean
Ball
Upper bound
Order of a polynomial
Polynomial
Optimization
Semidefinite Programming
Sum of squares
Lebesgue Measure
Polytopes
Hypercube
Density Function
Probability density function
Lipschitz
Continuous Function
Rate of Convergence
Moment
Boundary conditions

Keywords

  • polynomial optimization
  • semidefinite optimization
  • Lasserre hierarchy

Cite this

de Klerk, E., Laurent, M., & Sun, Z. (2014). Convergence Analysis for Lasserre's Measure-based Hierarchy of Upper Bounds for Polynomial Optimization. (Preprint at arXiv; Vol. 1411.6867v3). Ithaca: Cornell University Library.
@book{0d85965de6804f6cb3c6ddf8e2cafc00,
title = "Convergence Analysis for Lasserre's Measure-based Hierarchy of Upper Bounds for Polynomial Optimization",
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.",
keywords = "polynomial optimization, semidefinite optimization, Lasserre hierarchy",
author = "{de Klerk}, E. and M. Laurent and Z. Sun",
year = "2014",
month = "12",
day = "1",
language = "English",
volume = "1411.6867",
series = "Preprint at arXiv",
publisher = "Cornell University Library",

}

de Klerk, E, Laurent, M & Sun, Z 2014, Convergence Analysis for Lasserre's Measure-based Hierarchy of Upper Bounds for Polynomial Optimization. Preprint at arXiv, vol. 1411.6867v3, vol. 1411.6867, Cornell University Library, Ithaca.

Convergence Analysis for Lasserre's Measure-based Hierarchy of Upper Bounds for Polynomial Optimization. / de Klerk, E.; Laurent, M.; Sun, Z.

Ithaca : Cornell University Library, 2014. 23 p. (Preprint at arXiv; Vol. 1411.6867v3).

Research output: Book/ReportReportProfessional

TY - BOOK

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

AU - de Klerk, E.

AU - Laurent, M.

AU - Sun, Z.

PY - 2014/12/1

Y1 - 2014/12/1

N2 - 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.

AB - 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.

KW - polynomial optimization

KW - semidefinite optimization

KW - Lasserre hierarchy

M3 - Report

VL - 1411.6867

T3 - Preprint at arXiv

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

PB - Cornell University Library

CY - Ithaca

ER -