SDP Representation of Convex Sets
Preprint
Abstract
Let $S =\{x\in \re^n: g_1(x)\geq 0, ..., g_m(x)\geq 0\}$ be a semialgebraic set defined by multivariate polynomials $g_i(x)$. Assume $S$ is compact, convex and has nonempty interior. Let $S_i =\{x\in \re^n: g_i(x)\geq 0\}$ and $\bdS_i=\{x\in \re^n: g_i(x) = 0\}$ be its boundary. A question arising from \cite{NN94}, see \cite{HV,N06}, is: given $S \in \re^n$, does there exist an LMI representable set $\hS$ in some higher dimensional space $ \re^{n+N}$ whose projection down onto $\re^n$ equals $S$. Such $S$ is called semidefinite representable or SDP representable. The following are the main contributions of this paper: {\bf (i)} Assume $g_i(x)$ are all concave on $S$. If the positive definite Lagrange Hessian (PDLH) condition holds, then $S$ is SDP representable. {\bf (ii)} If each $g_i(x)$ is either sos-concave or strictly quasi-concave on $S$, then $S$ is SDP representable. {\bf (iii)} If each $S_i$ is either sos-convex or poscurv-convex, then $S$ is SDP representable. This also holds for $S_i$ for which $ \bdS_i \cap S$ extends smoothly to the boundary of a poscurv-convex set containing $S$. {\bf (iv)} We give the complexity of Schm\"{u}dgen and Putinar's matrix Positivstellensatz, which are critical to the proofs of (i)-(iii).
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Convex sets with semidefinite representationMathematical Programming, 2008
- On the complexity of Putinar's PositivstellensatzJournal of Complexity, 2007
- An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric ConesMathematical Programming, 2006
- Matrix Sum-of-Squares Relaxations for Robust Semi-Definite ProgramsMathematical Programming, 2005
- Distinguished representations of non-negative polynomialsJournal of Algebra, 2005
- Sums of squares on real algebraic curvesMathematische Zeitschrift, 2003
- GloptiPoly: global optimization over polynomials with Matlab and SeDuMi2003
- Positive polynomials on semi-algebraic setsComptes Rendus de l'Académie des Sciences - Series I - Mathematics, 1999
- TheK-moment problem for compact semi-algebraic setsMathematische Annalen, 1991
- Submanifolds with everywhere semidefinite second fundamental formJournal of Mathematical Sciences, 1978