Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools. (English) Zbl 07061310
Summary: Numerous applied problems contain matrices as variables, and the formulas therefore involve polynomials in matrices. To handle such polynomials it is necessary study non-commutative polynomials. In this paper we will present an algorithm and its implementation in the free Matlab package NCSOStools using semidefinite programming to check whether a given non-commutative polynomial in non-symmetric variables can be written as a sum of Hermitian squares.
MSC:
| 90Bxx | Operations research and management science |
| 13J30 | Real algebra |
| 90C22 | Semidefinite programming |
| 08B20 | Free algebras |
| 11E25 | Sums of squares and representations by other particular quadratic forms |
| 90C90 | Applications of mathematical programming |
Keywords:
noncommutative polynomial; sum of Hermitian squares; semidefinite programming; Matlab toolbox; NCSOStoolsReferences:
| [1] | Anjos M, Lasserre J (2012) Handbook of semidefinite, conic and polynomial optimization: theory, algorithms, software and applications, vol 166. International series in operational research and management science. Springer, New York · Zbl 1235.90002 · doi:10.1007/978-1-4614-0769-0 |
| [2] | Bachoc C, Gijswijt DC, Schrijver A, Vallentin F (2012) Invariant semidefinite programs. In: Handbook on semidefinite, conic and polynomial optimization, international series in operations research & management science, vol 166. Springer, New York, pp 219-269 · Zbl 1334.90097 |
| [3] | Boyd S, Ghaoui LE, Feron E, Balakrishnan V (1994) Linear matrix inequalities in system and control theory. Studies in applied mathematics. SIAM, Philadelphia · Zbl 0816.93004 · doi:10.1137/1.9781611970777 |
| [4] | Burgdorf S, Cafuta K, Klep I, Povh J (2013a) Algorithmic aspects of sums of hermitian squares of noncommutative polynomials. Comput Optim Appl 55(1):137-153 · Zbl 1273.90144 · doi:10.1007/s10589-012-9513-8 |
| [5] | Burgdorf S, Cafuta K, Klep I, Povh J (2013b) The tracial moment problem and trace-optimization of polynomials. Math Program 137(1):557-578 · Zbl 1274.90256 · doi:10.1007/s10107-011-0505-8 |
| [6] | Burgdorf S, Klep I, Povh J (2016) Optimization of polynomials in non-commuting variables. Springer briefs in mathematics. Springer, Berlin · Zbl 1388.90001 |
| [7] | Cafuta K (2013) On matrix algebras associated to sum-of-squares semidefinite programs. Linear Multilinear Algebra 61(11):1496-1509 · Zbl 1284.13033 · doi:10.1080/03081087.2012.758261 |
| [8] | Cafuta K, Klep I, Povh J (2010) A note on the nonexistence of sum of squares certificates for the Bessis-Moussa-Villani conjecture. J Math Phys 51(8):083,521, 10 · Zbl 1312.81139 · doi:10.1063/1.3462915 |
| [9] | Cafuta K, Klep I, Povh J (2011) NCSOStools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials. Optim Methods Softw 26(3):363-380. http://ncsostools.fis.unm.si/ · Zbl 1226.90063 |
| [10] | Cafuta K, Klep I, Povh J (2012) Constrained polynomial optimization problems with noncommuting variables. SIAM J Optim 22(2):363-383 · Zbl 1263.90052 · doi:10.1137/110830733 |
| [11] | Cafuta K, Klep I, Povh J (2015) Rational sums of hermitian squares of free noncommutative polynomials. Ars Math Contemp 9(2):243-259 · Zbl 1386.16026 · doi:10.26493/1855-3974.518.768 |
| [12] | Choi M, Lam T, Reznick B (1995) Sums of squares of real polynomials. In: Proceedings of symposia in pure mathematics, \[KK\]-theory and algebraic geometry: connections with quadratic forms and division algebras, vol 58. AMS, Providence, pp 103-126 · Zbl 0821.11028 |
| [13] | Cimprič J (2010) A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming. J Math Anal Appl 369(2):443-452 · Zbl 1205.90215 · doi:10.1016/j.jmaa.2010.03.045 |
| [14] | de Oliveira M, Helton J, McCullough S, Putinar M (2008) Engineering systems and free semi-algebraic geometry. In: Emerging applications of algebraic geometry, IMA voume of mathematics and its application, vol 149. Springer, New York, pp 17-61 · Zbl 1156.14331 |
| [15] | Gatermann K, Parrilo P (2004) Symmetry groups, semidefinite programs, and sums of squares. J Pure Appl Algebra 192(1-3):95-128 · Zbl 1108.13021 · doi:10.1016/j.jpaa.2003.12.011 |
| [16] | Goemans MX (1997) Semidefinite programming in combinatorial optimization. Math Program 79(1-3, Ser. B):143-161 · Zbl 0887.90139 |
| [17] | Halická M, de Klerk E, Roos C (2002) On the convergence of the central path in semidefinite optimization. SIAM J Optim 12(4):1090-1099 · Zbl 1035.90100 · doi:10.1137/S1052623401390793 |
| [18] | Helton J (2002) “Positive” noncommutative polynomials are sums of squares. Ann of Math 156(2):675-694 · Zbl 1033.12001 · doi:10.2307/3597203 |
| [19] | Helton J, Nie J (2012) A semidefinite approach for truncated K-moment problems. Found Comput Math 12(6):851-881 · Zbl 1259.44005 · doi:10.1007/s10208-012-9132-x |
| [20] | Horn R, Johnson C (1985) Matrix analysis. Cambridge University Press, Cambridge · Zbl 0576.15001 · doi:10.1017/CBO9780511810817 |
| [21] | Klep I, Povh J (2010) Semidefinite programming and sums of hermitian squares of noncommutative polynomials. J Pure Appl Algebra 214:740-749 · Zbl 1246.11092 · doi:10.1016/j.jpaa.2009.07.003 |
| [22] | Klep I, Povh J (2016) Constrained trace-optimization of polynomials in freely noncommuting variables. J Global Optim 64(2):325-348 · Zbl 1356.90103 · doi:10.1007/s10898-015-0308-1 |
| [23] | Klep I, Schweighofer M (2008a) Connes’ embedding conjecture and sums of Hermitian squares. Adv Math 217(4):1816-1837 · Zbl 1184.46055 · doi:10.1016/j.aim.2007.09.016 |
| [24] | Klep I, Schweighofer M (2008b) Sums of Hermitian squares and the BMV conjecture. J Stat Phys 133(4):739-760 · Zbl 1158.15018 · doi:10.1007/s10955-008-9632-x |
| [25] | Lasserre J (2000/2001) Global optimization with polynomials and the problem of moments. SIAM J Optim 11(3):796-817 · Zbl 1010.90061 |
| [26] | Lasserre J (2009) Moments, positive polynomials and their applications, vol 1. Imperial college press optimization series. Imperial College Press, London |
| [27] | Laurent M (2009) Sums of squares, moment matrices and optimization over polynomials. In: Emerging applications of algebraic geometry, IMA volumes in mathematics and its application, vol 149. Springer, New York, pp 157-270 · Zbl 1163.13021 |
| [28] | Marshall M (2008) Positive polynomials and sums of squares, mathematical surveys and monographs, vol 146. American Mathematical Society, Providence · Zbl 1169.13001 · doi:10.1090/surv/146 |
| [29] | McCullough S (2001) Factorization of operator-valued polynomials in several non-commuting variables. Linear Algebra Appl 326(1-3):193-203 · Zbl 0980.47024 · doi:10.1016/S0024-3795(00)00285-8 |
| [30] | McCullough S, Putinar M (2005) Noncommutative sums of squares. Pac J Math 218(1):167-171 · Zbl 1177.47020 · doi:10.2140/pjm.2005.218.167 |
| [31] | Mittelman H http://plato.asu.edu/sub/pns.html |
| [32] | Nie J (2009) Sum of squares method for sensor network localization. Comput Optim Appl 43(2):151-179 · Zbl 1170.90510 · doi:10.1007/s10589-007-9131-z |
| [33] | Nie J (2014) Optimality conditions and finite convergence of Lasserre’s hierarchy. Math Program 146(1-2):97-121 · Zbl 1300.65041 · doi:10.1007/s10107-013-0680-x |
| [34] | Parrilo P (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD. thesis, California Institute of Technology |
| [35] | Parrilo P (2003) Semidefinite programming relaxations for semialgebraic problems. Math Program 96(2, Ser. B):293-320 · Zbl 1043.14018 · doi:10.1007/s10107-003-0387-5 |
| [36] | Pironio S, Navascués M, Acín A (2010) Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM J Optim 20(5):2157-2180 · Zbl 1228.90073 · doi:10.1137/090760155 |
| [37] | Powers V, Wörmann T (1998) An algorithm for sums of squares of real polynomials. J Pure Appl Algebra 127(1):99-104 · Zbl 0936.11023 · doi:10.1016/S0022-4049(97)83827-3 |
| [38] | Recht B, Fazel M, Parrilo P (2010) Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev 52(3):471-501 · Zbl 1198.90321 · doi:10.1137/070697835 |
| [39] | Reznick B (1978) Extremal PSD forms with few terms. Duke Math J 45(2):363-374 · Zbl 0395.10037 · doi:10.1215/S0012-7094-78-04519-2 |
| [40] | Shor NZ (1991) Dual quadratic estimates in polynomial and boolean programming. Ann Oper Res 25(1-4):163-168 · Zbl 0783.90081 |
| [41] | Sturm J (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim Methods Softw 11/12(1-4):625-653. http://sedumi.ie.lehigh.edu/ · Zbl 0973.90526 |
| [42] | Toh K, Todd M, Tütüncü R (2012) On the implementation and usage of SDPT3—a Matlab software package for semidefinite-quadratic-linear programming, version 4.0. In: Handbook on semidefinite, conic and polynomial optimization, international series in operations research & management science, vol 166. Springer, New York, pp 715-754. http://www.math.nus.edu.sg/ mattohkc/sdpt3.html · Zbl 1334.90117 |
| [43] | Wolkowicz H, Saigal R, Vandenberghe L (2000) Handbook of semidefinite programming. Kluwer, Dordrecht · Zbl 0962.90001 · doi:10.1007/978-1-4615-4381-7 |
| [44] | Yamashita M, Fujisawa K, Kojima M (2003) Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0). Optim Methods Softw 18(4):491-505. http://sdpa.sourceforge.net/ · Zbl 1106.90366 |
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.
