## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 621-660 |

Number of pages | 40 |

Journal | Mathematical Programming |

Volume | 197 |

Issue number | 2 |

DOIs | |

Publication status | Published - Feb 2023 |

## Keywords

- Binary polynomial optimization
- Lasserre hierarchy
- Sum-of-squares polynomials
- Fourier analysis
- Krawtchouk polynomials
- Polynomial kernels
- Semidefinite programming
- Polynomial matrices
- RELAXATIONS
- CUT
- REPRESENTATIONS
- COMPLEXITY
- MATRICES