Sum-of-squares hierarchies for binary polynomial optimization
From MaRDI portal
Publication:5925640
DOI10.1007/s10107-021-01745-9OpenAlexW3105711037MaRDI QIDQ5925640
Publication date: 14 March 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-021-01745-9
semidefinite programmingpolynomial matricesFourier analysisKrawtchouk polynomialsLasserre hierarchysum-of-squares polynomialspolynomial kernelsbinary polynomial optimization
Related Items
Sum of Squares Bounds for the Empty Integral Hull Problem, Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials, The Spectrum of the Grigoriev–Laurent Pseudomoments
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Polyhedral and semidefinite programming methods in combinatorial optimization
- Correlation clustering
- Semidefinite representations for finite varieties
- On the complexity of Putinar's Positivstellensatz
- On the complexity of Schmüdgen's Positivstellensatz
- A MAX-CUT formulation of 0/1 programs
- Uniform denominators in Hilbert's seventeenth problem
- Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
- Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets
- The sum-of-squares hierarchy on the sphere and applications in quantum information theory
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Matrix sum-of-squares relaxations for robust semi-definite programs
- Global Optimization with Polynomials and the Problem of Moments
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis
- Approximating the cut-norm via Grothendieck's inequality
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Sum-of-squares proofs and the quest toward optimal algorithms
- Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
- SOS Is Not Obviously Automatizable, Even Approximately
- Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
- On the Bit Complexity of Sum-of-Squares Proofs
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
