@book{883f61e704164d94aa7f60cbe4fc627a,
title = "An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution",
abstract = "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. (2013) and improves on previously known O(1/r) bounds in the quadratic case. ",
author = "{de Klerk}, E. and M. Laurent and Z. Sun",
year = "2014",
month = jul,
day = "9",
language = "English",
volume = "1407.2108",
series = "Preprint at arXiv",
publisher = "Cornell University Library",
}