Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube

Research output: Contribution to journalArticleScientificpeer-review

240 Downloads (Pure)

Abstract

We consider the problem of minimizing a polynomial on the hypercube $[0,1]^n$ and derive new error bounds for the hierarchy of semidefinite programming approximations to this problem corresponding to the Positivstellensatz of Schmüdgen [Math. Ann., 289 (1991), pp. 203–206]. The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates on the hypercube.
Original languageEnglish
Pages (from-to)3104-3120
JournalSIAM Journal on Optimization
Volume20
Issue number6
Publication statusPublished - 2010

Fingerprint

Semidefinite Programming
Hypercube
Error Bounds
Polynomials
Polynomial
Certificate
Approximation
Positivity
Hierarchy

Cite this

@article{619d965877df4b5e986809aca0615347,
title = "Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube",
abstract = "We consider the problem of minimizing a polynomial on the hypercube $[0,1]^n$ and derive new error bounds for the hierarchy of semidefinite programming approximations to this problem corresponding to the Positivstellensatz of Schm{\"u}dgen [Math. Ann., 289 (1991), pp. 203–206]. The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates on the hypercube.",
author = "{de Klerk}, E. and M. Laurent",
year = "2010",
language = "English",
volume = "20",
pages = "3104--3120",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "6",

}

Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube. / de Klerk, E.; Laurent, M.

In: SIAM Journal on Optimization, Vol. 20, No. 6, 2010, p. 3104-3120.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube

AU - de Klerk, E.

AU - Laurent, M.

PY - 2010

Y1 - 2010

N2 - We consider the problem of minimizing a polynomial on the hypercube $[0,1]^n$ and derive new error bounds for the hierarchy of semidefinite programming approximations to this problem corresponding to the Positivstellensatz of Schmüdgen [Math. Ann., 289 (1991), pp. 203–206]. The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates on the hypercube.

AB - We consider the problem of minimizing a polynomial on the hypercube $[0,1]^n$ and derive new error bounds for the hierarchy of semidefinite programming approximations to this problem corresponding to the Positivstellensatz of Schmüdgen [Math. Ann., 289 (1991), pp. 203–206]. The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates on the hypercube.

M3 - Article

VL - 20

SP - 3104

EP - 3120

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 6

ER -