An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution
Etienne De Klerk(E.deKlerkuvt.nl)
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.
Keywords: Polynomial optimization over the simplex, Global optimization, Nonlinear optimization
Category 1: Global Optimization
Category 2: Nonlinear Optimization
Citation: Technical report, Tilburg University and CWI, Amsterdam, July 2014.
Entry Submitted: 07/08/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|