A convex polynomial that is not sos-convex

Amir Ali Ahmadi(a_a_amit.edu)
Pablo A. Parrilo(parrilomit.edu)

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 has been recently speculated 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. Interestingly, our example is found with software using sum of squares programming techniques and the duality theory of semidefinite optimization. As a byproduct of our numerical procedure, we obtain a simple method for searching over a restricted family of nonnegative polynomials that are not sums of squares.

Keywords: convexity, sum of squares, semidefinite programming

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: LIDS technical report #2810, March 2009.

Download: [PDF]

Entry Submitted: 03/08/2009
Entry Accepted: 03/08/2009
Entry Last Modified: 03/08/2009

Modify/Update this entry