### Abstract

Original language | English |
---|---|

Place of Publication | Ithaca |

Publisher | Cornell University Library |

Number of pages | 17 |

Volume | 1407.2108 |

Publication status | Published - 9 Jul 2014 |

### Publication series

Name | Preprint at arXiv |
---|---|

Volume | 1407.2108 |

### Fingerprint

### Cite this

*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.

}

*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.

Research output: Book/Report › Report › Professional

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 -