Document Open Access Logo

Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials

Authors Mareike Dressler, Adam Kurpisz, Timo de Wolff

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.82.pdf
  • Filesize: 0.59 MB
  • 17 pages

Document Identifiers

Author Details

Mareike Dressler
  • Goethe-Universität, FB 12 - Institut für Mathematik, Robert-Mayer-Str. 6-10, 60054 Frankfurt am Main, Germany
Adam Kurpisz
  • ETH Zürich, Department of Mathematics, Rämistrasse 101, 8092 Zürich, Switzerland
Timo de Wolff
  • Technische Universität Berlin, Institut für Mathematik, Straße des 17. Juni 136, 10623 Berlin, Germany

Funding

  • Kurpisz, Adam: Swiss National Science Foundation project PZ00P2_174117 "Theory and Applications of Linear and Semidefinite Relaxations for Combinatorial Optimization Problems"
  • de Wolff, Timo: DFG grant WO 2206/1-1

Cite As Get BibTex

Mareike Dressler, Adam Kurpisz, and Timo de Wolff. Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 82:1-82:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.82

Abstract

Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube. One particularly successful way to prove complexity bounds for these types of problems are based on sums of squares (SOS) as nonnegativity certificates. In this article, we initiate optimization over the boolean hypercube via a recent, alternative certificate called sums of nonnegative circuit polynomials (SONC). We show that key results for SOS based certificates remain valid: First, there exists a SONC certificate of degree at most n+d for polynomials which are nonnegative over the n-variate boolean hypercube with constraints of degree d. Second, if there exists a degree d SONC certificate for nonnegativity of a polynomial over the boolean hypercube, then there also exists a short degree d SONC certificate, that includes at most n^O(d) nonnegative circuit polynomials. Finally, we show certain differences between SOS and SONC cones: we prove that, in contrast to SOS, the SONC cone is not closed under taking affine transformation of variables and that for SONC there does not exist an equivalent to Putinar's Positivestellensatz. We discuss these results both from algebraic and optimization perspective.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Convex optimization
Keywords
  • nonnegativity certificate
  • hypercube optimization
  • sums of nonnegative circuit polynomials
  • relative entropy programming
  • sums of squares

Metrics

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

References

  1. S. Arora, B. Barak, and D. Steurer. Subexponential algorithms for unique games and related problems. In FOCS, pages 563-572, 2010. Google Scholar
  2. S. Arora, S. Rao, and U. V. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1-5:37, 2009. URL: http://dx.doi.org/10.1145/1502793.1502794.
  3. B. Barak, S. B. Hopkins, J. A. Kelner, P. Kothari, A. Moitra, and A. Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 428-437, 2016. Google Scholar
  4. B. Barak, P. Raghavendra, and D. Steurer. Rounding semidefinite programming hierarchies via global correlation. In FOCS, pages 472-481, 2011. Google Scholar
  5. B. Barak and D. Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. Electronic Colloquium on Computational Complexity (ECCC), 21:59, 2014. Google Scholar
  6. Boaz Barak, Jonathan A. Kelner, and David Steurer. Dictionary learning and tensor decomposition via the sum-of-squares method. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 143-151, 2015. Google Scholar
  7. Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, pages 417-445, 2016. Google Scholar
  8. M. H. Bateni, M. Charikar, and V. Guruswami. Maxmin allocation via degree lower-bounded arborescences. In STOC, pages 543-552, 2009. URL: http://dx.doi.org/10.1145/1536414.1536488.
  9. Grigoriy Blekherman. There are significantly more nonegative polynomials than sums of squares. Israel Journal of Mathematics, 153(1):355-380, Dec 2006. Google Scholar
  10. V. Chandrasekaran and P. Shah. Relative entropy optimization and its applications. Math. Program., 161(1-2):1-32, 2017. Google Scholar
  11. K. K. H. Cheung. Computation of the Lasserre ranks of some polytopes. Math. Oper. Res., 32(1):88-94, 2007. Google Scholar
  12. E. Chlamtac. Approximation algorithms using hierarchies of semidefinite programming relaxations. In FOCS, pages 691-701, 2007. Google Scholar
  13. E. Chlamtac and G. Singh. Improved approximation guarantees through higher levels of SDP hierarchies. In APPROX-RANDOM, pages 49-62, 2008. Google Scholar
  14. E. Chlamtac and M. Tulsiani. Convex relaxations and integrality gaps. In to appear in Handbook on semidefinite, conic and polynomial optimization. Springer, 2012. Google Scholar
  15. D.A. Cox and J. Little D. O'Shea. Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015. An introduction to computational algebraic geometry and commutative algebra. Google Scholar
  16. M. Cygan, F. Grandoni, and M. Mastrolilli. How to sell hyperedges: The hypermatching assignment problem. In SODA, pages 342-351, 2013. Google Scholar
  17. W. F. de la Vega and C. Kenyon-Mathieu. Linear programming relaxations of maxcut. In SODA, pages 53-61, 2007. Google Scholar
  18. T. de Wolff. Amoebas, nonnegative polynomials and sums of squares supported on circuits. Oberwolfach Rep., 23:53-56, 2015. Google Scholar
  19. M. Dressler, S. Iliman, and T. de Wolff. A Positivstellensatz for Sums of Nonnegative Circuit Polynomials. SIAM J. Appl. Algebra Geom., 1(1):536-555, 2017. Google Scholar
  20. M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach., 42(6):1115-1145, 1995. Google Scholar
  21. D. Grigoriev. Complexity of positivstellensatz proofs for the knapsack. Comput. Complexity, 10(2):139-154, 2001. Google Scholar
  22. D. Grigoriev, E. A. Hirsch, and D. V. Pasechnik. Complexity of semi-algebraic proofs. In STACS, pages 419-430, 2002. Google Scholar
  23. D. Grigoriev and N. Vorobjov. Complexity of null-and positivstellensatz proofs. Ann. Pure App. Logic, 113(1-3):153-160, 2001. Google Scholar
  24. V. Guruswami and A. K. Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In FOCS, pages 482-491, 2011. Google Scholar
  25. D. Hilbert. Uber die darstellung definiter formen als summe von formen-quadraten. Annals of Mathematics, 32:342–350, 1888. Google Scholar
  26. Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 178-191, 2016. Google Scholar
  27. S. Iliman and T. de Wolff. Amoebas, nonnegative polynomials and sums of squares supported on circuits. Res. Math. Sci., 3:3:9, 2016. Google Scholar
  28. Pravesh Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, 2018. Google Scholar
  29. Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 132-145, 2017. Google Scholar
  30. M. Kreuzer and L. Robbiano. Computational commutative algebra. 1. Springer-Verlag, Berlin, 2000. Google Scholar
  31. A. Kurpisz, S. Leppänen, and M. Mastrolilli. Sum-of-squares hierarchy lower bounds for symmetric formulations. In Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, pages 362-374, 2016. Google Scholar
  32. A. Kurpisz, S. Leppänen, and M. Mastrolilli. On the hardest problem formulations for the 0/1 lasserre hierarchy. Math. Oper. Res., 42(1):135-143, 2017. Google Scholar
  33. A. Kurpisz, S. Leppänen, and M. Mastrolilli. An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem. Math. Program., 166(1-2):1-17, 2017. Google Scholar
  34. J.B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796-817, 2000/01. Google Scholar
  35. M. Laurent. A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res., 28(3):470-496, 2003. Google Scholar
  36. M. Laurent. Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res., 28(4):871-883, 2003. Google Scholar
  37. M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry, volume 149 of IMA Vol. Math. Appl., pages 157-270. Springer, New York, 2009. Google Scholar
  38. M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry, volume 149 of IMA Vol. Math. Appl., pages 157-270. Springer, New York, 2009. Google Scholar
  39. J. R. Lee, P. Raghavendra, and D. Steurer. Lower bounds on the size of semidefinite programming relaxations. In STOC, pages 567-576, 2015. Google Scholar
  40. L. Lovász. On the shannon capacity of a graph. IEEE Trans. Inform. Theory, 25:1-7, 1979. Google Scholar
  41. A. Magen and M. Moharrami. Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy. In APPROX-RANDOM, pages 258-271, 2009. Google Scholar
  42. M. Mastrolilli. High degree sum of squares proofs, bienstock-zuckerberg hierarchy and CG cuts. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 405-416, 2017. Google Scholar
  43. R. Meka, A. Potechin, and A. Wigderson. Sum-of-squares lower bounds for planted clique. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 87-96, 2015. Google Scholar
  44. T.S. Motzkin. The arithmetic-geometric inequality. Symposium on Inequalities, pages 205-224, 1967. cited By 1. Google Scholar
  45. Y. Nesterov. Global quadratic optimization via conic relaxation, pages 363-384. Kluwer Academic Publishers, 2000. Google Scholar
  46. Y. Nesterov and A. Nemirovskii. Interior Point Polynomial Algorithms in Convex Programming. Studies in Applied Mathematics. Society for Industrial and Applied Mathematics, 1994. Google Scholar
  47. J. Oxley. Matroid theory, volume 2 of Oxford Graduate Texts in Mathematics. Oxford University Press, 2011. Google Scholar
  48. P. Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000. Google Scholar
  49. Aaron Potechin and David Steurer. Exact tensor completion with sum-of-squares. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 1619-1673, 2017. Google Scholar
  50. M. Putinar. Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J., 42(3):969-984, 1993. Google Scholar
  51. P. Raghavendra and N. Tan. Approximating csps with global cardinality constraints using sdp hierarchies. In SODA, pages 373-387, 2012. Google Scholar
  52. B. Reznick. Forms derived from the arithmetic-geometric inequality. Math. Ann., 283(3):431-464, 1989. Google Scholar
  53. B. Reznick. Some concrete aspects of Hilbert’s 17th Problem. In Real algebraic geometry and ordered structures (Baton Rouge, LA, 1996), volume 253 of Contemp. Math., pages 251-272. Amer. Math. Soc., Providence, RI, 2000. Google Scholar
  54. Tselil Schramm and David Steurer. Fast and robust tensor decomposition with applications to dictionary learning. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 1760-1793, 2017. Google Scholar
  55. N. Shor. Class of global minimum bounds of polynomial functions. Cybernetics, 23(6):731-734, 1987. Google Scholar
  56. Johan Thapper and Stanislav Zivny. The limits of SDP relaxations for general-valued csps. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1-12, 2017. Google Scholar
  57. G.M. Ziegler. Lectures on Polytopes. Springer Verlag, 2007. 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 About DROPS Imprint Privacy Contact