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

Research output: Contribution to journalArticleScientificpeer-review

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, Laurent, and Sun [Math. Program., 151 (2015), pp. 433--457]. and improves on previously known $O(1/r)$ bounds in the quadratic case.
Original languageEnglish
Pages (from-to)1498-1514
Number of pages17
JournalSIAM Journal on Optimization
Volume25
Issue number3
DOIs
Publication statusPublished - 2015

Fingerprint

Hypergeometric Distribution
Multivariate Distribution
Error Analysis
Error analysis
Convergence Rate
Polynomials
Global Minimizer
Polynomial
Stable Set
Optimization
Quadratic Polynomial
Rational Approximation
Rational Points
Denominator
Sun
Graph theory
NP-complete problem
Grid

Cite this

@article{2e0a5f820d974d5e94b565885ef009f4,
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, Laurent, and Sun [Math. Program., 151 (2015), pp. 433--457]. and improves on previously known $O(1/r)$ bounds in the quadratic case.",
author = "{de Klerk}, Etienne and Monique Laurent and Zhao Sun",
year = "2015",
doi = "10.1137/140976650",
language = "English",
volume = "25",
pages = "1498--1514",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution. / de Klerk, Etienne; Laurent, Monique; Sun, Zhao.

In: SIAM Journal on Optimization, Vol. 25, No. 3, 2015, p. 1498-1514.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - de Klerk, Etienne

AU - Laurent, Monique

AU - Sun, Zhao

PY - 2015

Y1 - 2015

N2 - 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, Laurent, and Sun [Math. Program., 151 (2015), pp. 433--457]. and improves on previously known $O(1/r)$ bounds in the quadratic case.

AB - 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, Laurent, and Sun [Math. Program., 151 (2015), pp. 433--457]. and improves on previously known $O(1/r)$ bounds in the quadratic case.

U2 - 10.1137/140976650

DO - 10.1137/140976650

M3 - Article

VL - 25

SP - 1498

EP - 1514

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 3

ER -