An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution
SIAM Journal on Optimization , Volume 25 - Issue 3 p. 1498- 1514
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.  and improves on previously known O(1/r) bounds in the quadratic case.
|Keywords||Polynomial optimization over the simplex, Global optimization, Nonlinear optimization|
|THEME||Logistics (theme 3)|
|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.