Document Open Access Logo

Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems

Authors Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.78.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Adam Kurpisz
Samuli Leppänen
Monaldo Mastrolilli

Cite AsGet BibTex

Adam Kurpisz, Samuli Leppänen, and Monaldo Mastrolilli. Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.78

Abstract

We give two results concerning the power of the Sum-Of-Squares(SoS)/Lasserre hierarchy. For binary polynomial optimization problems of degree 2d and an odd number of variables n, we prove that (n+2d-1)/2 levels of the SoS/Lasserre hierarchy are necessary to provide the exact optimal value. This matches the recent upper bound result by Sakaue, Takeda, Kim and Ito. Additionally, we study a conjecture by Laurent, who considered the linear representation of a set with no integral points. She showed that the Sherali-Adams hierarchy requires n levels to detect the empty integer hull, and conjectured that the SoS/Lasserre rank for the same problem is n-1. We disprove this conjecture and derive lower and upper bounds for the rank.
Keywords
  • SoS/Lasserre hierarchy
  • lift and project methods
  • binary polynomial optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yu Hin Au. A Comprehensive Analysis of Lift-and-Project Methods for Combinatorial Optimization. PhD thesis, University of Waterloo, 2014. Google Scholar
  2. Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In STOC, pages 307-326, 2012. URL: http://dx.doi.org/10.1145/2213977.2214006.
  3. Grigoriy Blekherman. Symmetric sums of squares on the hypercube. Manuscript in preparation, 2015. Google Scholar
  4. William Cook and Sanjeeb Dash. On the matrix-cut rank of polyhedra. Mathematics of Operations Research, 26(1):19-30, 2001. Google Scholar
  5. Gérard Cornuéjols and Yanjun Li. On the rank of mixed 0, 1 polyhedra. In IPCO, pages 71-77. Springer, 2001. Google Scholar
  6. AC Dixon. Summation of a certain series. Proceedings of the London Mathematical Society, 1(1):284-291, 1902. Google Scholar
  7. Hamza Fawzi, James Saunderson, and Pablo A. Parrilo. Sparse sums of squares on finite abelian groups and improved semidefinite lifts. Mathematical Programming, pages 1-43, 2016. URL: http://dx.doi.org/10.1007/s10107-015-0977-z.
  8. Michel X. Goemans and Levent Tunçel. When does the positive semidefiniteness constraint help in lifting procedures? Mathematics of Operations Research, 26(4):796-815, 2001. URL: http://dx.doi.org/10.1287/moor.26.4.796.10012.
  9. Dima Grigoriev. Complexity of positivstellensatz proofs for the knapsack. Computational Complexity, 10(2):139-154, 2001. URL: http://dx.doi.org/10.1007/s00037-001-8192-0.
  10. Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1-2):613-622, 2001. URL: http://dx.doi.org/10.1016/S0304-3975(00)00157-2.
  11. Dima Grigoriev and Nicolai Vorobjov. Complexity of null-and positivstellensatz proofs. Annals of Pure and Applied Logic, 113(1-3):153-160, 2001. URL: http://dx.doi.org/10.1016/S0168-0072(01)00055-0.
  12. Adam Kurpisz, Samuli Leppänen, and Monaldo Mastrolilli. On the hardest problem formulations for the 0/1 lasserre hierarchy. In ICALP, pages 872-885, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_71.
  13. Adam Kurpisz, Samuli Leppänen, and Monaldo Mastrolilli. Sum-of-squares lower bounds for maximally symmetric formulations. In To appear in IPCO, 2016. URL: http://arxiv.org/abs/1407.1746.
  14. Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):796-817, 2001. URL: http://dx.doi.org/10.1137/S1052623400366802.
  15. Monique Laurent. A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Mathematics of Operations Research, 28(3):470-496, 2003. URL: http://dx.doi.org/10.1287/moor.28.3.470.16391.
  16. Monique Laurent. Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Mathematics of Operations Research, 28(4):871-883, 2003. URL: http://dx.doi.org/10.1287/moor.28.4.871.20508.
  17. James R. Lee, Prasad Raghavendra, and David Steurer. Lower bounds on the size of semidefinite programming relaxations. In STOC, pages 567-576, 2015. URL: http://dx.doi.org/10.1145/2746539.2746599.
  18. Troy Lee, Anupam Prakash, Ronald de Wolf, and Henry Yuen. On the sum-of-squares degree of symmetric quadratic functions. In To appear in CCC, 2016. URL: http://arxiv.org/abs/1601.02311.
  19. Claire Mathieu and Alistair Sinclair. Sherali-adams relaxations of the matching polytope. In STOC, pages 293-302, 2009. URL: http://dx.doi.org/10.1145/1536414.1536456.
  20. Raghu Meka, Aaron Potechin, and Avi Wigderson. Sum-of-squares lower bounds for planted clique. In STOC, pages 87-96, 2015. URL: http://dx.doi.org/10.1145/2746539.2746600.
  21. Pablo Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000. Google Scholar
  22. Shinsaku Sakaue, Akiko Takeda, Sunyoung Kim, and Naoki Ito. Exact sdp relaxations with truncated moment matrix for binary polynomial optimization problems. Technical report, University of Tokyo, 2016. URL: http://www.keisu.t.u-tokyo.ac.jp/research/techrep/data/2016/METR16-01.pdf.
  23. Tamon Stephen and Levent Tunçel. On a representation of the matching polytope via semidefinite liftings. Mathematics of Operations Research, 24(1):1-7, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact