Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

Etienne de Klerk (), Jean B. Lasserre (), Monique Laurent () and Zhao Sun ()
Additional contact information
Etienne de Klerk: Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands; and Delft Institute of Applied Mathematics, Delft University of Technology, 2628 CD Delft Netherlands
Jean B. Lasserre: LAAS-CNRS and Institute of Mathematics, University of Toulouse, 31400 Toulouse, France
Monique Laurent: Centrum Wiskunde and Informatica (CWI), 1098 XG Amsterdam, Netherlands; and Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands
Zhao Sun: Symetrics B.V., 1097 DN Amsterdam, Netherlands

Mathematics of Operations Research, 2017, vol. 42, issue 3, 834-853

Abstract: We provide a monotone nonincreasing sequence of upper bounds f k H ( 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 f k H 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/ k 2 ), but at the cost of O ( k n ) function evaluations, while the new bound f k H needs only O ( n k ) elementary calculations.

Keywords: polynomial optimization; bound-constrained optimization; Lasserre hierarchy (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0829 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:3:p:834-853

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().