Semidefinite representation of convex sets

Let S = {x is an element of R-n : g(1)(x) >= 0, ..., g(m)(x) >= 0} be a semialgebraic set defined by multivariate polynomials g(i) (x). Assume S is convex, compact and has nonempty interior. Let S-i = {x is an element of R-n : g(i)(x) >= 0}, and partial derivative S (resp. partial derivative S-i ) be the boundary of S (resp. S-i ). This paper, as does the subject of semidefinite programming (SDP), concerns linear matrix inequalities (LMIs). The set S is said to have an LMI representation if it equals the set of solutions to some LMI and it is known that some convex S may not be LMI representable (Helton and Vinnikov in Commun Pure Appl Math 60(5):654-674, 2007). A question arising from Nesterov and Nemirovski (SIAM studies in applied mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1994), see Helton and Vinnikov in Commun Pure Appl Math 60(5):654-674, 2007 and Nemirovski in Plenary lecture, International Congress of Mathematicians (ICM), Madrid, Spain, 2006, is: given a subset S of R-n, does there exist an LMI representable set (S) over cap in some higher dimensional space Rn+N whose projection down onto R-n equals S. Such S is called semidefinite representable or SDP representable. This paper addresses the SDP representability problem. The following are the main contributions of this paper: (i) assume g(i) (x) are all concave on S. If the positive definite Lagrange Hessian condition holds, i.e., the Hessian of the Lagrange function for optimization problem of minimizing any nonzero linear function l(T) x on S is positive definite at the minimizer, then S is SDP representable. (ii) If each g(i) (x) is either sos-concave ( - del(2) g(i) (x) = W(x) (T) W(x) for some possibly nonsquare matrix polynomial W(x)) or strictly quasi-concave on S, then S is SDP representable. (iii) If each S-i is either sos-convex or poscurv-convex (S-i is compact convex, whose boundary has positive curvature and is nonsingular, i.e., del g(i) (x) not equal 0 on partial derivative S-i boolean AND S), then S is SDP representable. This also holds for S-i for which partial derivative S-i boolean AND S extends smoothly to the boundary of a poscurv-convex set containing S. (iv) We give the complexity of Schmudgen and Putinar's matrix Positivstellensatz, which are critical to the proofs of (i)-(iii).