An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution

Research output: Book/ReportReport

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.
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages17
Volume1407.2108
Publication statusPublished - 9 Jul 2014

Publication series

NamePreprint at arXiv
Volume1407.2108

Fingerprint Dive into the research topics of 'An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution'. Together they form a unique fingerprint.

Cite this