A Convex Polynomial That Is Not sos-convex

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.

Summary¶

Constructs a convex polynomial that is not Sos-convex, separating ordinary convexity from the Sos-verifiable sufficient condition. The counterexample is important for understanding the conservatism of semidefinite relaxations in polynomial optimization.

Links¶

Tags¶

Similar Papers¶