On sums of squares of K-nomials

DOI10.1016/J.JPAA.2021.106820MaRDI QIDQ1979337zbMATHOpenAlexFDO

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)

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

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)

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.

Recommendations

• scientific article; zbMATH DE number 70084
• 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

Cites work

• scientific article; zbMATH DE number 3167805 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• A quantitative version of Hurwitz' theorem on the arithmetic-geometric inequality.
• DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
• Forms derived from the arithmetic-geometric inequality
• Global optimization with polynomials and the problem of moments
• Matrix mathematics. Theory, facts, and formulas
• On factor width and symmetric \(H\)-matrices
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Positive semidefinite diagonal minus tail forms are sums of squares
• Semidefinite Optimization and Convex Algebraic Geometry
• Some geometric results in semidefinite programming
• Uniform denominators in Hilbert's seventeenth problem

Cited in

(11)

• Sums of squares in Macaulay2
• A Sum of Squares Characterization of Perfect Graphs
• On a theorem of A. I. Popov on sums of squares
• Sum-of-squares certificates for copositivity via test states
• scientific article; zbMATH DE number 7653018 (Why is no real title available?)
• On sum of squares decomposition for a biquadratic matrix function
• Sums of Squares of Polynomials
• Sum of squares representation for the Böttcher-Wenzel biquadratic form
• Subset Selection and the Cone of Factor-Width-k Matrices
• Sums of \(4k\) squares: a polynomial approach
• Hyperbolic Relaxation of $k$-Locally Positive Semidefinite Matrices

Describes a project that uses

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)