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 [26]. The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates on the hypercube.
Additional Metadata
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 S.I.A.M.
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.