Optimization Online


Semidefinite Representation of Convex Sets

J. William Helton (helton***at***math.ucsd.edu)
Jiawang Nie (njw***at***math.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/2007
Entry Accepted: 06/20/2007
Entry Last Modified: 07/21/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