×

Matrix convex hulls of free semialgebraic sets. (English) Zbl 1361.46056

The authors study a noncommutative (free) analog of real algebraic geometry. In particular, they consider matrix convex sets and their projections. A free semialgebraic set which is convex and bounded and open can be represented as the solution of a linear matrix inequality (LMI), so there should be not too many convex free semialgebraic sets. Also, in contrast to the Tarski-Seidenberg theorem in real algebraic geometry over a real closed field, the projection of a free convex semialgebraic set need not be free semialgebraic.
This motivates the authors to the study matrix convex hull of free semialgebraic sets. They present a construction of a sequence of LMI domains in increasingly many variables whose projections are successively finer outer approximations of the matrix hull of a free semialgebraic set. It is based on free analogs of moments and Hankel matrices. The virtues of this construction are demonstrated.

MSC:

46L89 Other “noncommutative” mathematics based on \(C^*\)-algebra theory
46L07 Operator spaces and completely bounded maps
14P10 Semialgebraic sets and related spaces
13J30 Real algebra
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agler, Jim; McCarthy, John E., Global holomorphic functions in several noncommuting variables, Canad. J. Math., 67, 2, 241-285 (2015) · Zbl 1311.32001 · doi:10.4153/CJM-2014-024-1
[2] Arveson, William, Subalgebras of \(C^{\ast } \)-algebras. II, Acta Math., 128, 3-4, 271-308 (1972) · Zbl 0245.46098
[3] Ball, Joseph A.; Bolotnikov, Vladimir, Interpolation in the noncommutative Schur-Agler class, J. Operator Theory, 58, 1, 83-126 (2007) · Zbl 1164.47023
[4] Barvinok, Alexander, A course in convexity, Graduate Studies in Mathematics 54, x+366 pp. (2002), American Mathematical Society, Providence, RI · Zbl 1014.52001
[5] Semidefinite optimization and convex algebraic geometry, MOS-SIAM Series on Optimization 13, xx+476 pp. (2013), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA · Zbl 1260.90006
[6] Bochnak, Jacek; Coste, Michel; Roy, Marie-Fran{\c{c}}oise, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)] 36, x+430 pp. (1998), Springer-Verlag, Berlin · Zbl 0912.14023 · doi:10.1007/978-3-662-03718-8
[7] Curto, Ra{\'u}l E.; Fialkow, Lawrence A., An analogue of the Riesz-Haviland theorem for the truncated moment problem, J. Funct. Anal., 255, 10, 2709-2731 (2008) · Zbl 1158.44003 · doi:10.1016/j.jfa.2008.09.003
[8] [DK+] K. R. Davidson and M. Kennedy, The Choquet boundary of an operator system, preprint \urlhttp://www.arxiv.org/abs/1303.3252 · Zbl 1344.46041
[9] de Klerk, Etienne; Laurent, Monique, On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems, SIAM J. Optim., 21, 3, 824-832 (2011) · Zbl 1230.90199 · doi:10.1137/100814147
[10] de Oliveira, Mauricio C.; Helton, J. William; McCullough, Scott A.; Putinar, Mihai, Engineering systems and free semi-algebraic geometry. Emerging applications of algebraic geometry, IMA Vol. Math. Appl. 149, 17-61 (2009), Springer, New York · Zbl 1156.14331 · doi:10.1007/978-0-387-09686-5\_2
[11] Dym, Harry; Helton, William; McCullough, Scott, Irreducible noncommutative defining polynomials for convex sets have degree four or less, Indiana Univ. Math. J., 56, 3, 1189-1231 (2007) · Zbl 1128.47020 · doi:10.1512/iumj.2007.56.2904
[12] Effros, Edward G.; Winkler, Soren, Matrix convexity: operator analogues of the bipolar and Hahn-Banach theorems, J. Funct. Anal., 144, 1, 117-152 (1997) · Zbl 0897.46046 · doi:10.1006/jfan.1996.2958
[13] Farenick, Douglas R., Pure matrix states on operator systems, Linear Algebra Appl., 393, 149-173 (2004) · Zbl 1073.46044 · doi:10.1016/j.laa.2004.06.020
[14] Farenick, Douglas; Paulsen, Vern I., Operator system quotients of matrix algebras and their tensor products, Math. Scand., 111, 2, 210-243 (2012) · Zbl 1273.46038
[15] Graham, Matthew R.; de Oliveira, Mauricio C., Linear matrix inequality tests for frequency domain inequalities with affine multipliers, Automatica J. IFAC, 46, 5, 897-901 (2010) · Zbl 1191.93106 · doi:10.1016/j.automatica.2010.02.009
[16] Gouveia, Jo{\~a}o; Laurent, Monique; Parrilo, Pablo A.; Thomas, Rekha, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, Math. Program., 133, 1-2, Ser. A, 203-225 (2012) · Zbl 1262.90123 · doi:10.1007/s10107-010-0425-z
[17] Gouveia, Jo{\~a}o; Parrilo, Pablo A.; Thomas, Rekha R., Theta bodies for polynomial ideals, SIAM J. Optim., 20, 4, 2097-2118 (2010) · Zbl 1213.90190 · doi:10.1137/090746525
[18] Gouveia, Jo{\~a}o; Parrilo, Pablo A.; Thomas, Rekha R., Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 2, 248-264 (2013) · Zbl 1291.90172 · doi:10.1287/moor.1120.0575
[19] Gouveia, Jo{\~a}o; Thomas, Rekha, Convex hulls of algebraic sets. Handbook on semidefinite, conic and polynomial optimization, Internat. Ser. Oper. Res. Management Sci. 166, 113-138 (2012), Springer, New York · Zbl 1334.90102 · doi:10.1007/978-1-4614-0769-0\_5
[20] Gr{\`“o}tschel, Martin; Lov{\'”a}sz, L{\'a}szl{\'o}; Schrijver, Alexander, Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics 2, xii+362 pp. (1993), Springer-Verlag, Berlin · Zbl 0837.05001 · doi:10.1007/978-3-642-78240-4
[21] Helton, J. William; Klep, Igor; McCullough, Scott, The convex Positivstellensatz in a free algebra, Adv. Math., 231, 1, 516-534 (2012) · Zbl 1260.14071 · doi:10.1016/j.aim.2012.04.028
[22] Helton, J. William; Klep, Igor; McCullough, Scott, The matricial relaxation of a linear matrix inequality, Math. Program., 138, 1-2, Ser. A, 401-445 (2013) · Zbl 1272.15012 · doi:10.1007/s10107-012-0525-z
[23] [Arvboundary] 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. · Zbl 1457.14123
[24] Helton, J. William; McCullough, Scott A., A Positivstellensatz for non-commutative polynomials, Trans. Amer. Math. Soc., 356, 9, 3721-3737 (electronic) (2004) · Zbl 1071.47005 · doi:10.1090/S0002-9947-04-03433-6
[25] Helton, J. William; McCullough, Scott, Every convex free basic semi-algebraic set has an LMI representation, Ann. of Math. (2), 176, 2, 979-1013 (2012) · Zbl 1260.14011 · doi:10.4007/annals.2012.176.2.6
[26] [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
[27] Helton, J. William; Nie, Jiawang, Sufficient and necessary conditions for semidefinite representability of convex hulls and sets, SIAM J. Optim., 20, 2, 759-791 (2009) · Zbl 1190.14058 · doi:10.1137/07070526X
[28] Helton, J. William; Nie, Jiawang, Semidefinite representation of convex sets, Math. Program., 122, 1, Ser. A, 21-64 (2010) · Zbl 1192.90143 · doi:10.1007/s10107-008-0240-y
[29] Helton, J. William; Vinnikov, Victor, Linear matrix inequality representation of sets, Comm. Pure Appl. Math., 60, 5, 654-674 (2007) · Zbl 1116.15016 · doi:10.1002/cpa.20155
[30] Henrion, Didier, Semidefinite representation of convex hulls of rational varieties, Acta Appl. Math., 115, 3, 319-327 (2011) · Zbl 1279.90128 · doi:10.1007/s10440-011-9623-9
[31] Johnston, Nathaniel; Kribs, David W.; Paulsen, Vern I.; Pereira, Rajesh, Minimal and maximal operator spaces and operator systems in entanglement theory, J. Funct. Anal., 260, 8, 2407-2423 (2011) · Zbl 1252.46051 · doi:10.1016/j.jfa.2010.10.003
[32] Kaliuzhnyi-Verbovetskyi, Dmitry S.; Vinnikov, Victor, Foundations of free noncommutative function theory, Mathematical Surveys and Monographs 199, vi+183 pp. (2014), American Mathematical Society, Providence, RI · Zbl 1312.46003 · doi:10.1090/surv/199
[33] Kleski, Craig, Boundary representations and pure completely positive maps, J. Operator Theory, 71, 1, 45-62 (2014) · Zbl 1349.46061 · doi:10.7900/jot.2011oct22.1927
[34] Lasserre, Jean B., Convex sets with semidefinite representation, Math. Program., 120, 2, Ser. A, 457-477 (2009) · Zbl 1198.14055 · doi:10.1007/s10107-008-0222-0
[35] Lasserre, Jean Bernard, Moments, positive polynomials and their applications, Imperial College Press Optimization Series 1, xxii+361 pp. (2010), Imperial College Press, London · Zbl 1211.90007
[36] Laurent, Monique, Sums of squares, moment matrices and optimization over polynomials. Emerging applications of algebraic geometry, IMA Vol. Math. Appl. 149, 157-270 (2009), Springer, New York · Zbl 1163.13021 · doi:10.1007/978-0-387-09686-5\_7
[37] Lov{\'a}sz, L{\'a}szl{\'o}, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985
[38] Muhly, Paul S.; Solel, Baruch, Progress in noncommutative function theory, Sci. China Math., 54, 11, 2275-2294 (2011) · Zbl 1325.46001 · doi:10.1007/s11425-011-4241-6
[39] Nesterov, Yurii; Nemirovskii, Arkadii, Interior-point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics 13, x+405 pp. (1994), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 0824.90112 · doi:10.1137/1.9781611970791
[40] Netzer, Tim; Plaumann, Daniel; Schweighofer, Markus, Exposed faces of semidefinitely representable sets, SIAM J. Optim., 20, 4, 1944-1955 (2010) · Zbl 1204.13018 · doi:10.1137/090750196
[41] Nie, Jiawang; Schweighofer, Markus, On the complexity of Putinar’s Positivstellensatz, J. Complexity, 23, 1, 135-150 (2007) · Zbl 1143.13028 · doi:10.1016/j.jco.2006.07.002
[42] de Oliveira, M. C.; Geromel, J. C.; Bernussou, J., Extended \(H_2\) and \(H_\infty\) norm characterizations and controller parametrizations for discrete-time systems, Internat. J. Control, 75, 9, 666-679 (2002) · Zbl 1029.93020 · doi:10.1080/00207170210140212
[43] [Par06] P. Parrilo, Exact semidefinite representation for genus zero curves, Talk at the Banff workshop Positive Polynomials and Optimization, Banff, Canada, 2006.
[44] Paulsen, Vern, Completely bounded maps and operator algebras, Cambridge Studies in Advanced Mathematics 78, xii+300 pp. (2002), Cambridge University Press, Cambridge · Zbl 1029.47003
[45] Pironio, S.; Navascu{\'e}s, M.; Ac{\'{\i }}n, A., Convergent relaxations of polynomial optimization problems with noncommuting variables, SIAM J. Optim., 20, 5, 2157-2180 (2010) · Zbl 1228.90073 · doi:10.1137/090760155
[46] Popescu, Gelu, Free holomorphic automorphisms of the unit ball of \(B(\mathcal{H})^n\), J. Reine Angew. Math., 638, 119-168 (2010) · Zbl 1196.47005 · doi:10.1515/CRELLE.2010.005
[47] Scheiderer, Claus, Convex hulls of curves of genus one, Adv. Math., 228, 5, 2606-2622 (2011) · Zbl 1231.14049 · doi:10.1016/j.aim.2011.07.014
[48] [SchArx12] C. Scheiderer, Semidefinite representation for convex hulls of real algebraic curves, preprint \urlhttp://arxiv.org/abs/1208.3865 · Zbl 1390.14173
[49] Schweighofer, Markus, On the complexity of Schm\`“udgen”s positivstellensatz, J. Complexity, 20, 4, 529-543 (2004) · Zbl 1161.68480 · doi:10.1016/j.jco.2004.01.005
[50] Voiculescu, Dan, Free analysis questions. I. Duality transform for the coalgebra of \(\partial_{X\colon B} \), Int. Math. Res. Not., 16, 793-822 (2004) · Zbl 1084.46053 · doi:10.1155/S1073792804132443
[51] Voiculescu, Dan-Virgil, Free analysis questions II: the Grassmannian completion and the series expansions at the origin, J. Reine Angew. Math., 645, 155-236 (2010) · Zbl 1228.46058 · doi:10.1515/CRELLE.2010.063
[52] Webster, Corran; Winkler, Soren, The Krein-Milman theorem in operator convexity, Trans. Amer. Math. Soc., 351, 1, 307-322 (1999) · Zbl 0908.47042 · doi:10.1090/S0002-9947-99-02364-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.