We consider the problem of minimizing a given multivariate polynomial f over the hypercube [-1,1]^n. An idea, introduced by Lasserre, is to find a probability distribution on the hypercube with polynomial density function h (of given degree r) that minimizes the expectation of f over the hypercube with respect to this probability distribution. It is known that, for the Lebesgue measure one may show an error bound in 1/sqrt{r} if h is a sum-of-squares density, and an error bound in 1/r if h is the density of a beta distribution. In this paper, we show another probability distribution that permits to show an error bound in 1/r^2 when selecting a density function h with a Schmuedgen-type sum-of-squares decomposition. The convergence rate analysis relies on the theory of polynomial kernels, and in particular on Jackson kernels. We also show that the resulting upper bounds may be computed as generalized eigenvalue problems, as is also the case for sum-of-squares densities
Additional Metadata
Keywords box-constrained global optimization, polynomial optimization, Jackson kernel, semidenite programming, generalized eigenvalue problem, sum-of-squares polynomial
THEME Logistics (theme 3)
Publisher Cornell University Library
Series arXiv.org e-Print archive
Project Approximation Algorithms, Quantum Information and Semidefinite Optimization
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/617.001.351 - Approximation Algorithms, Quantum Information and Semidefinite Optimization
Citation
de Klerk, E, Hess, R, & Laurent, M. (2016). Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization. arXiv.org e-Print archive. Cornell University Library.