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.


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
Full Text: DOI


[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
[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
[4] Burgdorf, S.; Cafuta, K.; Klep, I.; Povh, J., Algorithmic aspects of sums of hermitian squares of noncommutative polynomials, Comput Optim Appl, 55, 137-153, (2013) · Zbl 1273.90144
[5] Burgdorf, S.; Cafuta, K.; Klep, I.; Povh, J., The tracial moment problem and trace-optimization of polynomials, Math Program, 137, 557-578, (2013) · Zbl 1274.90256
[6] Burgdorf S, Klep I, Povh J (2016) Optimization of polynomials in non-commuting variables. Springer briefs in mathematics. Springer, Berlin
[7] Cafuta, K., On matrix algebras associated to sum-of-squares semidefinite programs, Linear Multilinear Algebra, 61, 1496-1509, (2013) · Zbl 1284.13033
[8] Cafuta, K.; Klep, I.; Povh, J., A note on the nonexistence of sum of squares certificates for the Bessis-Moussa-Villani conjecture, J Math Phys, 51, 083,521, 10, (2010) · Zbl 1312.81139
[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., Constrained polynomial optimization problems with noncommuting variables, SIAM J Optim, 22, 363-383, (2012) · Zbl 1263.90052
[11] Cafuta, K.; Klep, I.; Povh, J., Rational sums of hermitian squares of free noncommutative polynomials, Ars Math Contemp, 9, 243-259, (2015) · Zbl 1386.16026
[12] Choi M, Lam T, Reznick B (1995) Sums of squares of real polynomials. In: Proceedings of symposia in pure mathematics, \(K\)-theory and algebraic geometry: connections with quadratic forms and division algebras, vol 58. AMS, Providence, pp 103-126
[13] Cimprič, J., A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming, J Math Anal Appl, 369, 443-452, (2010) · Zbl 1205.90215
[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
[15] Gatermann, K.; Parrilo, P., Symmetry groups, semidefinite programs, and sums of squares, J Pure Appl Algebra, 192, 95-128, (2004) · Zbl 1108.13021
[16] Goemans, MX, Semidefinite programming in combinatorial optimization, Math Program, 79, 143-161, (1997) · Zbl 0887.90139
[17] Halická, M.; Klerk, E.; Roos, C., On the convergence of the central path in semidefinite optimization, SIAM J Optim, 12, 1090-1099, (2002) · Zbl 1035.90100
[18] Helton, J., “Positive” noncommutative polynomials are sums of squares, Ann of Math, 156, 675-694, (2002) · Zbl 1033.12001
[19] Helton, J.; Nie, J., A semidefinite approach for truncated K-moment problems, Found Comput Math, 12, 851-881, (2012) · Zbl 1259.44005
[20] Horn R, Johnson C (1985) Matrix analysis. Cambridge University Press, Cambridge · Zbl 0576.15001
[21] Klep, I.; Povh, J., Semidefinite programming and sums of hermitian squares of noncommutative polynomials, J Pure Appl Algebra, 214, 740-749, (2010) · Zbl 1246.11092
[22] Klep, I.; Povh, J., Constrained trace-optimization of polynomials in freely noncommuting variables, J Global Optim, 64, 325-348, (2016) · Zbl 1356.90103
[23] Klep, I.; Schweighofer, M., Connes’ embedding conjecture and sums of Hermitian squares, Adv Math, 217, 1816-1837, (2008) · Zbl 1184.46055
[24] Klep, I.; Schweighofer, M., Sums of Hermitian squares and the BMV conjecture, J Stat Phys, 133, 739-760, (2008) · Zbl 1158.15018
[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
[28] Marshall M (2008) Positive polynomials and sums of squares, mathematical surveys and monographs, vol 146. American Mathematical Society, Providence
[29] McCullough, S., Factorization of operator-valued polynomials in several non-commuting variables, Linear Algebra Appl, 326, 193-203, (2001) · Zbl 0980.47024
[30] McCullough, S.; Putinar, M., Noncommutative sums of squares, Pac J Math, 218, 167-171, (2005) · Zbl 1177.47020
[31] Mittelman H http://plato.asu.edu/sub/pns.html
[32] Nie, J., Sum of squares method for sensor network localization, Comput Optim Appl, 43, 151-179, (2009) · Zbl 1170.90510
[33] Nie, J., Optimality conditions and finite convergence of Lasserre’s hierarchy, Math Program, 146, 97-121, (2014) · Zbl 1300.65041
[34] Parrilo P (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD. thesis, California Institute of Technology
[35] Parrilo, P., Semidefinite programming relaxations for semialgebraic problems, Math Program, 96, 293-320, (2003) · Zbl 1043.14018
[36] Pironio, S.; Navascués, M.; Acín, A., Convergent relaxations of polynomial optimization problems with noncommuting variables, SIAM J Optim, 20, 2157-2180, (2010) · Zbl 1228.90073
[37] Powers, V.; Wörmann, T., An algorithm for sums of squares of real polynomials, J Pure Appl Algebra, 127, 99-104, (1998) · Zbl 0936.11023
[38] Recht, B.; Fazel, M.; Parrilo, P., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev, 52, 471-501, (2010) · Zbl 1198.90321
[39] Reznick, B., Extremal PSD forms with few terms, Duke Math J, 45, 363-374, (1978) · Zbl 0395.10037
[40] Shor, NZ, Dual quadratic estimates in polynomial and boolean programming, Ann Oper Res, 25, 163-168, (1991)
[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/
[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
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.