Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Matrix convex hulls of free semialgebraic sets


Authors: J. William Helton, Igor Klep and Scott McCullough
Journal: Trans. Amer. Math. Soc. 368 (2016), 3105-3139
MSC (2010): Primary 46L07, 14P10, 90C22; Secondary 13J30, 46L89
DOI: https://doi.org/10.1090/tran/6560
Published electronically: July 10, 2015
MathSciNet review: 3451871
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This article resides in the realm of the noncommutative (free) analog of real algebraic geometry - the study of polynomial inequalities and equations over the real numbers - with a focus on matrix convex sets $ \mathcal {C}$ and their projections $ \hat {\mathcal {C}}$. A free semialgebraic set which is convex as well as bounded and open can be represented as the solution set of a Linear Matrix Inequality (LMI), a result which suggests that convex free semialgebraic sets are rare. Further, a cornerstone of real algebraic geometry fails in the free setting: The projection of a free convex semialgebraic set need not be free semialgebraic. Both of these results, and the importance of convex approximations in the optimization community, provide impetus and motivation for the study of the matrix convex hull of free semialgebraic sets.

This article presents the construction of a sequence $ {\mathcal {C}}^{(d)}$ of LMI domains in increasingly many variables whose projections $ \hat {\mathcal {C}}^{(d)}$ are successively finer outer approximations of the matrix convex hull of a free semialgebraic set $ \mathcal {D}_p=\{X: p(X)\succeq 0\}$. It is based on free analogs of moments and Hankel matrices. Such an approximation scheme is possibly the best that can be done in general. Indeed, natural noncommutative transcriptions of formulas for certain well-known classical (commutative) convex hulls do not produce the convex hulls in the free case. This failure is illustrated here on one of the simplest free nonconvex $ \mathcal {D}_p$.

A basic question is which free sets $ \hat {\mathcal {S}}$ are the projection of a free semialgebraic set $ \mathcal {S}$? Techniques and results of this paper bear upon this question which is open even for free convex sets.


References [Enhancements On Off] (What's this?)

  • [AM15] Jim Agler and John E. McCarthy, Global holomorphic functions in several noncommuting variables, Canad. J. Math. 67 (2015), no. 2, 241-285. MR 3314834, https://doi.org/10.4153/CJM-2014-024-1
  • [Arv72] William Arveson, Subalgebras of $ C^{\ast } $-algebras. II, Acta Math. 128 (1972), no. 3-4, 271-308. MR 0394232 (52 #15035)
  • [BB07] Joseph A. Ball and Vladimir Bolotnikov, Interpolation in the noncommutative Schur-Agler class, J. Operator Theory 58 (2007), no. 1, 83-126. MR 2336046 (2009j:47032)
  • [Bar02] Alexander Barvinok, A course in convexity, Graduate Studies in Mathematics, vol. 54, American Mathematical Society, Providence, RI, 2002. MR 1940576 (2003j:52001)
  • [BPR13] Grigoriy Blekherman, Pablo A. Parrilo, and Rekha R. Thomas (eds.), Semidefinite optimization and convex algebraic geometry, MOS-SIAM Series on Optimization, vol. 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2013. MR 3075433
  • [BCR98] Jacek Bochnak, Michel Coste, and Marie-Françoise Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36, Springer-Verlag, Berlin, 1998. Translated from the 1987 French original; Revised by the authors. MR 1659509 (2000a:14067)
  • [CF08] Raúl E. Curto and Lawrence A. Fialkow, An analogue of the Riesz-Haviland theorem for the truncated moment problem, J. Funct. Anal. 255 (2008), no. 10, 2709-2731. MR 2464189 (2009i:47039), https://doi.org/10.1016/j.jfa.2008.09.003
  • [DK+] K. R. Davidson and M. Kennedy, The Choquet boundary of an operator system, preprint http://www.arxiv.org/abs/1303.3252
  • [DKL11] Etienne de Klerk and Monique Laurent, On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems, SIAM J. Optim. 21 (2011), no. 3, 824-832. MR 2837553 (2012h:90142), https://doi.org/10.1137/100814147
  • [dOHMP09] Mauricio C. de Oliveira, J. William Helton, Scott A. McCullough, and Mihai Putinar, Engineering systems and free semi-algebraic geometry, Emerging applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York, 2009, pp. 17-61. MR 2500463 (2010d:93045), https://doi.org/10.1007/978-0-387-09686-5_2
  • [DHM07] Harry Dym, William Helton, and Scott McCullough, Irreducible noncommutative defining polynomials for convex sets have degree four or less, Indiana Univ. Math. J. 56 (2007), no. 3, 1189-1231. MR 2333470 (2008d:47033), https://doi.org/10.1512/iumj.2007.56.2904
  • [EW97] Edward G. Effros and Soren Winkler, Matrix convexity: operator analogues of the bipolar and Hahn-Banach theorems, J. Funct. Anal. 144 (1997), no. 1, 117-152. MR 1430718 (98e:46066), https://doi.org/10.1006/jfan.1996.2958
  • [Far04] Douglas R. Farenick, Pure matrix states on operator systems, Linear Algebra Appl. 393 (2004), 149-173. MR 2098611 (2005g:46112), https://doi.org/10.1016/j.laa.2004.06.020
  • [FP12] Douglas Farenick and Vern I. Paulsen, Operator system quotients of matrix algebras and their tensor products, Math. Scand. 111 (2012), no. 2, 210-243. MR 3023524
  • [GO10] Matthew R. Graham and Mauricio C. de Oliveira, Linear matrix inequality tests for frequency domain inequalities with affine multipliers, Automatica J. IFAC 46 (2010), no. 5, 897-901. MR 2877163 (2012m:93101), https://doi.org/10.1016/j.automatica.2010.02.009
  • [GLPT12] João Gouveia, Monique Laurent, Pablo A. Parrilo, and Rekha Thomas, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, Math. Program. 133 (2012), no. 1-2, Ser. A, 203-225. MR 2921097, https://doi.org/10.1007/s10107-010-0425-z
  • [GPT10] João Gouveia, Pablo A. Parrilo, and Rekha R. Thomas, Theta bodies for polynomial ideals, SIAM J. Optim. 20 (2010), no. 4, 2097-2118. MR 2630035 (2011m:90107), https://doi.org/10.1137/090746525
  • [GPT12] João Gouveia, Pablo A. Parrilo, and Rekha R. Thomas, Lifts of convex sets and cone factorizations, Math. Oper. Res. 38 (2013), no. 2, 248-264. MR 3062007, https://doi.org/10.1287/moor.1120.0575
  • [GT12] João Gouveia and Rekha Thomas, Convex hulls of algebraic sets, Handbook on semidefinite, conic and polynomial optimization, Internat. Ser. Oper. Res. Management Sci., vol. 166, Springer, New York, 2012, pp. 113-138. MR 2894693, https://doi.org/10.1007/978-1-4614-0769-0_5
  • [GLS93] Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, 2nd ed., Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR 1261419 (95e:90001)
  • [HKM12] J. William Helton, Igor Klep, and Scott McCullough, The convex Positivstellensatz in a free algebra, Adv. Math. 231 (2012), no. 1, 516-534. MR 2935397, https://doi.org/10.1016/j.aim.2012.04.028
  • [HKM13] J. William Helton, Igor Klep, and Scott McCullough, The matricial relaxation of a linear matrix inequality, Math. Program. 138 (2013), no. 1-2, Ser. A, 401-445. MR 3034812, https://doi.org/10.1007/s10107-012-0525-z
  • [HKM+] J. W. Helton, I. Klep, and S. McCullough, The tracial Hahn-Banach Theorem, polar duals, matrix convex sets, and projections of free spectrahedra, preprint, http://arxiv.org/abs/1407.8198.
  • [HM04] J. William Helton and Scott A. McCullough, A Positivstellensatz for non-commutative polynomials, Trans. Amer. Math. Soc. 356 (2004), no. 9, 3721-3737 (electronic). MR 2055751 (2005c:47006), https://doi.org/10.1090/S0002-9947-04-03433-6
  • [HM12] J. William Helton and Scott McCullough, Every convex free basic semi-algebraic set has an LMI representation, Ann. of Math. (2) 176 (2012), no. 2, 979-1013. MR 2950768, https://doi.org/10.4007/annals.2012.176.2.6
  • [HN08] J. W. Helton and J. Nie, Structured semidefinite representation of some convex sets, in: 47th IEEE Conference on Decision and Control (CDC) (2008) 4797-4800
  • [HN09] J. William Helton and Jiawang Nie, Sufficient and necessary conditions for semidefinite representability of convex hulls and sets, SIAM J. Optim. 20 (2009), no. 2, 759-791. MR 2515796 (2010i:14105), https://doi.org/10.1137/07070526X
  • [HN10] J. William Helton and Jiawang Nie, Semidefinite representation of convex sets, Math. Program. 122 (2010), no. 1, Ser. A, 21-64. MR 2533752 (2010j:90103), https://doi.org/10.1007/s10107-008-0240-y
  • [HV07] J. William Helton and Victor Vinnikov, Linear matrix inequality representation of sets, Comm. Pure Appl. Math. 60 (2007), no. 5, 654-674. MR 2292953 (2009a:93050), https://doi.org/10.1002/cpa.20155
  • [Hen11] Didier Henrion, Semidefinite representation of convex hulls of rational varieties, Acta Appl. Math. 115 (2011), no. 3, 319-327. MR 2823121 (2012f:14112), https://doi.org/10.1007/s10440-011-9623-9
  • [JKPP11] Nathaniel Johnston, David W. Kribs, Vern I. Paulsen, and Rajesh Pereira, Minimal and maximal operator spaces and operator systems in entanglement theory, J. Funct. Anal. 260 (2011), no. 8, 2407-2423. MR 2772376 (2012c:46140), https://doi.org/10.1016/j.jfa.2010.10.003
  • [KVV14] Dmitry S. Kaliuzhnyi-Verbovetskyi and Victor Vinnikov, Foundations of free noncommutative function theory, Mathematical Surveys and Monographs, vol. 199, American Mathematical Society, Providence, RI, 2014. MR 3244229
  • [Kls+] Craig Kleski, Boundary representations and pure completely positive maps, J. Operator Theory 71 (2014), no. 1, 45-62. MR 3173052, https://doi.org/10.7900/jot.2011oct22.1927
  • [Las09a] Jean B. Lasserre, Convex sets with semidefinite representation, Math. Program. 120 (2009), no. 2, Ser. A, 457-477. MR 2505746 (2010i:52003), https://doi.org/10.1007/s10107-008-0222-0
  • [Las09b] Jean Bernard Lasserre, Moments, positive polynomials and their applications, Imperial College Press Optimization Series, vol. 1, Imperial College Press, London, 2010. MR 2589247 (2011c:90001)
  • [Lau09] Monique Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York, 2009, pp. 157-270. MR 2500468 (2010j:13054), https://doi.org/10.1007/978-0-387-09686-5_7
  • [Lov79] László Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), no. 1, 1-7. MR 514926 (81g:05095), https://doi.org/10.1109/TIT.1979.1055985
  • [MS11] Paul S. Muhly and Baruch Solel, Progress in noncommutative function theory, Sci. China Math. 54 (2011), no. 11, 2275-2294. MR 2859694 (2012j:46002), https://doi.org/10.1007/s11425-011-4241-6
  • [NN94] Yurii Nesterov and Arkadii Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics, vol. 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR 1258086 (94m:90005)
  • [NPS10] Tim Netzer, Daniel Plaumann, and Markus Schweighofer, Exposed faces of semidefinitely representable sets, SIAM J. Optim. 20 (2010), no. 4, 1944-1955. MR 2600247 (2011c:90061), https://doi.org/10.1137/090750196
  • [NiS07] Jiawang Nie and Markus Schweighofer, On the complexity of Putinar's Positivstellensatz, J. Complexity 23 (2007), no. 1, 135-150. MR 2297019 (2008b:14095), https://doi.org/10.1016/j.jco.2006.07.002
  • [OGB02] M. C. de Oliveira, J. C. Geromel, and J. Bernussou, Extended $ H_2$ and $ H_\infty $ norm characterizations and controller parametrizations for discrete-time systems, Internat. J. Control 75 (2002), no. 9, 666-679. MR 1916432 (2003f:93037), https://doi.org/10.1080/00207170210140212
  • [Par06] P. Parrilo, Exact semidefinite representation for genus zero curves, Talk at the Banff workshop Positive Polynomials and Optimization, Banff, Canada, 2006.
  • [Pau02] Vern Paulsen, Completely bounded maps and operator algebras, Cambridge Studies in Advanced Mathematics, vol. 78, Cambridge University Press, Cambridge, 2002. MR 1976867 (2004c:46118)
  • [PNA10] S. Pironio, M. Navascués, and A. Acín, Convergent relaxations of polynomial optimization problems with noncommuting variables, SIAM J. Optim. 20 (2010), no. 5, 2157-2180. MR 2650843 (2011d:90075), https://doi.org/10.1137/090760155
  • [Poe10] Gelu Popescu, Free holomorphic automorphisms of the unit ball of $ B(\mathcal {H})^n$, J. Reine Angew. Math. 638 (2010), 119-168. MR 2595338 (2012c:46161), https://doi.org/10.1515/CRELLE.2010.005
  • [Sce11] Claus Scheiderer, Convex hulls of curves of genus one, Adv. Math. 228 (2011), no. 5, 2606-2622. MR 2838050 (2012i:14070), https://doi.org/10.1016/j.aim.2011.07.014
  • [Sce+] C. Scheiderer, Semidefinite representation for convex hulls of real algebraic curves, preprint http://arxiv.org/abs/1208.3865
  • [Scw04] Markus Schweighofer, On the complexity of Schmüdgen's positivstellensatz, J. Complexity 20 (2004), no. 4, 529-543. MR 2068157 (2005g:14109), https://doi.org/10.1016/j.jco.2004.01.005
  • [Voi04] Dan Voiculescu, Free analysis questions. I. Duality transform for the coalgebra of $ \partial _{X\colon B}$, Int. Math. Res. Not. 16 (2004), 793-822. MR 2036956 (2005a:46140), https://doi.org/10.1155/S1073792804132443
  • [Voi10] Dan-Virgil Voiculescu, Free analysis questions II: the Grassmannian completion and the series expansions at the origin, J. Reine Angew. Math. 645 (2010), 155-236. MR 2673426 (2012b:46144), https://doi.org/10.1515/CRELLE.2010.063
  • [WW99] Corran Webster and Soren Winkler, The Krein-Milman theorem in operator convexity, Trans. Amer. Math. Soc. 351 (1999), no. 1, 307-322. MR 1615970 (99d:46079), https://doi.org/10.1090/S0002-9947-99-02364-8

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 46L07, 14P10, 90C22, 13J30, 46L89

Retrieve articles in all journals with MSC (2010): 46L07, 14P10, 90C22, 13J30, 46L89


Additional Information

J. William Helton
Affiliation: Department of Mathematics, University of California, San Diego, California 92093
Email: helton@math.ucsd.edu

Igor Klep
Affiliation: Department of Mathematics, The University of Auckland, New Zealand
Email: igor.klep@auckland.ac.nz

Scott McCullough
Affiliation: Department of Mathematics, University of Florida, Gainesville, Florida 32611-8105
Email: sam@math.ufl.edu

DOI: https://doi.org/10.1090/tran/6560
Keywords: Convex hull, Linear Matrix Inequality (LMI), LMI domain, spectrahedron, spectrahedrop, semialgebraic set, free real algebraic geometry, noncommutative polynomial
Received by editor(s): February 8, 2014
Published electronically: July 10, 2015
Additional Notes: The first author’s research was supported by National Science Foundation (NSF) grant DMS 1201498, and the Ford Motor Co.
The second author was supported by the Marsden Fund Council of the Royal Society of New Zealand and partially supported by Slovenian Research Agency grants P1-0222, L1-4292 and L1-6722. Part of this research was done while the author was on leave from the University of Maribor
The third author’s research was supported by NSF grant DMS 1101137
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society