Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing

Research output: Contribution to journalArticleScientificpeer-review

78 Downloads (Pure)

Abstract

We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre [Lasserre JB (2011) A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21(3):864–885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, this comparison yields a faster rate of convergence of the Lasserre hierarchy than what was previously known in the literature.
Original languageEnglish
Pages (from-to)1317-1325
JournalMathematics of Operations Research
Volume43
Issue number4
DOIs
Publication statusPublished - Nov 2018

Fingerprint

Simulated annealing
Simulated Annealing
Polynomials
Polynomial
Optimization
Nonnegativity
Convex Body
Closed set
Compact Set
Continuous Function
Rate of Convergence
Upper bound
Hierarchy
Rate of convergence

Keywords

  • polynomial optimization
  • semidefinite optimization
  • Lasserre hierarchy
  • simulated annealing

Cite this

@article{78f8f496dc89413e864df01908bfbe2e,
title = "Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing",
abstract = "We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre [Lasserre JB (2011) A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21(3):864–885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, this comparison yields a faster rate of convergence of the Lasserre hierarchy than what was previously known in the literature.",
keywords = "polynomial optimization, semidefinite optimization, Lasserre hierarchy, simulated annealing",
author = "{de Klerk}, Etienne and Monique Laurent",
year = "2018",
month = "11",
doi = "10.1287/moor.2017.0906",
language = "English",
volume = "43",
pages = "1317--1325",
journal = "Mathematics of Operations Research",
issn = "0364-765X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "4",

}

Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing. / de Klerk, Etienne; Laurent, Monique.

In: Mathematics of Operations Research, Vol. 43, No. 4, 11.2018, p. 1317-1325.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing

AU - de Klerk, Etienne

AU - Laurent, Monique

PY - 2018/11

Y1 - 2018/11

N2 - We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre [Lasserre JB (2011) A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21(3):864–885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, this comparison yields a faster rate of convergence of the Lasserre hierarchy than what was previously known in the literature.

AB - We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre [Lasserre JB (2011) A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21(3):864–885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, this comparison yields a faster rate of convergence of the Lasserre hierarchy than what was previously known in the literature.

KW - polynomial optimization

KW - semidefinite optimization

KW - Lasserre hierarchy

KW - simulated annealing

U2 - 10.1287/moor.2017.0906

DO - 10.1287/moor.2017.0906

M3 - Article

VL - 43

SP - 1317

EP - 1325

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 4

ER -