Sparse sums of squares on finite abelian groups and improved semidefinite lifts
From MaRDI portal
Publication:344935
DOI10.1007/s10107-015-0977-zzbMath1387.90180arXiv1503.01207OpenAlexW3099419577MaRDI QIDQ344935
James Saunderson, Hamza Fawzi, Pablo A. Parrilo
Publication date: 25 November 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.01207
Semidefinite programming (90C22) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational aspects related to convexity (52B55)
Related Items
Lifting for Simplicity: Concise Descriptions of Convex Sets, Sum-of-squares rank upper bounds for matching problems, Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel, Disordered systems insights on computational hardness, Sums of squares on the hypercube, The Spectrum of the Grigoriev–Laurent Pseudomoments, On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy, A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian, Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems, Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization, Sum-of-squares hierarchies for binary polynomial optimization, Sum-of-squares hierarchies for binary polynomial optimization, Sum-of-Squares Rank Upper Bounds for Matching Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sums of squares on the hypercube
- Positive semidefinite rank
- Positive definite completions of partial Hermitian matrices
- Positive semidefinite matrices with a given sparsity pattern
- Expressing combinatorial optimization problems by linear programs
- Combinatorial bounds on nonnegative rank and extended formulations
- Small extended formulations for cyclic polytopes
- Global Optimization with Polynomials and the Problem of Moments
- Constructing Extended Formulations from Reflection Relations
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Lectures on Polytopes
- Semidefinite Optimization and Convex Algebraic Geometry
- Lifts of Convex Sets and Cone Factorizations
- On the existence of convex decompositions of partially separable functions
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Equivariant Semidefinite Lifts of Regular Polygons
- Positive trigonometric polynomials and signal processing applications
