Optimization Online


Bound-constrained polynomial optimization using only elementary calculations

Etienne de Klerk (E.deKlerk***at***uvt.nl)
Jean Lasserre (lasserre***at***laas.fr)
Monique Laurent (M.Laurent***at***cwi.nl)
Zhao Sun (z.sun***at***uvt.nl)

Abstract: We provide a monotone non increasing sequence of upper bounds $f^H_k$ ($k\ge 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 $f^H_k$ have a rate of convergence in $O(1/\sqrt {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^H_k$ needs only $O(n^k)$ elementary calculations.

Keywords: Polynomial optimization, bound-constrained optimization, Lasserre hierarchy

Category 1: Nonlinear Optimization (Bound-constrained Optimization )

Category 2: Global Optimization (Theory )

Citation: Technical report, Tilburg University, CWI Amsterdam and LAAS-CNRS, July 2015.

Download: [PDF]

Entry Submitted: 07/15/2015
Entry Accepted: 07/15/2015
Entry Last Modified: 05/25/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society