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/2007
Entry Accepted: 10/15/2007
Entry Last Modified: 10/15/2007

Modify/Update this entry