On sums of squares of K-nomials

DOI10.1016/J.JPAA.2021.106820zbMATH Open1477.13048arXiv1912.01371OpenAlexW3176627360MaRDI QIDQ1979337FDOQ1979337

Authors: João Gouveia, Mina Saee, Alexander Kovačec 

Publication date: 2 September 2021

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Abstract: In 2005, Boman et al introduced the concept of factor width for a real symmetric positive semidefinite matrix. This is the smallest positive integer $k$ for which the matrix $A$ can be written as $A=V{V}^T$ with each column of $V$ containing at most $k$ non-zeros. The cones of matrices of bounded factor width give a hierarchy of inner approximations to the PSD cone. In the polynomial optimization context, a Gram matrix of a polynomial having factor width $k$ corresponds to the polynomial being a sum of squares of polynomials of support at most $k$. Recently, Ahmadi and Majumdar, explored this connection for case $k=2$ and proposed to relax the reliance on sum of squares polynomials in semidefinite programming to sum of binomial squares polynomials (sobs; which they call sdsos), for which semidefinite programming can be reduced to second order programming to gain scalability at the cost of some tolerable loss of precision. With this they tap into the study of sobs that goes back to Reznick and Hurwitz. In this paper, we will prove some results on the geometry of the cones of matrices with bounded factor widths and their duals, and use them to derive new results on the limitations of certificates of nonnegativity of quadratic forms by sums of $k$-nomial squares using standard multipliers. In particular we will show that they never help for symmetric quadratics, for any quadratic if $k=2$, and any quaternary quadratic if $k=3$. Furthermore we give some evidence that those are a complete list of such cases.

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

Recommendations

• scientific article
• Polynomial optimization, sums of squares, and applications
• Sums of squares and sparse semidefinite programming
• Positive polynomials and sums of squares: theory and practice
• Computation of sum of squares polynomials from data points
• Lower bounds for polynomials using geometric programming
• Nonnegative polynomials and sums of squares
• Moments and sums of squares for polynomial optimization and related problems
• An algorithm for sums of squares of real polynomials
• Sums of Squares of Polynomials

zbMATH Keywords

sums of squarespositive semidefinitefactor width\(k\)-nomialsscaled diagonally dominant sum of squares (SDSOS)

Mathematics Subject Classification ID

Nonlinear programming (90C30) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Real algebra (13J30)

Cites Work

• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Title not available (Why is that?)
• Title not available (Why is that?)
• Global optimization with polynomials and the problem of moments
• Matrix mathematics. Theory, facts, and formulas
• Uniform denominators in Hilbert's seventeenth problem
• Semidefinite Optimization and Convex Algebraic Geometry
• Forms derived from the arithmetic-geometric inequality
• On factor width and symmetric \(H\)-matrices
• DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization
• Positive semidefinite diagonal minus tail forms are sums of squares
• Some geometric results in semidefinite programming
• A quantitative version of Hurwitz' theorem on the arithmetic-geometric inequality.

Cited In (9)

• Sums of squares in Macaulay2
• On sum of squares decomposition for a biquadratic matrix function
• On a theorem of A. I. Popov on sums of squares
• A Sum of Squares Characterization of Perfect Graphs
• Sums of Squares of Polynomials
• Subset Selection and the Cone of Factor-Width-k Matrices
• Title not available (Why is that?)
• Hyperbolic Relaxation of $k$-Locally Positive Semidefinite Matrices
• Sums of \(4k\) squares: a polynomial approach

Uses Software

• SPOTless
• frlib

This page was built for publication: On sums of squares of \(K\)-nomials

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