  


Semidefinite Representation of Convex Sets
J. William Helton (heltonmath.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 sosconcave ($\nabla^2g_i(x)=W(x)^TW(x)$ for some possibly nonsquare matrix polynomial $W(x)$) or strictly quasiconcave on $S$, then $S$ is SDP representable. {\bf (iii)} If each $S_i$ is either sosconvex or poscurvconvex ($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 poscurvconvex 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 poscurvconvex, positive second fundamental form, poscurvconvex, sosconcave (sosconvex) Category 1: Linear, Cone and Semidefinite Programming (Semidefinite 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 Modify/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  