Convexity and semidefinite programming in dimension-free matrix unknowns. (English) Zbl 1334.90103
Anjos, Miguel F. (ed.) et al., Handbook on semidefinite, conic and polynomial optimization. New York, NY: Springer (ISBN 978-1-4614-0768-3/hbk; 978-1-4614-0769-0/ebook). International Series in Operations Research & Management Science 166, 377-405 (2012).
Summary: One of the main applications of semidefinite programming lies in linear systems and control theory. Many problems in this subject, certt leastinly the textbook classics, have matrices as variables, and the formulas naturally contain non-commutative polynomials in matrices. These polynomials depend only on the system layout and do not change with the size of the matrices involved, hence such problems are called “dimension-free”. Analyzing dimension-free problems has led to the development recently of a non-commutative (nc) real algebraic geometry (RAG) which, when combined with convexity, produces dimension-free Semidefinite Programming. This article surveys what is known about convexity in the non-commutative setting and nc SDP and includes a brief survey of nc RAG. Typically, the qualitative properties of the non-commutative case are much cleaner than those of their scalar counterparts – variables in \({\mathbb{R}}^{g}\). Indeed we describe how reltxation of scalar variables by matrix variables in several natural situations results in a beautiful structure.
For the entire collection see [Zbl 1235.90002].
For the entire collection see [Zbl 1235.90002].
Software:
NCAlgebraReferences:
| [1] | Arveson, W., Subalgebras of C^∗-algebras, Acta Mathematica, 123, 141-224 (1969) · Zbl 0194.15701 · doi:10.1007/BF02392388 |
| [2] | Arveson, W., Subalgebras of C^∗-algebras, II. Acta Mathematica, 128, 3-4, 271-308 (1972) · Zbl 0245.46098 · doi:10.1007/BF02392166 |
| [3] | Arveson, W., The noncommutative Choquet boundary, Journal of the American Mathematical Society, 21, 4, 1065-1084 (2008) · Zbl 1207.46052 · doi:10.1090/S0894-0347-07-00570-X |
| [4] | Bochnack, J., Coste, M., Roy, M.-F.: Real algebraic geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge A Series of Modern Surveys in Mathematics, Vol. 36. Springer-Verlag, Berlin (1998) · Zbl 0912.14023 |
| [5] | Ball, JA; Groenewald, G.; Malakorn, T., Bounded real lemma for structured noncommutative multidimensional linear systems and robust control, Multidimensional Systems And Signal Processing, 17, 2-3, 119-150 (2006) · Zbl 1125.93334 · doi:10.1007/s11045-005-6730-7 |
| [6] | Burgdorf, S., Klep, I.: The truncated tracial moment problem. To appear in the Journal of Operator Theory, http://arxiv.org/abs/1001.3679 · Zbl 1260.47016 |
| [7] | Blecher, DP; Le Merdy, C., Operator algebras and their modules—an operator space approach, London Mathematical Society Monographs (2004), Oxford: The Clarendon Press Oxford University Press, Oxford · Zbl 1061.47002 · doi:10.1093/acprof:oso/9780198526599.001.0001 |
| [8] | Bessis, D.; Moussa, P.; Villani, M., Monotonic converging variational approximations to the functional integrals in quantum statistical mechanics, Journal of Mathematical Physics, 16, 11, 2318-2325 (1975) · Zbl 0976.82501 · doi:10.1063/1.522463 |
| [9] | Ben-Tal, A.; Nemirovski, A., On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty, SIAM Journal on Optimization, 12, 3, 811-833 (2002) · Zbl 1008.90034 · doi:10.1137/S1052623400374756 |
| [10] | Camino, JF; Helton, JW; Skelton, RE; Ye, J., Matrix inequalities: a symbolic procedure to determine convexity automatically, Integral Equation and Operator Theory, 46, 4, 399-454 (2003) · Zbl 1046.68139 · doi:10.1007/s00020-001-1147-7 |
| [11] | Cafuta, K.; Klep, I.; Povh, J., NCSOStools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials, Optimization methods and Software, 26, 3, 363-380 (2011) · Zbl 1226.90063 · doi:10.1080/10556788.2010.544312 |
| [12] | Connes, A., Classification of injective factors. Cases { II}1, { II} ∞ , { III}λ, λ≠1, Annals of Mathematics, 104, 73-115 (1976) · Zbl 0343.46042 · doi:10.2307/1971057 |
| [13] | Effros, EG; Winkler, S., Matrix convexity: operator analogues of the bipolar and Hahn-Banach theorems, Journal of Functional Analysis, 144, 1, 117-152 (1997) · Zbl 0897.46046 · doi:10.1006/jfan.1996.2958 |
| [14] | Hay, DM; Helton, JW; Lim, A.; McCullough, S., Non-commutative partial matrix convexity, Indiana University Mathematics Journal, 57, 6, 2815-2842 (2008) · Zbl 1171.15020 · doi:10.1512/iumj.2008.57.3638 |
| [15] | Helton, JW, ‘Positive’ noncommutative polynomials are sums of squares, Annals Of Mathematics, 156, 2, 675-694 (2002) · Zbl 1033.12001 · doi:10.2307/3597203 |
| [16] | Helton, J.W., de Oliveira, M.C., Stankus, M., Miller, R.L.: NCAlgebra, 2010 release edition. Available from http://math.ucsd.edu/ ncalg (2010) |
| [17] | Helton, JW; Klep, I.; McCullough, S., Analytic mappings between noncommutative pencil balls, Journal of Mathematical Analysis and Applications, 376, 2, 407-428 (2011) · Zbl 1210.47039 · doi:10.1016/j.jmaa.2010.11.040 |
| [18] | Helton, J.W., Klep, I., McCullough, S.: The matricial relaxation of a linear matrix inequality. Preprint, available from http://arxiv.org/abs/1003.0908 · Zbl 1272.15012 |
| [19] | Helton, JW; Klep, I.; McCullough, S., Proper analytic free maps, Journal of Functional Analysis, 260, 5, 1476-1490 (2011) · Zbl 1215.47011 · doi:10.1016/j.jfa.2010.11.007 |
| [20] | Helton, JW; Klep, I.; McCullough, S.; Slinglend, N., Noncommutative ball maps, Journal of Functional Analysis, 257, 1, 47-87 (2009) · Zbl 1179.47012 · doi:10.1016/j.jfa.2009.03.008 |
| [21] | Helton, J.W., McCullough, S.: Every free basic convex semi-algebraic set has an LMI representation. Preprint, available from http://arxiv.org/abs/0908.4352 · Zbl 1260.14011 |
| [22] | Helton, JW; McCullough, S., Convex noncommutative polynomials have degree two or less, SIAM Journal on Matrix Analysis and Applications, 25, 4, 1124-1139 (2003) · Zbl 1102.47009 · doi:10.1137/S0895479803421999 |
| [23] | Helton, JW; McCullough, S., A positivstellensatz for non-commutative polynomials, Transactions of The American Mathematical Society, 356, 9, 3721-3737 (2004) · Zbl 1071.47005 · doi:10.1090/S0002-9947-04-03433-6 |
| [24] | Helton, JW; McCullough, SA; Putinar, M., A non-commutative positivstellensatz on isometries, Journal Für Die Reine Und Angewandte Mathematik, 568, 71-80 (2004) · Zbl 1039.47004 |
| [25] | Helton, JW; McCullough, S.; Putinar, M., Non-negative hereditary polynomials in a free *-algebra, Mathematische Zeitschrift, 250, 3, 515-522 (2005) · Zbl 1103.47012 · doi:10.1007/s00209-004-0758-5 |
| [26] | Helton, JW; McCullough, S.; Putinar, M., Strong majorization in a free *-algebra, Mathematische Zeitschrift, 255, 3, 579-596 (2007) · Zbl 1117.47010 · doi:10.1007/s00209-006-0032-0 |
| [27] | Helton, JW; McCullough, SA; Vinnikov, V., Noncommutative convexity arises from linear matrix inequalities, Journal Of Functional Analysis, 240, 1, 105-191 (2006) · Zbl 1135.47005 · doi:10.1016/j.jfa.2006.03.018 |
| [28] | Helton, JW; Putinar, M.; Bakonyi, M.; Gheondea, A.; Putinar, M.; Rovnyak, J., Positive polynomials in scalar and matrix variables, the spectral theorem, and optimization, Operator Theory, Structured Matrices, and Dilations. A Volume Dedicated to the Memory of Tiberiu Constantinescu, 229-306 (2007), Bucharest: Theta, Bucharest · Zbl 1199.47001 |
| [29] | Helton, JW; Vinnikov, V., Linear matrix inequality representation of sets, Communications On Pure And Applied Mathematics, 60, 5, 654-674 (2007) · Zbl 1116.15016 · doi:10.1002/cpa.20155 |
| [30] | Klep, I.; Schweighofer, M., A nichtnegativstellensatz for polynomials in noncommuting variables, Israel Journal of Mathematics, 161, 1, 17-27 (2007) · Zbl 1171.47060 · doi:10.1007/s11856-007-0070-2 |
| [31] | Klep, I.; Schweighofer, M., Connes’ embedding conjecture and sums of Hermitian squares, Advances in Mathematics, 217, 1816-1837 (2008) · Zbl 1184.46055 · doi:10.1016/j.aim.2007.09.016 |
| [32] | Klep, I.; Schweighofer, M., Sums of Hermitian squares and the BMV conjecture, Journal of Statistical Physics, 133, 4, 739-760 (2008) · Zbl 1158.15018 · doi:10.1007/s10955-008-9632-x |
| [33] | Kaliuzhnyi-Verbovetskyi, DS; Vinnikov, V., Singularities of rational functions and minimal factorizations: the noncommutative and the commutative setting, Linear Algebra and its Applications, 430, 4, 869-889 (2009) · Zbl 1217.47032 · doi:10.1016/j.laa.2008.08.027 |
| [34] | Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11, 3, 796-817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802 |
| [35] | Lewis, A.S., Parrilo, P.A., Ramana, M.V.: The Lax conjecture is true. roceedings of the American Mathematical Society 133(9), 2495-2499 (2005) · Zbl 1073.90029 |
| [36] | McCullough, S., Factorization of operator-valued polynomials in several non-commuting variables, Linear Algebra and its Applications, 326, 1-3, 193-203 (2001) · Zbl 0980.47024 · doi:10.1016/S0024-3795(00)00285-8 |
| [37] | Navascués, M., Pironio, S., Acín, A.: SDP relaxations for non-commutative polynomial optimization. this volume. · Zbl 1334.90113 |
| [38] | Parrilo, P.A.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology (2000) |
| [39] | Paulsen, V., Completely bounded maps and operator algebras, Cambridge Studies in Advanced Mathematics (2002), Cambridge: Cambridge University Press, Cambridge · Zbl 1029.47003 |
| [40] | Prestel, A., Delzell, C.N.: Positive polynomials. From Hilbert’s 17th problem to real algebra. Springer Monographs in Mathematics. Springer, Berlin (2001) · Zbl 0987.13016 |
| [41] | Pisier, G., Introduction to operator space theory, London Mathematical Society Lecture Note Series (2003), Cambridge: Cambridge University Press, Cambridge · Zbl 1093.46001 · doi:10.1017/CBO9781107360235 |
| [42] | Pironio, S.; Navascués, M.; Acín, A., Convergent relaxations of polynomial optimization problems with noncommuting variables, SIAM Journal on Optimization, 20, 5, 2157-2180 (2010) · Zbl 1228.90073 · doi:10.1137/090760155 |
| [43] | Popescu, G., Noncommutative transforms and free pluriharmonic functions, Advances in Mathematics, 220, 3, 831-893 (2009) · Zbl 1169.47010 · doi:10.1016/j.aim.2008.09.019 |
| [44] | Popescu, G., Free holomorphic functions on the unit ball of B(H)^n, II. Journal of Functional Analysis, 258, 5, 1513-1578 (2010) · Zbl 1197.47014 · doi:10.1016/j.jfa.2009.10.014 |
| [45] | Putinar, M., Positive polynomials on compact semi-algebraic sets, Indiana University Mathematics Journal, 42, 3, 969-984 (1993) · Zbl 0796.12002 · doi:10.1512/iumj.1993.42.42045 |
| [46] | Schmüdgen, K., A strict Positivstellensatz for the Weyl algebra, Math. Ann., 331, 4, 779-794 (2005) · Zbl 1137.47030 · doi:10.1007/s00208-004-0604-4 |
| [47] | Schmüdgen, K., Savchuk, Y.: Unbounded induced representations of ∗ -algebras. Preprint, http://arxiv.org/abs/0806.2428 · Zbl 1410.16037 |
| [48] | Skelton, RE; Iwasaki, T.; Grigoriadis, KM, A unified algebraic approach to linear control design (1998), London: The Taylor & Francis Systems and Control Book Series. Taylor & Francis Ltd., London |
| [49] | Voiculescu, D., Free analysis questions II: The Grassmannian completion and the series expansions at the origin, Journal Für Die Reine Und Angewandte Mathematik, 645, 155-236 (2010) · Zbl 1228.46058 |
| [50] | Voiculescu, D., Free analysis questions. I. Duality transform for the coalgebra of ∂, International Mathematics Research Notices, 16, 793-822 (2004) · Zbl 1084.46053 · doi:10.1155/S1073792804132443 |
| [51] | Voiculescu, D.: Aspects of free probability. In: XIVth International Congress on Mathematical Physics, pp. 145-157. World Sci. Publ., Hackensack, NJ (2005) |
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.
