Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
SIAM Journal on Optimization , Volume 20 - Issue 6 p. 3104- 3120
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)|
|Journal||SIAM Journal on Optimization|
de Klerk, E, & Laurent, M. (2010). Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube. SIAM Journal on Optimization, 20(6), 3104–3120.