Let
$${S =\{x\in \mathbb{R}^n: g_1(x)\geq 0, \ldots, g_m(x)\geq 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\in \mathbb{R}^n:\, g_i(x)\geq 0\}}$$
, and ∂ *S* (resp. ∂ *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
$${\mathbb{R}^n}$$
, does there exist an LMI representable set Ŝ in some higher dimensional space
$${ \mathbb{R}^{n+N}}$$
whose projection down onto
$${\mathbb{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 *ℓ*^{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 ( − ∇^{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., ∇*g*_{i}(*x*) ≠ 0 on ∂ *S*_{i} ∩ *S*), then *S* is SDP representable. This also holds for *S*_{i} for which ∂ *S*_{i} ∩ *S* extends smoothly to the boundary of a poscurv-convex set containing *S*. (iv) We give the complexity of Schmüdgen and Putinar’s matrix Positivstellensatz, which are critical to the proofs of (i)–(iii).