The article proves sufficient conditions and necessary conditions for SDP representability of convex sets and convex hulls by proposing a new approach to construct SDP representations. The contributions of this paper are: (i) For bounded SDP representable sets $W_1,\cdots,W_m$, we give an explicit construction of an SDP representation for $conv(\cup_{k=1}^mW_k)$. This provides a technique for building global SDP representations from the local ones. (ii) For the SDP representability of a compact convex semialgebraic set $S$, we prove sufficient condition: the boundary $\partial S$ is positively curved, and necessary condition: $\partial S$ has nonnegative curvature at smooth points and on nondegenerate corners. This amounts to the strict versus nonstrict quasi-concavity of defining polynomials on those points on $\partial S$ where they vanish. (iii) For the SDP representability of the convex hull of a compact nonconvex semialgebraic set $T$, we find that the critical object is $\partial_cT$, the maximum subset of $\partial T$ contained in $\partial conv(T)$. We prove sufficient conditions for SDP representability: $\partial_cT$ is positively curved, and necessary conditions: $\partial_cT$ has nonnegative curvature at smooth points and on nondegenerate corners. The positive definite Lagrange Hessian (PDLH) condition is also discussed.
Citation
http://www.arxiv.org/abs/0709.4017
Article
View Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets