Matrix convex hulls of free semialgebraic sets

Helton, J.; Klep, Igor; McCullough, Scott

doi:10.1090/tran/6560

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