Sums of squares and sparse semidefinite programming

DOI10.1137/20M1376170MaRDI QIDQ5157588zbMATH OpenOpenAlexWikidataFDO

Authors Grigoriy Blekherman, Kevin Shu

Publication date 19 October 2021

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

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

zbMATH Keywords

matrix completionreal algebraic geometrysemidefinite programming

Mathematics Subject Classification ID

Real algebraic and real-analytic geometry (14P99) Matrix completion problems (15A83) Semidefinite programming (90C22)

Abstract: We consider two seemingly unrelated questions: the relationship between nonnegative polynomials and sums of squares on real varieties, and sparse semidefinite programming. This connection is natural when a real variety $X$ is defined by a quadratic square-free monomial ideal. In this case nonnegative polynomials and sums of squares on $X$ are also natural objects in positive semidefinite matrix completion. Nonnegative quadratic forms over $X$ naturally correspond to partially specified matrices where all of the fully specified square blocks are PSD, and sums of squares quadratic forms naturally correspond to partially specified matrices which can be completed to a PSD matrix. We show quantitative results on approximation of nonnegative polynomials by sums of squares, which leads to applications in sparse semidefinite programming.

Recommendations

• Sparsity in sums of squares of polynomials
• Polynomial optimization, sums of squares, and applications
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Nonnegative polynomials and sums of squares
• Moments and sums of squares for polynomial optimization and related problems

Cites work

• Decomposition by clique separators
• Dictionary learning and tensor decomposition via the sum-of-squares method
• Do sums of squares dream of free resolutions?
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• scientific article; zbMATH DE number 16165 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 1149836 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Minimum fill-in: inapproximability and almost tight lower bounds
• On a parametrization of positive semidefinite matrices with zeros
• Positive definite completions of partial Hermitian matrices
• Semidefinite Optimization and Convex Algebraic Geometry
• Structural conditions for cycle completable graphs
• Sums of squares and varieties of minimal degree
• The real positive definite completion problem for a simple cycle
• The real positive definite completion problem: cycle completability
• There are significantly more nonnegative polynomials than sums of squares

Cited in

(10)

• Sparsity in sums of squares of polynomials
• On sums of squares of \(K\)-nomials
• Nonnegative polynomials and sums of squares
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Approximating nonnegative polynomials via spectral sparsification
• An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture
• Sums of Separable and Quadratic Polynomials
• Bilinear matrix inequalities and polynomials in several freely noncommuting variables
• Convergence rates for the moment-SoS hierarchy
• Lectures on nonnegative polynomials and sums of squares

This page was built for publication: Sums of squares and sparse semidefinite programming

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