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

DOI10.1007/S10107-015-0977-ZMaRDI QIDQ344935zbMATH OpenOpenAlexFDO

Authors Hamza Fawzi, James Saunderson, 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)

Abstract: Let G be a finite abelian group. This paper is concerned with nonnegative functions on G that are sparse with respect to the Fourier basis. We establish combinatorial conditions on subsets S and T of Fourier basis elements under which nonnegative functions with Fourier support S are sums of squares of functions with Fourier support T. Our combinatorial condition involves constructing a chordal cover of a graph related to G and S (the Cayley graph Cay($hatG$,S)) with maximal cliques related to T. Our result relies on two main ingredients: the decomposition of sparse positive semidefinite matrices with a chordal sparsity pattern, as well as a simple but key observation exploiting the structure of the Fourier basis elements of G. We apply our general result to two examples. First, in the case where $G=mathbb{Z}_2^n$, by constructing a particular chordal cover of the half-cube graph, we prove that any nonnegative quadratic form in n binary variables is a sum of squares of functions of degree at most $lceiln/2ceil$, establishing a conjecture of Laurent. Second, we consider nonnegative functions of degree d on $mathbb{Z}_N$ (when d divides N). By constructing a particular chordal cover of the d'th power of the N-cycle, we prove that any such function is a sum of squares of functions with at most $3dlog(N/d)$ nonzero Fourier coefficients. Dually this shows that a certain cyclic polytope in $mathbb{R}^{2d}$ with N vertices can be expressed as a projection of a section of the cone of psd matrices of size $3dlog(N/d)$. Putting $N=d^2$ gives a family of polytopes $P_{d}subsetmathbb{R}^{2d}$ with LP extension complexity $ext{xc}_{LP}(P_d)=Omega(d^2)$ and SDP extension complexity $ext{xc}_{PSD}(P_d)=O(dlog(d))$. To the best of our knowledge, this is the first explicit family of polytopes in increasing dimensions where $ext{xc}_{PSD}(P_d)=o(ext{xc}_{LP}(P_d))$.

Recommendations

• Sums of squares and sparse semidefinite programming
• Sums of squares on the hypercube
• Symmetry groups, semidefinite programs, and sums of squares
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity

Cites work

• scientific article; zbMATH DE number 1318047 (Why is no real title available?)
• scientific article; zbMATH DE number 1489808 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 3223483 (Why is no real title available?)
• scientific article; zbMATH DE number 46730 (Why is no real title available?)
• Combinatorial bounds on nonnegative rank and extended formulations
• Constructing extended formulations from reflection relations
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• Equivariant semidefinite lifts of regular polygons
• Expressing combinatorial optimization problems by linear programs
• Global optimization with polynomials and the problem of moments
• Lectures on Polytopes
• Lifts of Convex Sets and Cone Factorizations
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• On the existence of convex decompositions of partially separable functions
• Positive definite completions of partial Hermitian matrices
• Positive semidefinite matrices with a given sparsity pattern
• Positive semidefinite rank
• Positive trigonometric polynomials and signal processing applications
• Semidefinite Optimization and Convex Algebraic Geometry
• Small extended formulations for cyclic polytopes
• Sums of squares on the hypercube

Cited in

(16)

• Lower bounds of functions on finite abelian groups
• 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
• Lifting for simplicity: concise descriptions of convex sets
• Disordered systems insights on computational hardness
• Sum-of-squares rank upper bounds for matching problems
• Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
• Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
• Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
• Sums of squares on the hypercube
• Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
• Sum-of-squares rank upper bounds for matching problems
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• Sum-of-squares hierarchies for binary polynomial optimization
• Sum-of-squares hierarchies for binary polynomial optimization
• Loraine – an interior-point solver for low-rank semidefinite programming

This page was built for publication: Sparse sums of squares on finite abelian groups and improved semidefinite lifts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344935)