### Abstract

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

Place of Publication | Ithaca |

Publisher | Cornell University Library |

Number of pages | 23 |

Publication status | Published - 15 Jul 2015 |

### Publication series

Name | arXiv |
---|---|

Volume | 1507.04404 |

### Fingerprint

### Keywords

- polynomial optimization
- bound-constrained optimization
- Lasserre hierarchy

### Cite this

*Bound-Constrained Polynomial Optimization Using Only Elementary Calculations*. (arXiv; Vol. 1507.04404). Ithaca: Cornell University Library.

}

**Bound-Constrained Polynomial Optimization Using Only Elementary Calculations.** / de Klerk, Etienne; Lasserre, J.B.; Laurent, Monique; Sun, Zhao.

Research output: Working paper › Other research output

TY - UNPB

T1 - Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

AU - de Klerk, Etienne

AU - Lasserre, J.B.

AU - Laurent, Monique

AU - Sun, Zhao

PY - 2015/7/15

Y1 - 2015/7/15

N2 - We provide a monotone non increasing sequence of upper bounds fHk (k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864--885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds fHk have a rate of convergence in O(1/k√). Moreover we show a stronger convergence rate in O(1/k) for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator k produces bounds with a rate of convergence in O(1/k2), but at the cost of O(kn) function evaluations, while the new bound fHk needs only O(nk) elementary calculations.

AB - We provide a monotone non increasing sequence of upper bounds fHk (k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864--885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds fHk have a rate of convergence in O(1/k√). Moreover we show a stronger convergence rate in O(1/k) for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator k produces bounds with a rate of convergence in O(1/k2), but at the cost of O(kn) function evaluations, while the new bound fHk needs only O(nk) elementary calculations.

KW - polynomial optimization

KW - bound-constrained optimization

KW - Lasserre hierarchy

UR - http://arxiv.org/abs/1507.04404

M3 - Working paper

T3 - arXiv

BT - Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

PB - Cornell University Library

CY - Ithaca

ER -