2022-01-07

# Sum-of-squares hierarchies for binary polynomial optimization

## Publication

### Publication

*
Mathematical Programming
,
Volume 197
p. 621-
660
*

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.

Additional Metadata | |
---|---|

, , , , , , , | |

doi.org/10.1007/s10107-021-01745-9 | |

Mathematical Programming | |

Mixed-Integer Nonlinear Optimization | |

Organisation | Networks and Optimization |

Slot, L., & Laurent, M. (2022). Sum-of-squares hierarchies for binary polynomial optimization. Mathematical Programming, 197, 621–660. doi:10.1007/s10107-021-01745-9 |

See Also |
---|