Sum-of-squares hierarchies for binary polynomial optimization

We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial f over the boolean hypercube B^n = {0, 1}^n. This hierarchy provides for each integer r ∈ N a lower bound f(r ) on the minimum f_min of f , given by the largest scalar λ for which the polynomial f −λ is a sum-of-squares on B^n with degree at most 2r . We analyze the quality of these bounds by estimating the worst case error f_min − f(r ) in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed t ∈ [0, 1/2], we can show that this worst-case error in the regime r ≈ t · n is of the order 1/2−√t(1 − t) as n tends to ∞. Our proof combines classical Fourier analysis on B^n with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds f(r ) and another hierarchy of upper bounds f (r ), for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the q-ary cube (Z/qZ)^n. Furthermore, our results apply to the setting of matrix-valued polynomials.

• View at Publisher

Full Text ( Author Manuscript , 630kb )

See Also
inProceedings Sum-of-squares hierarchies for binary polynomial optimization L.F.H. Slot (Lucas) and M. Laurent (Monique)
techReport Sum-of-squares hierarchies for binary polynomial optimization L.F.H. Slot (Lucas) and M. Laurent (Monique)