{
  "id": "0709.4017",
  "version": "v3",
  "published": "2007-09-25T19:27:45.000Z",
  "updated": "2008-12-07T23:48:11.000Z",
  "title": "Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets",
  "authors": [
    "J. William Helton",
    "Jiawang Nie"
  ],
  "comment": "28 pages, revised version made on December 7, 2008",
  "categories": [
    "math.OC",
    "math.AG"
  ],
  "abstract": "A set $S\\subseteq \\re^n$ is called to be {\\it Semidefinite (SDP)} representable if $S$ equals the projection of a set in higher dimensional space which is describable by some Linear Matrix Inequality (LMI). The contributions of this paper are: (i) For bounded SDP representable sets $W_1,...,W_m$, we give an explicit construction of an SDP representation for $\\cv{\\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 $\\bdS$ is positively curved, and necessary condition: $\\bdS$ 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 $\\bdS$ where they vanish. The gaps between them are $\\bdS$ having positive versus nonnegative curvature and smooth versus nonsmooth points. A sufficient condition bypassing the gaps is when some defining polynomials of $S$ are sos-concave. (iii) For the SDP representability of the convex hull of a compact nonconvex semialgebraic set $T$, we find that the critical object is $\\pt_cT$, the maximum subset of $\\pt T$ contained in $\\pt \\cv{T}$. We prove sufficient conditions for SDP representability: $\\pt_cT$ is positively curved, and necessary conditions: $\\pt_cT$ has nonnegative curvature at smooth points and on nondegenerate corners. The gaps between them are similar to case (ii). The positive definite Lagrange Hessian (PDLH) condition is also discussed.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2008-12-07T23:48:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "necessary condition",
      "convex hull",
      "semidefinite representability",
      "sufficient condition",
      "sdp representability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0709.4017H"
    }
  }
}