  


A convex polynomial that is not sosconvex
Amir Ali Ahmadi(a_a_amit.edu) Abstract: A multivariate polynomial $p(x)=p(x_1,...,x_n)$ is sosconvex 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 sosconvexity is a sufficient condition for convexity of $p(x)$. Moreover, the problem of deciding sosconvexity 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 sosconvexity 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 sosconvex. 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 (Semidefinite Programming ) Citation: LIDS technical report #2810, March 2009. Download: [PDF] Entry Submitted: 03/08/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  