Relaxations for binary polynomial optimization via signed certificates

Liding Xu, Leo Liberti

We consider the problem of minimizing a polynomial $f$ over the (binary) hypercube. We show that, for a specific set of polynomials, their binary non-negativity (i.e. on the hyperc…