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 Schmu ̈dgen . The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates on the hypercube.
|Keywords||Positivstellensatz, positive polynomial, sum of squares of polynomials, bound constrained optimization of polynomials, multivariate Bernstein approximation, semidefinite programming|
|MSC||Abstract computational complexity for mathematical programming problems (msc 90C60)|
|THEME||Logistics (theme 3)|
|Publisher||Mathematical Programming Society|
de Klerk, E, & Laurent, M. (2010). Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube. Optimization Online. Mathematical Programming Society.