### Abstract

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

Pages (from-to) | 597-608 |

Journal | Optimization Letters |

Volume | 11 |

Issue number | 3 |

DOIs | |

Publication status | Published - Mar 2017 |

### Fingerprint

### Keywords

- Polynomial optimization
- Taylor’s theorem - grid search

### Cite this

}

*Optimization Letters*, vol. 11, no. 3, pp. 597-608. https://doi.org/10.1007/s11590-016-1023-7

**On the convergence rate of grid search for polynomial optimization over the simplex.** / de Klerk, Etienne; Laurent, Monique; Sun, Zhao; Vera Lizcano, Juan.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - On the convergence rate of grid search for polynomial optimization over the simplex

AU - de Klerk, Etienne

AU - Laurent, Monique

AU - Sun, Zhao

AU - Vera Lizcano, Juan

PY - 2017/3

Y1 - 2017/3

N2 - We consider the approximate minimization of a given polynomial on the standard simplex, obtained by taking the minimum value over all rational grid points with given denominator r∈N . It was shown in [De Klerk, E., Laurent, M., Sun, Z.: An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution. {\em SIAM J. Optim.} 25(3) 1498--1514 (2015)] that the relative accuracy of this approximation depends on r as O(1/r 2 ) if there exists a rational global minimizer. In this note we show that the rational minimizer condition is not necessary to obtain the O(1/r 2 ) bound

AB - We consider the approximate minimization of a given polynomial on the standard simplex, obtained by taking the minimum value over all rational grid points with given denominator r∈N . It was shown in [De Klerk, E., Laurent, M., Sun, Z.: An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution. {\em SIAM J. Optim.} 25(3) 1498--1514 (2015)] that the relative accuracy of this approximation depends on r as O(1/r 2 ) if there exists a rational global minimizer. In this note we show that the rational minimizer condition is not necessary to obtain the O(1/r 2 ) bound

KW - Polynomial optimization

KW - Taylor’s theorem - grid search

U2 - 10.1007/s11590-016-1023-7

DO - 10.1007/s11590-016-1023-7

M3 - Article

VL - 11

SP - 597

EP - 608

JO - Optimization Letters

JF - Optimization Letters

SN - 1862-4472

IS - 3

ER -