A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
From MaRDI portal
Publication:6081938
DOI10.1145/3597066.3597075arXiv2305.14944OpenAlexW4383213595WikidataQ131124578 ScholiaQ131124578MaRDI QIDQ6081938
Sven C. Polak, Lucas Slot, Sander Gribling
Publication date: 3 November 2023
Published in: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2305.14944
momentscomputational complexitysums of squaressemidefinite programmingpolynomial optimizationmoment-SOS hierarchy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient and accurate computation of upper bounds of approximation errors
- The ellipsoid method and its consequences in combinatorial optimization
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- Geometric algorithms and combinatorial optimization.
- Volumes of tubular neighbourhoods of real algebraic varieties
- An exact duality theory for semidefinite programming and its complexity implications
- Semidefinite programming relaxations for semialgebraic problems
- Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
- Global Optimization with Polynomials and the Problem of Moments
- Lectures on Modern Convex Optimization
- On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming
- A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis
- Khachiyan’s algorithm for linear programming
- SOS Is Not Obviously Automatizable, Even Approximately
- On the Bit Complexity of Sum-of-Squares Proofs
- On the volume of tubular neighborhoods of real algebraic varieties
- Algorithms in real algebraic geometry
- Strong duality in lasserre's hierarchy for polynomial optimization
- Hausdorff approximations and volume of tubes of singular algebraic sets
This page was built for publication: A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
