### Abstract

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

Pages (from-to) | 834-853 |

Journal | Mathematics of Operations Research |

Volume | 42 |

Issue number | 3 |

Early online date | Mar 2017 |

DOIs | |

Publication status | Published - Aug 2017 |

### Fingerprint

### Keywords

- polynomial optimization
- bound-constrained optimization
- Lasserre hierarchy

### Cite this

*Mathematics of Operations Research*,

*42*(3), 834-853. https://doi.org/10.1287/moor.2016.0829

}

*Mathematics of Operations Research*, vol. 42, no. 3, pp. 834-853. https://doi.org/10.1287/moor.2016.0829

**Bound-constrained polynomial optimization using only elementary calculations.** / de Klerk, Etienne; Lasserre, J.B.; Laurent, Monique; Sun, Zhao.

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

TY - JOUR

T1 - Bound-constrained polynomial optimization using only elementary calculations

AU - de Klerk, Etienne

AU - Lasserre, J.B.

AU - Laurent, Monique

AU - Sun, Zhao

PY - 2017/8

Y1 - 2017/8

N2 - We provide a monotone nonincreasing sequence of upper bounds fHk(k≥1)fkH(k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in ℝn. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21:864–885] is that only elementary computations are required. For optimization over the hypercube [0, 1]n, we show that the new bounds fHkfkH have a rate of convergence in O(1/k−−√)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 fHkfkH needs only O(nk) elementary calculations.

AB - We provide a monotone nonincreasing sequence of upper bounds fHk(k≥1)fkH(k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in ℝn. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21:864–885] is that only elementary computations are required. For optimization over the hypercube [0, 1]n, we show that the new bounds fHkfkH have a rate of convergence in O(1/k−−√)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 fHkfkH needs only O(nk) elementary calculations.

KW - polynomial optimization

KW - bound-constrained optimization

KW - Lasserre hierarchy

U2 - 10.1287/moor.2016.0829

DO - 10.1287/moor.2016.0829

M3 - Article

VL - 42

SP - 834

EP - 853

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 3

ER -