A convex polynomial that is not sos-convex

Amir Ali Ahmadi, Pablo A. Parrilo

Research output: Contribution to journalArticlepeer-review

33 Scopus citations

Abstract

A multivariate polynomial p(x) = p(x 1,⋯, x n) is sos-convex if its Hessian H(x) can be factored as H(x) = M T (x) M(x) with a possibly nonsquare polynomial matrix M(x). It is easy to see that sos-convexity is a sufficient condition for convexity of p(x). Moreover, the problem of deciding sos-convexity of a polynomial can be cast as the feasibility of a semidefinite program, which can be solved efficiently. Motivated by this computational tractability, it is natural to study whether sos-convexity is also a necessary condition for convexity of polynomials. In this paper, we give a negative answer to this question by presenting an explicit example of a trivariate homogeneous polynomial of degree eight that is convex but not sos-convex.

Original languageEnglish (US)
Pages (from-to)275-292
Number of pages18
JournalMathematical Programming
Volume135
Issue number1-2
DOIs
StatePublished - Oct 1 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Convexity
  • Semidefinite programming
  • Sos-convexity
  • Sum of squares

Fingerprint Dive into the research topics of 'A convex polynomial that is not sos-convex'. Together they form a unique fingerprint.

Cite this