On sums of squares of K-nomials

DOI10.1016/J.JPAA.2021.106820MaRDI QIDQ1979337zbMATH OpenOpenAlexFDO

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

\(k\)-nomials factor width positive semidefinite scaled diagonally dominant sum of squares (SDSOS)sums of squares

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.

Review text

The paper under reviews deals with sums of squares certificates for nonnegative real polynomials. This is of practical importance for approximating the infimum of real polynomials by using semidefinite programming. Central is here a meanwhile classical result by \textit{B. Reznick} [Math. Z. 220, No. 1, 75--97 (1995; Zbl 0828.12002)]: Any positive definite form of degree \(2d\) in \(n\) variables can be written as a sum of squares after being multiplied by a sufficiently high power of \(x_1^2+\ldots +x_n^2\). For efficiency in semidefinite programming, it is interesting to impose restraints on sums of square certificates; for example to bound the number of monomials. Given a natural number \(k\), a \(k\)-nomial is of the form \(\alpha_1m_1+\ldots\alpha_km_k\) with \(\alpha_1,\ldots,\alpha_k\) reals and \(m_1,\ldots,m_k\) monomials. In the cases \(k=2, 3, 4\) one speaks of binomials, trinomials and tetranomials, respectively. For quadratic forms the authors show the limitations of the multiplier method in certain cases. The main result is the following: Theorem: Let \(p\) be a quadratic form in \(n\) variables. When any of the following holds \begin{itemize} \item[1.] \(p\) is symmetric, \item[2.] \(k=2\), \item[3.] \(n=4\) and \(k=3\), \end{itemize} then there exists a nonnegative integer \(r\) such that \((x_1^2+\ldots x_n^2)^r p\) is a sum of squared\\ \(k\)-nomials if and only if \(p\) itself is a sum of squared \(k\)-nomials. For the proof the concept of factor width for a real symmetric positive semidefinite matrix is used (cf. [\textit{E. G. Boman} et al., Linear Algebra Appl. 405, 239--248 (2005; Zbl 1098.15014)]).

Recommendations

Cites work

Cited in

(12)

Describes a project that uses

Uses Software

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)