We study the minimization of fixed-degree polynomials over the simplex. This problem is well-known to be NP-hard, as it contains the maximum stable set problem in graph theory as a special case. In this paper, we consider a rational approximation by taking the minimum over the regular grid, which consists of rational points with denominator r (for given r). We show that the associated convergence rate is O(1/r^2 ) for quadratic polynomials. For general polynomials, if there exists a rational global minimizer over the simplex, we show that the convergence rate is also of the order O(1/r^2 ). Our results answer a question posed by De Klerk et al. [9] and improves on previously known O(1/r) bounds in the quadratic case.
Additional Metadata
Keywords Polynomial optimization over the simplex, Global optimization, Nonlinear optimization
THEME Logistics (theme 3)
Publisher S.I.A.M.
Journal SIAM Journal on Optimization
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
de Klerk, E, Laurent, M, & Sun, Z. (2015). An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution. SIAM Journal on Optimization, 25(3), 1498–1514.