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

DOI10.1007/S10107-015-0977-ZzbMATH Open1387.90180arXiv1503.01207OpenAlexW3099419577MaRDI QIDQ344935FDOQ344935

Pablo A. Parrilo, James Saunderson, Hamza Fawzi

Publication date: 25 November 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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))$.

Full work available at URL: https://arxiv.org/abs/1503.01207

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

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)

Cites Work

• Lectures on Polytopes
• Global optimization with polynomials and the problem of moments
• Expressing combinatorial optimization problems by linear programs
• Constructing Extended Formulations from Reflection Relations
• Title not available (Why is that?)
• Semidefinite Optimization and Convex Algebraic Geometry
• Lifts of Convex Sets and Cone Factorizations
• Title not available (Why is that?)
• Positive definite completions of partial Hermitian matrices
• Title not available (Why is that?)
• Combinatorial bounds on nonnegative rank and extended formulations
• Positive trigonometric polynomials and signal processing applications
• Title not available (Why is that?)
• Positive semidefinite rank
• Positive semidefinite matrices with a given sparsity pattern
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• Equivariant Semidefinite Lifts of Regular Polygons
• Sums of squares on the hypercube
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Small extended formulations for cyclic polytopes
• Title not available (Why is that?)
• On the existence of convex decompositions of partially separable functions

Cited In (16)

• Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
• Lower bounds of functions on finite abelian groups
• Sum-of-squares rank upper bounds for matching problems
• Sum-of-Squares Rank Upper Bounds for Matching Problems
• Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
• Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• Sums of squares on the hypercube
• Lifting for Simplicity: Concise Descriptions of Convex Sets
• Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
• Disordered systems insights on computational hardness
• On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
• Loraine – an interior-point solver for low-rank semidefinite programming
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
• Sum-of-squares hierarchies for binary polynomial optimization
• Sum-of-squares hierarchies for binary polynomial optimization

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)