Worst-case examples for Lasserre's measure--based hierarchy for\n polynomial optimization on the hypercube

2018/04/16 by Etienne de Klerk, de Klerk, Etienne, Monique Laurent +1
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Mathematical functions and polynomials #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.1804.05524

Abstract

We study the convergence rate of a hierarchy of upper bounds for polynomial\noptimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp.\n864-885], and a related hierarchy by De Klerk, Hess and Laurent [SIAM J. Optim.\n27(1), (2017) pp. 347-367]. For polynomial optimization over the hypercube, we\nshow a refined convergence analysis for the first hierarchy. We also show lower\nbounds on the convergence rate for both hierarchies on a class of examples.\nThese lower bounds match the upper bounds and thus establish the true rate of\nconvergence on these examples. Interestingly, these convergence rates are\ndetermined by the distribution of extremal zeroes of certain families of\northogonal polynomials.\n

Related

• Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube
• Convergence analysis for Lasserre's measure--based hierarchy of upper bounds for polynomial optimization
• Bound-constrained polynomial optimization using only elementary calculations
• Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
• Comparison of Lasserre's measure--based bounds for polynomial optimization to bounds obtained by simulated annealing