Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

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

Research output: Working paperOther research output

Abstract

We provide a monotone non increasing sequence of upper bounds fHk (k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864--885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds fHk have a rate of convergence in 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 fHk needs only O(nk) elementary calculations.
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages23
Publication statusPublished - 15 Jul 2015

Publication series

NamearXiv
Volume1507.04404

Fingerprint

Hypercube
Polynomial
Optimization
Rate of Convergence
Upper bound
Monotonic increasing sequence
Quadratic Polynomial
Nonnegativity
Global Minimum
Denominator
Evaluation Function
Closed set
Strong Convergence
Minimizer
Convergence Rate
Monotone
Grid
Unit
Evaluation

Keywords

  • polynomial optimization
  • bound-constrained optimization
  • Lasserre hierarchy

Cite this

de Klerk, E., Lasserre, J. B., Laurent, M., & Sun, Z. (2015). Bound-Constrained Polynomial Optimization Using Only Elementary Calculations. (arXiv; Vol. 1507.04404). Ithaca: Cornell University Library.
de Klerk, Etienne ; Lasserre, J.B. ; Laurent, Monique ; Sun, Zhao. / Bound-Constrained Polynomial Optimization Using Only Elementary Calculations. Ithaca : Cornell University Library, 2015. (arXiv).
@techreport{992aff123d94494083637949454703bc,
title = "Bound-Constrained Polynomial Optimization Using Only Elementary Calculations",
abstract = "We provide a monotone non increasing sequence of upper bounds fHk (k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864--885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds fHk have a rate of convergence in 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 fHk 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 = "2015",
month = "7",
day = "15",
language = "English",
series = "arXiv",
publisher = "Cornell University Library",
type = "WorkingPaper",
institution = "Cornell University Library",

}

de Klerk, E, Lasserre, JB, Laurent, M & Sun, Z 2015 'Bound-Constrained Polynomial Optimization Using Only Elementary Calculations' arXiv, vol. 1507.04404, Cornell University Library, Ithaca.

Bound-Constrained Polynomial Optimization Using Only Elementary Calculations. / de Klerk, Etienne; Lasserre, J.B.; Laurent, Monique; Sun, Zhao.

Ithaca : Cornell University Library, 2015. (arXiv; Vol. 1507.04404).

Research output: Working paperOther research output

TY - UNPB

T1 - Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

AU - de Klerk, Etienne

AU - Lasserre, J.B.

AU - Laurent, Monique

AU - Sun, Zhao

PY - 2015/7/15

Y1 - 2015/7/15

N2 - We provide a monotone non increasing sequence of upper bounds fHk (k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864--885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds fHk have a rate of convergence in 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 fHk needs only O(nk) elementary calculations.

AB - We provide a monotone non increasing sequence of upper bounds fHk (k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864--885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds fHk have a rate of convergence in 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 fHk needs only O(nk) elementary calculations.

KW - polynomial optimization

KW - bound-constrained optimization

KW - Lasserre hierarchy

UR - http://arxiv.org/abs/1507.04404

M3 - Working paper

T3 - arXiv

BT - Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

PB - Cornell University Library

CY - Ithaca

ER -

de Klerk E, Lasserre JB, Laurent M, Sun Z. Bound-Constrained Polynomial Optimization Using Only Elementary Calculations. Ithaca: Cornell University Library. 2015 Jul 15. (arXiv).