Sum-of-squares hierarchy lower bounds for symmetric formulations

• 成果类型: Article
• 署名作者: Kurpisz, Adam; Leppanen, Samuli; Mastrolilli, Monaldo
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; Universita della Svizzera Italiana
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01398-9
• 发表日期: 2020
• 页码: 369-397
• 关键词: Optimization; proofs; rank

摘要

We introduce a method for proving Sum-of-Squares (SoS)/Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of well-behaved univariate polynomial inequalities. We illustrate the technique on two problems, one unconstrained and the other with constraints. More precisely, we give a short elementary proof of Grigoriev/Laurent lower bound for finding the integer cut polytope of the complete graph. We also show that the SoS hierarchy requires a non-constant number of rounds to improve the initial integrality gap of 2 for theMin-Knapsacklinear program strengthened with cover inequalities.