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

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 Schmuedgen (1991). The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates on the hypercube.

Citation

Preprint, Tilburg University, The Netherlands, April 2010

Article

Download

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