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

Research output: Book/ReportReportProfessional

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

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

Cite this

de Klerk, E., Laurent, M., & Sun, Z. (2014). An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution. (Preprint at arXiv; Vol. 1407.2108). Ithaca: Cornell University Library.
@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 = "7",
day = "9",
language = "English",
volume = "1407.2108",
series = "Preprint at arXiv",
publisher = "Cornell University Library",

}

de Klerk, E, Laurent, M & Sun, Z 2014, An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution. Preprint at arXiv, vol. 1407.2108, vol. 1407.2108, Cornell University Library, Ithaca.

An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution. / de Klerk, E.; Laurent, M.; Sun, Z.

Ithaca : Cornell University Library, 2014. 17 p. (Preprint at arXiv; Vol. 1407.2108).

Research output: Book/ReportReportProfessional

TY - BOOK

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

AU - de Klerk, E.

AU - Laurent, M.

AU - Sun, Z.

PY - 2014/7/9

Y1 - 2014/7/9

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 et al. (2013) 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 et al. (2013) and improves on previously known O(1/r) bounds in the quadratic case.

M3 - Report

VL - 1407.2108

T3 - Preprint at arXiv

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

PB - Cornell University Library

CY - Ithaca

ER -