2017-03-01
On the convergence rate of grid search for polynomial optimization over the simplex
Publication
Publication
Optimization Letters
,
Volume 11
-
Issue 3
p. 597-
608
We consider the approximate minimization of a given polynomial on the s
tandard 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.
SIAM J. Optim. 25(3) 1498–1514 (2015)] that the relative accuracy of this approximation depends on
r as O(1/r2) if there exists a rational global minimizer. In this note we show that th
e rational minimizer condition is not necessary to obtain the O(1/r2) bound.
| Additional Metadata | |
|---|---|
| Keywords | Polynomial optimization · Taylor’s theorem - grid search |
| MSC | Nonlinear programming (msc 90C30) |
| THEME | Logistics (theme 3) |
| Publisher | Springer |
| Persistent URL | dx.doi.org/10.1007/s11590-016-1023-7 |
| Journal | Optimization Letters |
| Project | Approximation Algorithms, Quantum Information and Semidefinite Optimization |
| Grant | This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/617.001.351 - Approximation Algorithms, Quantum Information and Semidefinite Optimization |
| Citation |
de Klerk, E, Laurent, M, Sun, Z, & Vera, J.C. (2017). On the convergence rate of grid search for polynomial optimization over the simplex. Optimization Letters, 11(3), 597–608. doi:10.1007/s11590-016-1023-7
|
