Linear matrix inequality representation of sets

Abstract This article concerns the question, Which subsets of ℝ m can be represented with linear matrix inequalities (LMIs)? This gives some perspective on the scope and limitations of one of the most powerful techniques commonly used in control theory. Also, before having much hope of representing engineering problems as LMIs by automatic methods, one needs a good idea of which problems can and cannot be represented by LMIs. Little is currently known about such problems. In this article we give a necessary condition that we call “rigid convexity,” which must hold for a set 𝒞 ⊆ ℝ m in order for 𝒞 to have an LMI representation. Rigid convexity is proved to be necessary and sufficient when m = 2. This settles a question formally stated by Pablo Parrilo and Berndt Sturmfels in [15]. As shown by Lewis, Parillo, and Ramana [11], our main result also establishes (in the case of three variables) a 1958 conjecture by Peter Lax on hyperbolic polynomials. © 2006 Wiley Periodicals, Inc.