[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3597066.3597075acmotherconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
research-article
Open access

A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization

Published: 24 July 2023 Publication History

Abstract

The moment-sum-of-squares (moment-SOS) hierarchy is one of the most celebrated and widely applied methods for approximating the minimum of an n-variate polynomial over a feasible region defined by polynomial (in)equalities. A key feature of the hierarchy is that, at a fixed level, it can be formulated as a semidefinite program of size polynomial in the number of variables n. Although this suggests that it may therefore be computed in polynomial time, this is not necessarily the case. Indeed, as O’Donnell [16] and later Raghavendra & Weitz [20] show, there exist examples where the sos-representations used in the hierarchy have exponential bit-complexity. We study the computational complexity of the moment-SOS hierarchy, complementing and expanding upon earlier work of Raghavendra & Weitz [20]. In particular, we establish algebraic and geometric conditions under which polynomial-time computation is guaranteed to be possible.

References

[1]
Saugata Basu and Antonio Lerario. 2022. Hausdorff approximations and volume of tubes of singular algebraic sets. Math. Ann. (2022). https://doi.org/10.1007/s00208-022-02458-w
[2]
Saugata Basu, Richard Pollack, and Marie-Françoise Roy. 2006. Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics). Springer-Verlag, Berlin, Heidelberg.
[3]
Aharon Ben-Tal and Arkadi Nemirovski. 2001. Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics.
[4]
Sylvain Chevillard, John Harrison, Mioara Maria Joldes, and Christoph Lauter. 2011. Efficient and accurate computation of upper bounds of approximation errors. Theoretical Computer Science 416 (2011), 1523–1543.
[5]
Etienne de Klerk and Monique Laurent. 2019. A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis. In World Women in Mathematics 2018: Proceedings of the First World Meeting for Women in Mathematics (WM)². Springer International Publishing, Cham, 17–56.
[6]
Etienne de Klerk and Frank Vallentin. 2016. On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming. SIAM Journal on Optimization 26, 3 (2016), 1944–1961. https://doi.org/10.1137/15M103114X arXiv:https://doi.org/10.1137/15M103114X
[7]
Peter Gács and Laszlo Lovász. 1981. Khachiyan’s algorithm for linear programming. In Mathematical Programming at Oberwolfach, H. König, B. Korte, and K. Ritter (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 61–68. https://doi.org/10.1007/BFb0120921
[8]
Martin Grötschel, László Lovász, and Alexander Schrijver. 1981. The ellipsoid method and its consequences in combinatorial optimization.Combinatorica 1, 2 (1981), 169–197.
[9]
Martin Grötschel, László Lovász, and Alexander Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization. Springer Berlin, Heidelberg.
[10]
Fritz John. 1948. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948. Interscience Publishers, Inc., New York, N.Y., 187–204.
[11]
Cédric Josz and Didier Henrion. 2016. Strong duality in Lasserre’s hierarchy for polynomial optimization. Opt. Lett. 10 (2016), 3–10.
[12]
Jean-Bernard Lasserre. 2001. Global Optimization with Polynomials and the Problem of Moments. SIAM Journal on Optimization 11, 3 (2001), 796–817. https://doi.org/10.1137/S1052623400366802 arXiv:https://doi.org/10.1137/S1052623400366802
[13]
Monique Laurent. 2009. Sums of Squares, Moment Matrices and Optimization Over Polynomials. In Emerging Applications of Algebraic Geometry, Mihai Putinar and Seth Sullivant (Eds.). Springer New York, New York, NY, 157–270. https://doi.org/10.1007/978-0-387-09686-5_7
[14]
Martin Lotz. 2015. On the volume of tubular neighborhoods of real algebraic varieties. Proc. Amer. Math. Soc. 143, 5 (2015), 1875–1889.
[15]
Victor Magron, Mohab Safey El Din, and Markus Schweighofer. 2019. Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials. Journal of Symbolic Computation 93 (2019), 200–220.
[16]
Ryan O’Donnell. 2017. SOS Is Not Obviously Automatizable, Even Approximately. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 67), Christos H. Papadimitriou (Ed.). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 59:1–59:10. https://doi.org/10.4230/LIPIcs.ITCS.2017.59
[17]
Pablo Parrilo. 2003. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming Series B 96 (2003), 293–320.
[18]
Gábor Pataki and Aleksandr Touzov. 2021. How do exponential size solutions arise in semidefinite programming?www.arxiv.org/abs/2103.00041 (2021). https://doi.org/10.48550/arXiv.2103.00041
[19]
Alexander Prestel and Charles N. Delzell. 2001. Positive Polynomials – From Hilbert’s 17th Problem to Real Algebra. Springer, Berlin.
[20]
Prasad Raghavendra and Benjamin Weitz. 2017. On the Bit Complexity of Sum-of-Squares Proofs. ICALP 80 (2017), 1–13.
[21]
Motakuri V. Ramana. 1997. An exact duality theory for semidefinite programming and its complexity implications. Mathematical Programming 77, 1 (1997), 129–162.
[22]
James Renegar. 1992. On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. Journal of Symbolic Computation 13, 3 (1992), 255–299. https://doi.org/10.1016/S0747-7171(10)80003-3
[23]
Markus Schweighofer. 1999. Algorithmische Beweise für Nichtnegativ- und Positivstellensätze. Master’s thesis. Universität Passau.
[24]
Richard Wongkew. 1993. Volumes of tubular neighbourhoods of real algebraic varieties.Pacific J. Math. 159, 1 (1993), 177 – 184. https://doi.org/pjm/1102634385

Cited By

View all
  • (2024)Convergence rates for sums-of-squares hierarchies with correlative sparsityMathematical Programming10.1007/s10107-024-02071-6Online publication date: 25-Mar-2024

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation
July 2023
567 pages
ISBN:9798400700392
DOI:10.1145/3597066
This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 July 2023

Check for updates

Author Tags

  1. computational complexity
  2. moment-SOS hierarchy
  3. moments
  4. polynomial optimization
  5. semidefinite programming
  6. sums of squares

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Conference

ISSAC 2023

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)171
  • Downloads (Last 6 weeks)14
Reflects downloads up to 12 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Convergence rates for sums-of-squares hierarchies with correlative sparsityMathematical Programming10.1007/s10107-024-02071-6Online publication date: 25-Mar-2024

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

HTML Format

View this article in HTML Format.

HTML Format

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media