Optimization Online


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

J. William Helton (helton***at***math.ucsd.edu)
Jiawang Nie (njw***at***math.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: 05/19/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society