Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets

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

Download

View Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets