Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
From MaRDI portal
Publication:3451762
DOI10.1137/140966265zbMath1327.90175arXiv1312.6662OpenAlexW3105624319MaRDI QIDQ3451762
Hamza Fawzi, James Saunderson, Pablo A. Parrilo
Publication date: 18 November 2015
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.6662
Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symmetry properties of polytopes (52B15)
Related Items
Lifting for Simplicity: Concise Descriptions of Convex Sets, Query Complexity in Expectation, On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy, Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Global completability with applications to self-consistent quantum tomography, Lieb's concavity theorem, matrix geometric means, and semidefinite optimization, Sparse sums of squares on finite abelian groups and improved semidefinite lifts, Sum-of-squares hierarchy lower bounds for symmetric formulations, Positive semidefinite rank and nested spectrahedra, Semidefinite approximations of conical hulls of measured sets, Binary quadratic optimization problems that are difficult to solve by conic relaxations, Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization, Orbital geometry and group majorisation in optimisation, Positive semidefinite rank, Semidefinite Descriptions of the Convex Hull of Rotation Matrices, High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polytopes of minimum positive semidefinite rank
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- Smallest compact formulation for the permutahedron
- Positive semidefinite rank
- Expressing combinatorial optimization problems by linear programs
- Convex hulls of orbits of representations of finite groups and combinatorial optimization
- Convex sets with semidefinite representation
- Lectures on Modern Convex Optimization
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Constructing Extended Formulations from Reflection Relations
- Theta Bodies for Polynomial Ideals
- ORBITOPES
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Symmetry Matters for the Sizes of Extended Formulations
- On the Shannon capacity of a graph
- Semidefinite Optimization and Convex Algebraic Geometry
- Lifts of Convex Sets and Cone Factorizations
- Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
- Semidefinite Descriptions of the Convex Hull of Rotation Matrices
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Equivariant Semidefinite Lifts of Regular Polygons
- Doubly Stochastic Matrices and the Diagonal of a Rotation Matrix
