Journal
MATHEMATICAL PROGRAMMING
Volume 135, Issue 1-2, Pages 275-292Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-011-0457-z
Keywords
Convexity; Sos-convexity; Sum of squares; Semidefinite programming
Categories
Funding
- MURI AFOSR [FA9550-06-1-0303]
- NSF FRG [0757207]
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [0757207] Funding Source: National Science Foundation
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available