Sparse sums of squares on finite abelian groups and improved semidefinite lifts

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

zbMATH Keywords

semidefinite programming

Mathematics Subject Classification ID

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