Linear matrix inequality representation of sets

By J. William Helton, Victor Vinnikov. 2003

415 citations recorded by the source corpus.

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.

Subfields: Applied Mathematics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/e6ab3c4652d680e6b2f4b82e81954609b5439a02

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Polynomial convolutions and (nite) free probability (2021, methodology): “An extremely useful characterization of hyperbolic polynomials [15, 14]: Theorem 5.”
NONCOMMUTATIVE CONVEXITY ARISES FROM LINEAR MATRIX INEQUALITIES. (2006, background): “Recent articles with lists of references are [3,4,23,38], and earlier articles are [11,13,14,37,39].”
Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products (2006, background): “The following modified version of the higher dimensional Lax conjecture has recently been proposed in [ 16 ] (see also [3, Conjecture 1]):”
LMI Representations of Convex Semialgebraic Sets and Determinantal Representations of Algebraic Hypersurfaces: Past, Present, and Future (2012, background): “A complete answer for d = 2 was obtained in [28], though there are still outstanding computational questions, see [29, 46, 47]; for d > 2, no answer is known, though the recent results of [6, 43, 42] shed some additional light on the problem.”
Obstructions to determinantal representability (2010, methodology): “In two variables such sets were characterized by Helton and Vinnikov [7] by so called rigidly convex sets, thereby answering a question posed by Parrilo and Sturmfels [14].”
Polynomials with the half-plane property and matroid theory (2006, background): “ces A,B and a real symmetric matrix C such that f(x,y) = ±det(xA +yB +C). The proof of Theorem 4.2 uses the Lax Conjecture on hyperbolic polynomials which was proved only very recently [22], see also [15, 30]. Let Z = diag(z 1,...,zn) be a diagonal matrix. Consequences of Lemma 4.1 are the following”
The lax conjecture is true (2003, background): “A polynomial on R(2) is a real zero polynomial [7] if, for all vectors (y, z) ∈ R(2), the univariate polynomial t 7→ q(ty, tz) has all real roots.”
Multivariate Pólya–Schur classification problems in the Weyl algebra (2006, methodology): “The proof relies on the Lax conjecture that was recently settled in [42] by using in an essential way the results of [ 34 ].”
Interlacing families II: Mixed characteristic polynomials and the Kadison{Singer problem (2013, methodology): “7] and is proved using an adaptation of a result of Helton and Vinnikov [34] by Lewis, Parrilo and Ramana [38].”
Semidefinite Representation of the k-Ellipse (2007, methodology): “Combining our Theorem 1.1 with the Helton-Vinnikov Theorem, we conclude: Corollary 3.1.”