Relaxations for Binary Polynomial Optimization via Signed Certificates

We consider the problem of minimizing a polynomial f over the (binary) hypercube. We show that, for a specific set of polynomials, their binary nonnegativity (i.e., on the hypercube) can be checked in polynomial time via minimum cut algorithms, from which we construct a linear programming representation for this set of polynomials. We categorize binary polynomials according to their signed support patterns and develop parameterized linear programming representations for binary nonnegative polynomials. This allows the construction of signed certificates of binary nonnegativity with adjustable signed support patterns and representation complexities; and we propose a method for minimizing f by decomposing it as a sum of signed certificates. This method yields new hierarchies of linear programming relaxations for binary polynomial optimization. Moreover, because our decomposition depends only on the support of f, the new hierarchies are sparsity-preserving. Funding: Most of the work done by the first author on this paper occurred while he was a PhD student at Laboratoire d’Informatique de l’École Polytechnique, Centre National de la Recherche Scientifique, École Polytechnique, Institut Polytechnique de Paris (IPP), sponsored by a grant of the IPP doctoral school, for which both authors are grateful.