Certifying polynomial nonnegativity via hyperbolic optimization

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

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 d \geq 4, we show that this occurs whenever n \geq 4. 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.

Original languageEnglish
Pages (from-to)661-690
Number of pages30
JournalSIAM Journal on Applied Algebra and Geometry
Volume3
Issue number4
DOIs
Publication statusPublished - 2019

Keywords

  • Bezoutian
  • Hyperbolic polynomial
  • Hyperbolicity cone
  • Sums of squares

Cite this