Computational Tradeoffs and Symmetry in Polynomial Nonnegativity

Abstract

Understanding when a polynomial is nonnegative on a region is a fundamental problem in applied mathematics. Although exact conditions for nonnegativity are computationally intractable, there has been a surge of recent work giving sufficient conditions for nonnegativity to address its many practical applications. A major trend in this direction has been the use of convex optimization to characterize polynomials that are sums of squares (SOS); nevertheless, this well-studied condition can be computationally intensive for polynomials of moderate degree and dimension. This thesis addresses the challenge of balancing computational cost against the strength of sufficient conditions for nonnegativity. We make progress towards bridging the gap between simple but crude sufficient conditions, and the more powerful but expensive SOS approach. In the first part, we introduce new certificates of nonnegativity that may be used when SOS is too expensive yet cheaper sufficient conditions are too conservative. For this, we leverage different features of the polynomials, including its Bernstein coefficients, a lower-degree interpolant, or its harmonic decomposition. In the second part, we construct coordinate-invariant sufficient conditions for nonnegativity and study the symmetry properties of the space of Gram matrices. By considering it as a representation of GL(n,R) and combining this module structure with classical invariant theory, we construct an explicit equivariant map for nonnegativity certification. We further introduce an alternative approach using equivariant neural networks, analyzing their benefits and limitations.