{
  "id": "1510.01163",
  "version": "v1",
  "published": "2015-10-05T14:13:47.000Z",
  "updated": "2015-10-05T14:13:47.000Z",
  "title": "On the convergence rate of grid search for polynomial optimization over the simplex",
  "authors": [
    "Etienne de Klerk",
    "Monique Laurent",
    "Zhao Sun",
    "Juan C. Vera"
  ],
  "comment": "10 pages, 2 tables",
  "categories": [
    "math.OC"
  ],
  "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} \\in \\mathbb{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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-10-05T14:13:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C30",
      "90C60"
    ],
    "keywords": [
      "polynomial optimization",
      "grid search",
      "convergence rate",
      "rational global minimizer",
      "multivariate hypergeometric distribution"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}