We consider the approximate minimization of a given polynomial on the s tandard simplex, obtained by taking the minimum value over all rational grid points with given denominator r∈N. It was shown in [De Klerk, E., Laurent, M., Sun, Z.: An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution. SIAM J. Optim. 25(3) 1498–1514 (2015)] that the relative accuracy of this approximation depends on r as O(1/r2) if there exists a rational global minimizer. In this note we show that th e rational minimizer condition is not necessary to obtain the O(1/r2) bound.
Springer
doi.org/10.1007/s11590-016-1023-7
Optimization Letters
Approximation Algorithms, Quantum Information and Semidefinite Optimization
Networks and Optimization

de Klerk, E., Laurent, M., Sun, Z., & Vera, J. C. (2017). On the convergence rate of grid search for polynomial optimization over the simplex. Optimization Letters, 11(3), 597–608. doi:10.1007/s11590-016-1023-7