- Semidefinite Representation of Convex Sets J. William Helton (heltonmath.ucsd.edu) Jiawang Nie (njwmath.ucsd.edu) Abstract: Let $S =\{x\in \re^n:\, g_1(x)\geq 0, \cdots, g_m(x)\geq 0\}$ be a semialgebraic set defined by multivariate polynomials $g_i(x)$. Assume $S$ is convex, compact and has nonempty interior. Let $S_i =\{x\in \re^n:\, g_i(x)\geq 0\}$, and $\bdS$ (resp. $\bdS_i$) be the boundary of $S$ (resp. $S_i$). This paper, as does the subject of semidefinite programming (SDP), concerns Linear Matrix Inequalities (LMIs). The set $S$ is said to have an LMI representation if it equals the set of solutions to some LMI and it is known that some convex $S$ may not be LMI representable \cite{HV}. A question arising from \cite{NN94}, see \cite{HV,N06}, is: given a subset $S$ of $\re^n$, does there exist an LMI representable set $\hS$ in some higher dimensional space $\re^{n+N}$ whose iprojection down onto $\re^n$ equals $S$. Such $S$ is called semidefinite representable or SDP representable. This paper addresses the SDP representability problem. 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, i.e., the Hessian of the Lagrange function for optimization problem of minimizing any nonzero linear function $\ell^Tx$ on $S$ is positive definite at the minimizer, then $S$ is SDP representable. {\bf (ii)} If each $g_i(x)$ is either sos-concave ($-\nabla^2g_i(x)=W(x)^TW(x)$ for some possibly nonsquare matrix polynomial $W(x)$) or strictly quasi-concave on $S$, then $S$ is SDP representable. {\bf (iii)} If each $S_i$ is either sos-convex or poscurv-convex ($S_i$ is compact convex, whose boundary has positive curvature and is nonsingular, i.e. $\nabla g_i(x) \not = 0$ on $\bdS_i \cap S$), 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: Convex sets, semialgebraic geometry, semidefinite programming (SDP),linear matrix inequality (LMI), sum of squares(SOS), modified Hessian, moments, convex polynomials positive curvature, Schm\"{u}dgen and Putinar's matrix Positivstellensatz, positive definite Lagrange Hessian (PDLH) condition, extendable poscurv-convex, positive second fundamental form, poscurv-convex, sos-concave (sos-convex) Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Category 3: Global Optimization (Theory ) Citation: http://www.arxiv.org/abs/0705.4068 Download: [PDF]Entry Submitted: 06/20/2007Entry Accepted: 06/20/2007Entry Last Modified: 07/21/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.