Certifying Polynomial Nonnegativity via Hyperbolic Optimization

DOI10.1137/19M1253551MaRDI QIDQ5208888zbMATH OpenOpenAlexWikidataFDO

Authors James Saunderson

Publication date 22 January 2020

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

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

zbMATH Keywords

Bézoutianhyperbolic polynomialhyperbolicity conesums of squares

Mathematics Subject Classification ID

Sums of squares and representations by other particular quadratic forms (11E25) Semialgebraic sets and related spaces (14P10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Semidefinite programming (90C22) Convex programming (90C25)

Abstract: We describe a new approach to certifying the global nonnegativity of multivariate polynomials by solving hyperbolic optimization problems---a class of convex optimization problems that generalize semidefinite programs. We show how to produce families of nonnegative polynomials (which we call hyperbolic certificates of nonnegativity) from any hyperbolic polynomial. We investigate the pairs $(n,d)$ for which there is a hyperbolic polynomial of degree $d$ in $n$ variables such that an associated hyperbolic certificate of nonnegativity is not a sum of squares. If $dgeq4$ we show that this occurs whenever $ngeq4$. In the degree three case, we find an explicit hyperbolic cubic in $43$ variables that gives hyperbolic certificates that are not sums of squares. As a corollary, we obtain the first known hyperbolic cubic no power of which has a definite determinantal representation. Our approach also allows us to show that, given a cubic $p$, and a direction $e$, the decision problem "Is $p$ hyperbolic with respect to $e$?" is co-NP hard.

Recommendations

• Positivity certificates and polynomial optimization on non-compact semialgebraic sets
• Numerical optimization and positivity certificates for polynomials and rationals over simplices
• Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
• A convex optimization model for finding non-negative polynomials
• Nonnegative Morse polynomial functions and polynomial optimization
• On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity
• A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
• Positive polynomials and semidefinite programming
• Completely positive reformulations for polynomial optimization
• Exact certification in global polynomial optimization via rationalizing sums-of-squares

Cites work

• ``Efficient subgradient methods for general convex optimization
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• A note on the hyperbolicity cone of the specialized Vámos polynomial
• A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
• Accelerated first-order methods for hyperbolic programming
• Class of global minimum bounds of polynomial functions
• Determinantal representations and the Hermite matrix
• Determinantal representations of hyperbolic plane curves: an elementary approach
• Determinantal representations of smooth cubic surfaces
• Finite free convolutions of polynomials
• Global optimization with polynomials and the problem of moments
• Gårding's theory of hyperbolic polynomials
• scientific article; zbMATH DE number 3146819 (Why is no real title available?)
• scientific article; zbMATH DE number 1489808 (Why is no real title available?)
• Hyperbolic Polynomials and Interior Point Methods for Convex Programming
• Hyperbolic polynomials, interlacers, and sums of squares
• Hyperbolic programs, and their derivative relaxations
• Hyperbolicity cones of elementary symmetric polynomials are spectrahedral
• Lacunas for hyperbolic differential operators with constant coefficients.I
• Linear matrix inequality representation of sets
• Lower bounds on the size of semidefinite programming relaxations
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Noisy tensor completion via the sum-of-squares hierarchy
• Non-representable hyperbolic matroids
• Numerical methods for structured matrices and applications. The Georg Heinig memorial volume
• Obstructions to determinantal representability
• Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones
• Reducibility among combinatorial problems
• Sampling algebraic varieties for sum of squares programs
• Semidefinite geometry of the numerical range
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite programming relaxations for semialgebraic problems
• Spectrahedral representations of plane hyperbolic curves
• Spectrahedral shadows
• Spectrahedrality of hyperbolicity cones of multivariate matching polynomials
• Sums of squares and varieties of minimal degree
• The Euclidean distance degree of an algebraic variety
• The Lax conjecture is true
• The method of symmetric and Hermitian forms in the theory of the separation of the roots of algebraic equations
• Using Linear Programming to Decode Binary Linear Codes

Cited in

(16)

• Semi-definite representations for sets of cubics on the two-dimensional sphere
• Extremal cubics on the circle and the 2-sphere
• Testing hyperbolicity of real polynomials
• Definite determinantal representations via orthostochastic matrices
• Symmetric semi-algebraic sets and non-negativity of symmetric polynomials
• Imaginary projections: complex versus real coefficients
• {\textsc{RealCertify}}: a Maple package for certifying non-negativity
• A convex optimization model for finding non-negative polynomials
• Matroids on Eight Elements with the Half-Plane Property and Related Concepts
• Hyperbolicity cones are amenable
• Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
• Strictly stable Hurwitz polynomials and their determinantal representations
• Symmetric hyperbolic polynomials
• Non-negative polynomials without hyperbolic certificates of non-negativity
• Hyperbolic polynomials, interlacers, and sums of squares
• Deciding positivity of multisymmetric polynomials

This page was built for publication: Certifying Polynomial Nonnegativity via Hyperbolic Optimization

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