On sums of squares of k-nomials |
| |
Authors: | João Gouveia Alexander Kovačec Mina Saee |
| |
Affiliation: | 1. School of Mathematics, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai-40005, India;2. Organization for the Strategic Coordination of Research and Intellectual Properties, Meiji University, Japan;3. Department of Mathematics, College of Humanities and Sciences, Nihon University, Setagaya-Ku, Tokyo 156-0045, Japan;1. Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, Maharashtra, India;2. Department of Mathematics, Indian Institute of Technology Hyderabad, Kandi, Sangareddy, 502285, Telangana, India;1. Dipartimento di Informatica, Università degli Studi di Verona, Strada le Grazie 15, 37134 Verona, Italy;2. Department of Mathematics, Faculty of Sciences of Sfax, University of Sfax, 3000 Sfax, Tunisia;1. Tata Institute of Fundamental Research, School of Mathematics, Mumbai, India;2. Osnabrück University, Institute of Mathematics, Osnabrück, Germany |
| |
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 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 [1], explored this connection for case and proposed to relax the reliance on polynomials that are sums of squares in semidefinite programming to polynomials that are sums of binomial squares In this paper, we 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 show that they never help for symmetric quadratics, for any quadratic if , and any quaternary quadratic if . Furthermore we give some evidence that those are a complete list of such cases. |
| |
Keywords: | Factor width Sums of squares Positive semidefinite Scaled diagonally dominant sum of squares (SDSOS) |
本文献已被 ScienceDirect 等数据库收录! |
|