A convex polynomial that is not sos-convex

• 成果类型: Article
• 署名作者: Ahmadi, Amir Ali; Parrilo, Pablo A.
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0457-z
• 发表日期: 2012
• 页码: 275-292
• 关键词: semidefinite programs; squares; SUM; REPRESENTATION; relaxations; forms

摘要

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.