Abstract:

Suppose f, g1, ··· ,gm are multivariate polynomials in x ∈ Rn and their
degrees are at most 2d. Consider the problem:
Minimize f (x) subject to g1(x)  0, ··· ,gm(x)  0.
Let fmin (resp., fmax) be the minimum (resp., maximum) of f on the feasible set S,
and fsos be the lower bound of fmin given by Lasserre’s relaxation of order d. This
paper studies its approximation bound. Under a suitable condition on g1, ··· ,gm, we
prove that
(fmax −fsos)  Q(fmax − fmin)
with Q a constant depending only on g1, ··· ,gm but not on f . In particular, if S is
the unit ball, Q = O(nd ); if S is the hypercube, Q = O(n2d ); if S is the boolean set,
Q= O(nd ).

Key words: Approximation bound , Lasserre’s relaxation , Polynomials , Semidefinite programming , Sum of squares