Every convex free basic semi-algebraic set has an LMI representation

Pages 979-1013 from Volume 176 (2012), Issue 2 by J. William Helton, Scott McCullough

Abstract

The (matricial) solution set of a Linear Matrix Inequality (LMI) is a convex free basic open semi-algebraic set. The main theorem of this paper is a converse, each such set arises from some LMI. The result has implications for semi-definite programming and systems engineering as well as for free semi-algebraic geometry.

  • [Ar69] Go to document W. B. Arveson, "On subalgebras of $C^{\ast} $-algebras," Bull. Amer. Math. Soc., vol. 75, pp. 790-794, 1969.
    @article {Ar69, MRKEY = {0247483},
      AUTHOR = {Arveson, William B.},
      TITLE = {On subalgebras of {$C\sp{\ast} $}-algebras},
      JOURNAL = {Bull. Amer. Math. Soc.},
      FJOURNAL = {Bulletin of the American Mathematical Society},
      VOLUME = {75},
      YEAR = {1969},
      PAGES = {790--794},
      ISSN = {0002-9904},
      MRCLASS = {46.65},
      MRNUMBER = {0247483},
      MRREVIEWER = {T. W. Palmer},
      ZBLNUMBER = {0212.15402},
      DOI = {10.1090/S0002-9904-1969-12293-7},
     }
  • [Ar72] Go to document W. B. Arveson, "Subalgebras of $C^{\ast} $-algebras. II," Acta Math., vol. 128, iss. 3-4, pp. 271-308, 1972.
    @article {Ar72, MRKEY = {0394232},
      AUTHOR = {Arveson, William B.},
      TITLE = {Subalgebras of {$C\sp{\ast} $}-algebras. {II}},
      JOURNAL = {Acta Math.},
      FJOURNAL = {Acta Mathematica},
      VOLUME = {128},
      YEAR = {1972},
      NUMBER = {3-4},
      PAGES = {271--308},
      ISSN = {0001-5962},
      MRCLASS = {46L15 (47A45)},
      MRNUMBER = {0394232},
      MRREVIEWER = {R. G. Douglas},
      ZBLNUMBER = {0245.46098},
      DOI = {10.1007/BF02392166},
     }
  • [Ar08] Go to document W. B. Arveson, "The noncommutative Choquet boundary," J. Amer. Math. Soc., vol. 21, iss. 4, pp. 1065-1084, 2008.
    @article {Ar08, MRKEY = {2425180},
      AUTHOR = {Arveson, William B.},
      TITLE = {The noncommutative {C}hoquet boundary},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {21},
      YEAR = {2008},
      NUMBER = {4},
      PAGES = {1065--1084},
      ISSN = {0894-0347},
      MRCLASS = {46L07 (46L30 46L52)},
      MRNUMBER = {2425180},
      MRREVIEWER = {Christian Le Merdy},
      DOI = {10.1090/S0894-0347-07-00570-X},
      ZBLNUMBER = {1207.46052},
      }
  • [BCR98] J. Bochnak, M. Coste, and M. Roy, Real Algebraic Geometry, New York: Springer-Verlag, 1998, vol. 36.
    @book {BCR98, MRKEY = {1659509},
      AUTHOR = {Bochnak, Jacek and Coste, Michel and Roy, Marie-Fran{ç}oise},
      TITLE = {Real Algebraic Geometry},
      SERIES = {Ergeb. Math. Grenzgeb.},
      VOLUME = {36},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1998},
      PAGES = {x+430},
      ISBN = {3-540-64663-9},
      MRCLASS = {14Pxx (11E25 32C05 58A07)},
      MRNUMBER = {1659509},
      MRREVIEWER = {A. Tognoli},
      ZBLNUMBER = {0912.14023},
      }
  • [BL04] Go to document D. P. Blecher and C. Le Merdy, Operator Algebras and their Modules—An Operator Space Approach, Oxford: The Clarendon Press Oxford University Press, 2004, vol. 30.
    @book {BL04, MRKEY = {2111973},
      AUTHOR = {Blecher, David P. and Le Merdy, Christian},
      TITLE = {Operator Algebras and their Modules---An Operator Space Approach},
      SERIES = {London Math. Soc. Monogr. (NS)},
      VOLUME = {30},
      PUBLISHER = {The Clarendon Press Oxford University Press},
      ADDRESS = {Oxford},
      YEAR = {2004},
      PAGES = {x+387},
      ISBN = {0-19-852659-8},
      MRCLASS = {46L07 (47L30)},
      MRNUMBER = {2111973},
      MRREVIEWER = {Narutaka Ozawa},
      DOI = {10.1093/acprof:oso/9780198526599.001.0001},
      ZBLNUMBER = {1061.47002},
      }
  • [DHM07] Go to document H. Dym, W. Helton, and S. McCullough, "Irreducible noncommutative defining polynomials for convex sets have degree four or less," Indiana Univ. Math. J., vol. 56, iss. 3, pp. 1189-1231, 2007.
    @article {DHM07, MRKEY = {2333470},
      AUTHOR = {Dym, Harry and Helton, William and McCullough, Scott},
      TITLE = {Irreducible noncommutative defining polynomials for convex sets have degree four or less},
      JOURNAL = {Indiana Univ. Math. J.},
      FJOURNAL = {Indiana University Mathematics Journal},
      VOLUME = {56},
      YEAR = {2007},
      NUMBER = {3},
      PAGES = {1189--1231},
      ISSN = {0022-2518},
      CODEN = {IUMJAB},
      MRCLASS = {47A56 (14P10 16S10 47N10)},
      MRNUMBER = {2333470},
      MRREVIEWER = {Joseph A. Ball},
      DOI = {10.1512/iumj.2007.56.2904},
      ZBLNUMBER = {1128.47020},
      }
  • [EW97] Go to document E. G. Effros and S. Winkler, "Matrix convexity: operator analogues of the bipolar and Hahn-Banach theorems," J. Funct. Anal., vol. 144, iss. 1, pp. 117-152, 1997.
    @article {EW97, MRKEY = {1430718},
      AUTHOR = {Effros, Edward G. and Winkler, Soren},
      TITLE = {Matrix convexity: operator analogues of the bipolar and {H}ahn-{B}anach theorems},
      JOURNAL = {J. Funct. Anal.},
      FJOURNAL = {Journal of Functional Analysis},
      VOLUME = {144},
      YEAR = {1997},
      NUMBER = {1},
      PAGES = {117--152},
      ISSN = {0022-1236},
      CODEN = {JFUAAW},
      MRCLASS = {46L05 (46B28 47D15)},
      MRNUMBER = {1430718},
      MRREVIEWER = {Seung-Hyeok Kye},
      DOI = {10.1006/jfan.1996.2958},
      ZBLNUMBER = {0897.46046},
      }
  • [HV07] Go to document W. J. Helton and V. Vinnikov, "Linear matrix inequality representation of sets," Comm. Pure Appl. Math., vol. 60, iss. 5, pp. 654-674, 2007.
    @article {HV07, MRKEY = {2292953},
      AUTHOR = {Helton, J. William and Vinnikov, Victor},
      TITLE = {Linear matrix inequality representation of sets},
      JOURNAL = {Comm. Pure Appl. Math.},
      FJOURNAL = {Communications on Pure and Applied Mathematics},
      VOLUME = {60},
      YEAR = {2007},
      NUMBER = {5},
      PAGES = {654--674},
      ISSN = {0010-3640},
      CODEN = {CPAMA},
      MRCLASS = {93B40 (15A39 52A20)},
      MRNUMBER = {2292953},
      MRREVIEWER = {Driss Mentagui},
      DOI = {10.1002/cpa.20155},
      ZBLNUMBER = {1116.15016},
      }
  • [Ne06] Go to document A. Nemirovski, "Advances in convex optimization: conic programming," in International Congress of Mathematicians. Vol. I, Eur. Math. Soc., Zürich, 2007, pp. 413-444.
    @incollection {Ne06, MRKEY = {2334199},
      AUTHOR = {Nemirovski, Arkadi},
      TITLE = {Advances in convex optimization: conic programming},
      BOOKTITLE = {International {C}ongress of {M}athematicians. {V}ol. {I}},
      PAGES = {413--444},
      PUBLISHER = {Eur. Math. Soc., Zürich},
      YEAR = {2007},
      MRCLASS = {90C25 (90C22 90C51)},
      MRNUMBER = {2334199},
      DOI = {10.4171/022-1/17},
      ZBLNUMBER = {1135.90379},
      }
  • [Pa02] V. Paulsen, Completely Bounded Maps and Operator Algebras, Cambridge: Cambridge Univ. Press, 2002, vol. 78.
    @book {Pa02, MRKEY = {1976867},
      AUTHOR = {Paulsen, Vern},
      TITLE = {Completely Bounded Maps and Operator Algebras},
      SERIES = {Cambridge Studies Adv. Math.},
      VOLUME = {78},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {2002},
      PAGES = {xii+300},
      ISBN = {0-521-81669-6},
      MRCLASS = {46L07 (47A20 47L30)},
      MRNUMBER = {1976867},
      MRREVIEWER = {Christian Le Merdy},
      ZBLNUMBER = {1029.47003},
      }
  • [Pi03] G. Pisier, Introduction to Operator Space Theory, Cambridge: Cambridge Univ. Press, 2003, vol. 294.
    @book {Pi03, MRKEY = {2006539},
      AUTHOR = {Pisier, Gilles},
      TITLE = {Introduction to Operator Space Theory},
      SERIES = {London Math. Soc. Lect. Note Ser.},
      VOLUME = {294},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {2003},
      PAGES = {viii+478},
      ISBN = {0-521-81165-1},
      MRCLASS = {46L07 (46B28 47L25)},
      MRNUMBER = {2006539},
      MRREVIEWER = {Marius Junge},
      ZBLNUMBER = {1093.46001},
      }
  • [Vo04] Go to document D. Voiculescu, "Free analysis questions. I. Duality transform for the coalgebra of $\partial_{X\colon B}$," Int. Math. Res. Not., vol. 2004, p. no. 16, 793-822.
    @article {Vo04, MRKEY = {2036956},
      AUTHOR = {Voiculescu, Dan},
      TITLE = {Free analysis questions. {I}. {D}uality transform for the coalgebra of {$\partial\sb {X\colon B}$}},
      JOURNAL = {Int. Math. Res. Not.},
      FJOURNAL = {International Mathematics Research Notices},
      PAGES = {no.~16, 793--822},
      ISSN = {1073-7928},
      MRCLASS = {46L54 (16W30 60A05)},
      MRNUMBER = {2036956},
      MRREVIEWER = {Dimitri Y. Shlyakhtenko},
      DOI = {10.1155/S1073792804132443},
      VOLUME = {2004},
      ZBLNUMBER = {1084.46053},
     }
  • [Vo05] D. Voiculescu, "Aspects of free probability," in XIVth International Congress on Mathematical Physics, World Sci. Publ., Hackensack, NJ, 2005, pp. 145-157.
    @incollection {Vo05, MRKEY = {2227827},
      AUTHOR = {Voiculescu, Dan},
      TITLE = {Aspects of free probability},
      BOOKTITLE = {X{IV}th {I}nternational {C}ongress on {M}athematical {P}hysics},
      PAGES = {145--157},
      PUBLISHER = {World Sci. Publ., Hackensack, NJ},
      YEAR = {2005},
      MRCLASS = {46L54},
      MRNUMBER = {2227827},
      MRREVIEWER = {Todd Kemp},
      }

Keywords
, , , , , , ,
DOI
https://doi.org/10.4007/annals.2012.176.2.6
MR
2950768
zbMATH
06093945
Milestones
Received: 10 December 2009
Revised: 8 July 2011
Accepted: 11 April 2012
Published online: 1 September 2012

Authors

J. William Helton

Department of Mathematics, University of California San Diego, 9500 Gilman Drive #0112, La Jolla, CA 92093-0112

Scott McCullough

Department of Mathematics, University of Florida, 490 Little Hall, Gainesville, FL 32611-8105