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

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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
Original languageEnglish
Pages (from-to)597-608
JournalOptimization Letters
Volume11
Issue number3
DOIs
Publication statusPublished - Mar 2017

Fingerprint

Rate of Convergence
Grid
Polynomial
Optimization
Hypergeometric Distribution
Global Minimizer
Multivariate Distribution
Denominator
Sun
Minimizer
Error Analysis
Necessary
Approximation
Standards

Keywords

  • Polynomial optimization
  • Taylor’s theorem - grid search

Cite this

@article{81d31b6b975746cab08bdc0d73a38e86,
title = "On the convergence rate of grid search for polynomial optimization over the simplex",
abstract = "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",
keywords = "Polynomial optimization , Taylor’s theorem - grid search",
author = "{de Klerk}, Etienne and Monique Laurent and Zhao Sun and {Vera Lizcano}, Juan",
year = "2017",
month = "3",
doi = "10.1007/s11590-016-1023-7",
language = "English",
volume = "11",
pages = "597--608",
journal = "Optimization Letters",
issn = "1862-4472",
publisher = "Springer Verlag",
number = "3",

}

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

In: Optimization Letters, Vol. 11, No. 3, 03.2017, p. 597-608.

Research output: Contribution to journalArticleScientificpeer-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 -