- Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets J. William Helton (heltonmath.ucsd.edu) Jiawang Nie (njwmath.ucsd.edu) Abstract: 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. Keywords: convex set, convex hull, irredundancy, linear matrix inequality (LMI), nonsingularity, positive curvature, semialgebraic set, semidefinite (SDP) representation, (strictly) quasi-concavity, singularity, smoothness, sos-concavity, sum of squares (SOS) Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Citation: http://www.arxiv.org/abs/0709.4017 Download: [PDF]Entry Submitted: 10/15/2007Entry Accepted: 10/15/2007Entry Last Modified: 05/19/2008Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.