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.