Matrix convex hulls of free semialgebraic sets
HTML articles powered by AMS MathViewer
- by J. William Helton, Igor Klep and Scott McCullough PDF
- Trans. Amer. Math. Soc. 368 (2016), 3105-3139 Request permission
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
- Jim Agler and John E. McCarthy, Global holomorphic functions in several noncommuting variables, Canad. J. Math. 67 (2015), no. 2, 241–285. MR 3314834, DOI 10.4153/CJM-2014-024-1
- William Arveson, Subalgebras of $C^{\ast }$-algebras. II, Acta Math. 128 (1972), no. 3-4, 271–308. MR 394232, DOI 10.1007/BF02392166
- Joseph A. Ball and Vladimir Bolotnikov, Interpolation in the noncommutative Schur-Agler class, J. Operator Theory 58 (2007), no. 1, 83–126. MR 2336046
- Alexander Barvinok, A course in convexity, Graduate Studies in Mathematics, vol. 54, American Mathematical Society, Providence, RI, 2002. MR 1940576, DOI 10.1090/gsm/054
- 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
- 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, DOI 10.1007/978-3-662-03718-8
- 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, DOI 10.1016/j.jfa.2008.09.003
- K. R. Davidson and M. Kennedy, The Choquet boundary of an operator system, preprint http://www.arxiv.org/abs/1303.3252
- 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, DOI 10.1137/100814147
- 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, DOI 10.1007/978-0-387-09686-5_{2}
- 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, DOI 10.1512/iumj.2007.56.2904
- 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, DOI 10.1006/jfan.1996.2958
- Douglas R. Farenick, Pure matrix states on operator systems, Linear Algebra Appl. 393 (2004), 149–173. MR 2098611, DOI 10.1016/j.laa.2004.06.020
- 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, DOI 10.7146/math.scand.a-15225
- 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, DOI 10.1016/j.automatica.2010.02.009
- 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, DOI 10.1007/s10107-010-0425-z
- 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, DOI 10.1137/090746525
- 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, DOI 10.1287/moor.1120.0575
- 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, DOI 10.1007/978-1-4614-0769-0_{5}
- 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, DOI 10.1007/978-3-642-78240-4
- 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, DOI 10.1016/j.aim.2012.04.028
- 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, DOI 10.1007/s10107-012-0525-z
- 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.
- J. William Helton and Scott A. McCullough, A Positivstellensatz for non-commutative polynomials, Trans. Amer. Math. Soc. 356 (2004), no. 9, 3721–3737. MR 2055751, DOI 10.1090/S0002-9947-04-03433-6
- 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, DOI 10.4007/annals.2012.176.2.6
- 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
- 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, DOI 10.1137/07070526X
- J. William Helton and Jiawang Nie, Semidefinite representation of convex sets, Math. Program. 122 (2010), no. 1, Ser. A, 21–64. MR 2533752, DOI 10.1007/s10107-008-0240-y
- J. William Helton and Victor Vinnikov, Linear matrix inequality representation of sets, Comm. Pure Appl. Math. 60 (2007), no. 5, 654–674. MR 2292953, DOI 10.1002/cpa.20155
- Didier Henrion, Semidefinite representation of convex hulls of rational varieties, Acta Appl. Math. 115 (2011), no. 3, 319–327. MR 2823121, DOI 10.1007/s10440-011-9623-9
- 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, DOI 10.1016/j.jfa.2010.10.003
- 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, DOI 10.1090/surv/199
- Craig Kleski, Boundary representations and pure completely positive maps, J. Operator Theory 71 (2014), no. 1, 45–62. MR 3173052, DOI 10.7900/jot.2011oct22.1927
- Jean B. Lasserre, Convex sets with semidefinite representation, Math. Program. 120 (2009), no. 2, Ser. A, 457–477. MR 2505746, DOI 10.1007/s10107-008-0222-0
- Jean Bernard Lasserre, Moments, positive polynomials and their applications, Imperial College Press Optimization Series, vol. 1, Imperial College Press, London, 2010. MR 2589247
- 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, DOI 10.1007/978-0-387-09686-5_{7}
- László Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), no. 1, 1–7. MR 514926, DOI 10.1109/TIT.1979.1055985
- Paul S. Muhly and Baruch Solel, Progress in noncommutative function theory, Sci. China Math. 54 (2011), no. 11, 2275–2294. MR 2859694, DOI 10.1007/s11425-011-4241-6
- 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, DOI 10.1137/1.9781611970791
- Tim Netzer, Daniel Plaumann, and Markus Schweighofer, Exposed faces of semidefinitely representable sets, SIAM J. Optim. 20 (2010), no. 4, 1944–1955. MR 2600247, DOI 10.1137/090750196
- Jiawang Nie and Markus Schweighofer, On the complexity of Putinar’s Positivstellensatz, J. Complexity 23 (2007), no. 1, 135–150. MR 2297019, DOI 10.1016/j.jco.2006.07.002
- 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, DOI 10.1080/00207170210140212
- P. Parrilo, Exact semidefinite representation for genus zero curves, Talk at the Banff workshop Positive Polynomials and Optimization, Banff, Canada, 2006.
- Vern Paulsen, Completely bounded maps and operator algebras, Cambridge Studies in Advanced Mathematics, vol. 78, Cambridge University Press, Cambridge, 2002. MR 1976867
- 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, DOI 10.1137/090760155
- Gelu Popescu, Free holomorphic automorphisms of the unit ball of $B(\scr H)^n$, J. Reine Angew. Math. 638 (2010), 119–168. MR 2595338, DOI 10.1515/CRELLE.2010.005
- Claus Scheiderer, Convex hulls of curves of genus one, Adv. Math. 228 (2011), no. 5, 2606–2622. MR 2838050, DOI 10.1016/j.aim.2011.07.014
- C. Scheiderer, Semidefinite representation for convex hulls of real algebraic curves, preprint http://arxiv.org/abs/1208.3865
- Markus Schweighofer, On the complexity of Schmüdgen’s positivstellensatz, J. Complexity 20 (2004), no. 4, 529–543. MR 2068157, DOI 10.1016/j.jco.2004.01.005
- 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, DOI 10.1155/S1073792804132443
- 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, DOI 10.1515/CRELLE.2010.063
- Corran Webster and Soren Winkler, The Krein-Milman theorem in operator convexity, Trans. Amer. Math. Soc. 351 (1999), no. 1, 307–322. MR 1615970, DOI 10.1090/S0002-9947-99-02364-8
Additional Information
- J. William Helton
- Affiliation: Department of Mathematics, University of California, San Diego, California 92093
- MR Author ID: 84075
- 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
- MR Author ID: 220198
- Email: sam@math.ufl.edu
- 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 - © Copyright 2015 American Mathematical Society
- 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
- MathSciNet review: 3451871