Optimization Online


An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution

Etienne De Klerk(E.deKlerk***at***uvt.nl)
Monique Laurent(monique***at***cwi.nl)
Zhao Sun(z.sun***at***uvt.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.

Download: [PDF]

Entry Submitted: 07/08/2014
Entry Accepted: 07/08/2014
Entry Last Modified: 07/08/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society