# On the convergence rate of grid search for polynomial optimization over the simplex

arXiv: https://arxiv.org/abs/1510.01163 · HTML: https://mlsanity.com/paper/1510.01163/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2015.

## Built on by (most cited first, 1 of 1)

- [Inductive randomness predictors: beyond conformal](https://mlsanity.com/paper/2503.02803/) (2025)

## Abstract (arXiv)

We consider the approximate minimization of a given polynomial on the standard simplex, obtained by taking the minimum value over all rational grid points with given denominator r ∈ mathbbN. 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. em 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 the rational minimizer condition is not necessary to obtain the O(1/r2) bound.