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.
Polynomial optimization over the simplex, Global optimization, Nonlinear optimization
Logistics (theme 3)
S.I.A.M.
SIAM Journal on Optimization
Approximation Algorithms, Quantum Information and Semidefinite Optimization
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
Networks and 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.