Optimization Online


A convex polynomial that is not sos-convex

Amir Ali Ahmadi(a_a_a***at***mit.edu)
Pablo A. Parrilo(parrilo***at***mit.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society