### Abstract

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

Pages (from-to) | 1498-1514 |

Number of pages | 17 |

Journal | SIAM Journal on Optimization |

Volume | 25 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2015 |

### Fingerprint

### Cite this

}

*SIAM Journal on Optimization*, vol. 25, no. 3, pp. 1498-1514. https://doi.org/10.1137/140976650

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

Research output: Contribution to journal › Article › Scientific › peer-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 -