Abstract
The main topic addressed in this paper is trace-optimization of polynomials in noncommuting (nc) variables: given an nc polynomial f, what is the smallest trace \({f(\underline {A})}\) can attain for a tuple of matrices \({\underline {A}}\)? A relaxation using semidefinite programming (SDP) based on sums of hermitian squares and commutators is proposed. While this relaxation is not always exact, it gives effectively computable bounds on the optima. To test for exactness, the solution of the dual SDP is investigated. If it satisfies a certain condition called flatness, then the relaxation is exact. In this case it is shown how to extract global trace-optimizers with a procedure based on two ingredients. The first is the solution to the truncated tracial moment problem, and the other crucial component is the numerical implementation of the Artin-Wedderburn theorem for matrix *-algebras due to Murota, Kanno, Kojima, Kojima, and Maehara. Trace-optimization of nc polynomials is a nontrivial extension of polynomial optimization in commuting variables on one side and eigenvalue optimization of nc polynomials on the other side—two topics with many applications, the most prominent being to linear systems engineering and quantum physics. The optimization problems discussed here facilitate new possibilities for applications, e.g. in operator algebras and statistical physics.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Akhiezer, N.I.: The classical moment problem and some related questions in analysis. Translated by N. Kemmer. Hafner Publishing Co., New York (1965)
Burgdorf, S., Klep, I.: The truncated tracial moment problem. J. Oper. Theory (to appear). http://arxiv.org/abs/1001.3679
Bessis D., Moussa P., Villani M.: Monotonic converging variational approximations to the functional integrals in quantum statistical mechanics. J. Math. Phys. 16(11), 2318–2325 (1975)
Bayer C., Teichmann J.: The proof of Tchakaloff’s theorem. Proc. Am. Math. Soc. 134(10), 3035–3040 (2006)
Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization. MPS/SIAM Series on Optimization. SIAM, Philadelphia, PA (2001)
Curto, R.E., Fialkow, L.A.: Solution of the truncated complex moment problem for flat data. Mem. Am. Math. Soc. 119(568), x+52 (1996)
Cimprič J.: A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming. J. Math. Anal. Appl. 369(2), 443–452 (2010)
Cafuta, K., Klep, I., Povh, J.: NCSOStools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials. Optim. Methods Softw. 26(3), 363–380 (2011). http://ncsostools.fis.unm.si
Choi, M.D., Lam, T.Y., Reznick, B.: Sums of squares of real polynomials. In: K-Theory and Algebraic Geometry: Connections with Quadratic Forms and Division Algebras. Proceedings of Symposia in Pure Mathematics, vol. 58, pp. 103–126. AMS, Providence, RI (1995)
Connes A.: Classification of injective factors. Cases II1, II∞, IIIλ, λ ≠ 1. Ann. Math. 104(2), 73–115 (1976)
de Oliveira, M.C., Helton, J.W., McCullough, S., Putinar, M.: Engineering systems and free semi-algebraic geometry. In: Emerging Applications of Algebraic Geometry. IMA Volumes in Mathematics and its Applications, vol. 149, pp. 17–62. Springer (2008)
Doherty, A.C., Liang, Y.-C., Toner, B., Wehner, S.: The quantum moment problem and bounds on entangled multi-prover games. In: Twenty-Third Annual IEEE Conference on Computational Complexity, pp. 199–210. IEEE Computer Society, Los Alamitos, CA (2008)
Eberly W., Giesbrecht M.: Efficient decomposition of separable algebras. J. Symb. Comput. 37, 35–81 (2004)
Friedl K., Rónyai L.: Polynomial time solutions of some problems in computational algebra. Symp. Theory Comput. Am. Math. Soc. 17, 153–162 (1985)
Glauber R.J.: The quantum theory of optical coherence. Phys. Rev. 130(6), 2529–2539 (1963)
Helton, J.W., de Oliveira, M., Miller, R.L., Stankus, M.: NCAlgebra: a mathematica package for doing non commuting algebra. http://www.math.ucsd.edu/~ncalg/
Helton J.W.: “Positive” noncommutative polynomials are sums of squares. Ann. Math. (2) 156(2), 675–694 (2002)
Henrion, D., Lasserre, J.-B.: Detecting global optimality and extracting solutions in GloptiPoly. In: Positive Polynomials In Control. Lecture Notes in Control and Information Sciences, vol. 312, pp. 293–310. Springer, Berlin (2005)
Henrion, D., Lasserre, J.-B., Löfberg, J.: GloptiPoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24(4–5), 761–779 (2009). http://www.laas.fr/~henrion/software/gloptipoly3/
Klep I., Povh J.: Semidefinite programming and sums of hermitian squares of noncommutative polynomials. J. Pure Appl. Algebra 214, 740–749 (2010)
Klep I., Schweighofer M.: Connes’ embedding conjecture and sums of Hermitian squares. Adv. Math. 217(4), 1816–1837 (2008)
Klep I., Schweighofer M.: Sums of Hermitian squares and the BMV conjecture. J. Stat. Phys. 133(4), 739–760 (2008)
Lam T.Y.: A First Course In Noncommutative Rings. Graduate Texts in Mathematics, vol. 131. Springer, New York (1991)
Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (2000/01)
Lasserre J.B.: Moments, Positive Polynomials and Their Applications, vol. 1. Imperial College Press, London (2009)
Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications Of Algebraic Geometry. IMA Volumes in Mathematics and its Applications, vol. 149, pp. 157–270. Springer, New York (2009)
Löfberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004). http://users.isy.liu.se/johanl/yalmip/
Mazziotti, D.A.: Realization of quantum chemistry without wave functions through first-order semidefinite programming. Phys. Rev. Lett. 93(21), 213001, 4 (2004)
McCullough S.: Factorization of operator-valued polynomials in several non-commuting variables. Linear Algebra Appl. 326(1–3), 193–203 (2001)
Mittelmann, D.: An independent benchmarking of SDP and SOCP solvers. Math. Program. 95(2, Ser. B), 407–430 (2003). http://plato.asu.edu/sub/pns.html
Murota K., Kanno Y., Kojima M., Kojima S.: A numerical algorithm for block-diagonal decomposition of matrix *-algebras with application to semidefinite programming. Jpn. J. Ind. Appl. Math. 27(1), 125–160 (2010)
Maehara T., Murota K.: A numerical algorithm for block-diagonal decomposition of matrix *-algebras with general irreducible components. Jpn. J. Ind. Appl. Math. 27(2), 263–293 (2010)
Malick J., Povh J., Rendl F., Wiegele A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20(1), 336–356 (2009)
Nesterov Y., Nemirovskii A.: Interior-point Polynomial Algorithms In Convex Programming. SIAM Studies in Applied Mathematics, vol. 13. SIAM, Philadelphia (1994)
Parrilo P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2, Ser. B), 293–320 (2003)
Pironio S., Navascues M., Acin A.: Convergent relaxations of polynomial optimization problems with non-commuting variables. SIAM J. Optim. 20(5), 2157–2180 (2010)
Prajna, S., Papachristodoulou, A., Seiler, P., Parrilo, P.A.: SOSTOOLS and its control applications. In: Positive Polynomials in Control. Lecture Notes in Control and Information Sciences, vol. 312, pp. 273–292. Springer, Berlin (2005). http://www.cds.caltech.edu/sostools/
Parrilo, P.A., Sturmfels, B.: Minimizing polynomial functions. In: Algorithmic and Quantitative Real Algebraic Geometry (Piscataway, NJ, 2001). DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 60, pp. 83–99. American Mathematical Society, Providence, RI (2003)
Pál, K.F., Vértesi, T.: Quantum bounds on Bell inequalities. Phys. Rev. A (3) 79(2), 022120, 12 (2009)
Ramana M.V.: An exact duality theory for semidefinite programming and its complexity implications. Math. Program. Ser. B 77(2), 129–162 (1997)
Stochel J.: Solving the truncated moment problem solves the full moment problem. Glasg. Math. J. 43(3), 335–341 (2001)
Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12(1–4), 625–653 (1999). http://sedumi.ie.lehigh.edu/
Toh, K.-C., Todd, M.J., Tütüncü, R.-H.: SDPT3 a Matlab software package for semidenite programming. Optim. Methods Softw. 11, 545–581 (1999). http://www.math.nus.edu.sg/~mattohkc/sdpt3.html
Waki, H., Kim, S., Kojima, M., Muramatsu, M., Sugimoto, H.: Algorithm 883: sparsePOP—a sparse semidefinite programming relaxation of polynomial optimization problems. ACM Trans. Math. Softw. 35(2), Art. 15, 13 (2009)
Wolkowicz H., Saigal R., Vandenberghe L.: Handbook of Semidefinite Programming. Kluwer, Dordrecht (2000)
Yamashita M., Fujisawa, K., Kojima, M.: Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0). Optim. Methods Softw. 18(4), 491–505 (2003). http://sdpa.sourceforge.net/
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Burgdorf, S., Cafuta, K., Klep, I. et al. The tracial moment problem and trace-optimization of polynomials. Math. Program. 137, 557–578 (2013). https://doi.org/10.1007/s10107-011-0505-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-011-0505-8
Keywords
- Sum of squares
- Noncommutative polynomial
- Semidefinite programming
- Tracial moment problem
- Flat extension
- Free positivity
- Real algebraic geometry