Bound-constrained polynomial optimization using only elementary calculations

Etienne de Klerk, J.B. Lasserre, Monique Laurent, Zhao Sun

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We provide a monotone nonincreasing sequence of upper bounds fHk(k≥1)fkH(k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in ℝn. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21:864–885] is that only elementary computations are required. For optimization over the hypercube [0, 1]n, we show that the new bounds fHkfkH have a rate of convergence in O(1/k−−√)O(1/k). Moreover, we show a stronger convergence rate in O(1/k) for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator k produces bounds with a rate of convergence in O(1/k2), but at the cost of O(kn) function evaluations, while the new bound fHkfkH needs only O(nk) elementary calculations.
LanguageEnglish
Pages834-853
JournalMathematics of Operations Research
Volume42
Issue number3
Early online dateMar 2017
DOIs
StatePublished - Aug 2017

Fingerprint

Hypercube
Polynomials
Polynomial
Optimization
Rate of Convergence
Upper bound
Monotone Sequences
Quadratic Polynomial
Nonnegativity
Global Minimum
Denominator
Evaluation Function
Closed set
Strong Convergence
Minimizer
Convergence Rate
Function evaluation
Grid
Unit
Evaluation

Keywords

  • polynomial optimization
  • bound-constrained optimization
  • Lasserre hierarchy

Cite this

@article{ff5f1b52b2b848fcb9cb123e59858c0e,
title = "Bound-constrained polynomial optimization using only elementary calculations",
abstract = "We provide a monotone nonincreasing sequence of upper bounds fHk(k≥1)fkH(k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in ℝn. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21:864–885] is that only elementary computations are required. For optimization over the hypercube [0, 1]n, we show that the new bounds fHkfkH have a rate of convergence in O(1/k−−√)O(1/k). Moreover, we show a stronger convergence rate in O(1/k) for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator k produces bounds with a rate of convergence in O(1/k2), but at the cost of O(kn) function evaluations, while the new bound fHkfkH needs only O(nk) elementary calculations.",
keywords = "polynomial optimization, bound-constrained optimization, Lasserre hierarchy",
author = "{de Klerk}, Etienne and J.B. Lasserre and Monique Laurent and Zhao Sun",
year = "2017",
month = "8",
doi = "10.1287/moor.2016.0829",
language = "English",
volume = "42",
pages = "834--853",
journal = "Mathematics of Operations Research",
issn = "0364-765X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "3",

}

Bound-constrained polynomial optimization using only elementary calculations. / de Klerk, Etienne; Lasserre, J.B.; Laurent, Monique; Sun, Zhao.

In: Mathematics of Operations Research, Vol. 42, No. 3, 08.2017, p. 834-853.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Bound-constrained polynomial optimization using only elementary calculations

AU - de Klerk,Etienne

AU - Lasserre,J.B.

AU - Laurent,Monique

AU - Sun,Zhao

PY - 2017/8

Y1 - 2017/8

N2 - We provide a monotone nonincreasing sequence of upper bounds fHk(k≥1)fkH(k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in ℝn. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21:864–885] is that only elementary computations are required. For optimization over the hypercube [0, 1]n, we show that the new bounds fHkfkH have a rate of convergence in O(1/k−−√)O(1/k). Moreover, we show a stronger convergence rate in O(1/k) for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator k produces bounds with a rate of convergence in O(1/k2), but at the cost of O(kn) function evaluations, while the new bound fHkfkH needs only O(nk) elementary calculations.

AB - We provide a monotone nonincreasing sequence of upper bounds fHk(k≥1)fkH(k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in ℝn. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21:864–885] is that only elementary computations are required. For optimization over the hypercube [0, 1]n, we show that the new bounds fHkfkH have a rate of convergence in O(1/k−−√)O(1/k). Moreover, we show a stronger convergence rate in O(1/k) for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator k produces bounds with a rate of convergence in O(1/k2), but at the cost of O(kn) function evaluations, while the new bound fHkfkH needs only O(nk) elementary calculations.

KW - polynomial optimization

KW - bound-constrained optimization

KW - Lasserre hierarchy

U2 - 10.1287/moor.2016.0829

DO - 10.1287/moor.2016.0829

M3 - Article

VL - 42

SP - 834

EP - 853

JO - Mathematics of Operations Research

T2 - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 3

ER -