Relaxations for Binary Polynomial Optimization via Signed Certificates

• 成果类型: Article; Early Access
• 署名作者: Xu, Liding; Liberti, Leo
• 署名单位: Zuse Institute Berlin; Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; Ecole Polytechnique
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0534
• 发表日期: 2026-06-25
• 关键词: binary polynomial optimization; nonnegativity certificate; minimum cut; extended formulation; linear programming; sparsity; semidefinite programming relaxations; moment-sos hierarchy; positive polynomials; Lower bounds; convex; sums; algorithm; REPRESENTATIONS; ENVELOPES; matrices

摘要

We consider the problem of minimizing a polynomial f over the (binary) hyper-cube. 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.