Constrained trace-optimization of polynomials in freely noncommuting variables

详细信息    查看全文

• 作者：Igor Klep ; Janez Povh
• 关键词：Noncommutative polynomial ; Optimization ; Sum of squares ; Semidefinite programming ; Moment problem ; Hankel matrix ; Flat extension ; Matlab toolbox ; Real algebraic geometry ; Free positivity ; Primary 90C22 ; 14P10 ; Secondary 13J30 ; 47A57
• 刊名：Journal of Global Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：64
• 期：2
• 页码：325-348
• 全文大小：598 KB
• 参考文献：1.Anjos, M.F., Lasserre, J.B.: Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, volume 166 of International Series in Operational Research and Management Science. Springer, Berlin (2012)CrossRef
  2.Barvinok, A.: A Course in Convexity, Volume 54 of Graduate Studies in Mathematics. American Mathematical Society, Providence (2002)
  3.Burgdorf, S., Cafuta, K., Klep, I., Povh, J.: The tracial moment problem and trace-optimization of polynomials. Math. Program. 137(1–2), 557–578 (2013)CrossRef MathSciNet
  4.Brešar, M., Klep, I.: Noncommutative polynomials, Lie skew-ideals and tracial Nullstellensätze. Math. Res. Lett. 16(4), 605–626 (2009)CrossRef MathSciNet
  5.Burgdorf, S., Klep, I.: The truncated tracial moment problem. J. Oper. Theory 68, 141–163 (2012)MathSciNet
  6.Brändén, P.: Obstructions to determinantal representability. Adv. Math. 226(2), 1202–1212 (2011)CrossRef MathSciNet
  7.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)MathSciNet
  8.Curto, R.E., Fialkow, L.A.: Flat extensions of positive moment matrices: recursively generated relations. Mem. Am. Math. Soc. 136(648), x+56 (1998)MathSciNet
  9.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)CrossRef MathSciNet
  10.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). Available from http://​ncsostools.​fis.​unm.​si/​
  11.Cafuta, K., Klep, I., Povh, J.: Constrained polynomial optimization problems with noncommuting variables. SIAM J. Optim. 22(2), 363–383 (2012)CrossRef MathSciNet
  12.Connes, A.: Classification of injective factors. Cases \(II_{1}, II_{\infty }, III_{\lambda }, \lambda \ne 1\) . Ann. Math. (2) 104(1), 73–115 (1976)CrossRef MathSciNet
  13.de Klerk, E.: Aspects of Semidefinite Programming, Volume 65 of Applied Optimization. Kluwer, Dordrecht (2002)CrossRef
  14.Helton, J.W., Klep, I., McCullough, S.: The convex Positivstellensatz in a free algebra. Adv. Math. 231(1), 516–534 (2012)CrossRef MathSciNet
  15.Henrion, D., Lasserre, J.B., Löfberg, J.: GloptiPoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw., 24(4–5), 761–779 (2009). Available from http://​www.​laas.​fr/​henrion/​software/​gloptipoly3/​
  16.Helton, J.W., McCullough, S.: A Positivstellensatz for non-commutative polynomials. Trans. Am. Math. Soc. 356(9), 3721–3737 (2004)CrossRef MathSciNet
  17.Helton, J.W., McCullough, S.: Every convex free basic semi-algebraic set has an LMI representation. Ann. Math. (2) 176(2), 979–1013 (2012)CrossRef MathSciNet
  18.Helton, J.W., McCullough, S., de Oliveira, M.C., Putinar, M.: Engineering systems and free semi-algebraic geometry. In: Emerging Applications of Algebraic Geometry, Volume 149 of IMA Vol. Math. Appl., pp. 17–62. Springer, (2008)
  19.Klep, I., Schweighofer, M.: Connes’ embedding conjecture and sums of Hermitian squares. Adv. Math. 217(4), 1816–1837 (2008)CrossRef MathSciNet
  20.Kaliuzhnyi-Verbovetskyi, D.S., Vinnikov, V.: Foundations of free noncommutative function theory, volume 199. American Mathematical Society, (2014)
  21.Lasserre, J.B.: Global optimization with polynomials and the problem of moments. J. Optim. 11(3), 796–817 (2000/2001)
  22.Lasserre, J.B.: Moments, Positive Polynomials and Their Applications, vol. 1. Imperial College Press, London (2009)CrossRef
  23.Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry, pp. 157–270. Springer, (2009)
  24.Löfberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference, Taipei, Taiwan, 2004. Available from http://​control.​ee.​ethz.​ch/​joloef/​wiki/​pmwiki.​php
  25.Mittelmann, D.: An independent benchmarking of SDP and SOCP solvers. Math. Program. B, 95, 407–430 (2003). http://​plato.​asu.​edu/​bench.​html
  26.Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20(1), 336–356 (2009)CrossRef MathSciNet
  27.Nie, J.: The \({\cal A}\) -truncated \({\cal K}\) -moment problem. Found. Comput. Math. 14(6), 1243–1276 (2014)CrossRef MathSciNet
  28.Netzer, T., Thom, A.: Hyperbolic polynomials and generalized Clifford algebras. Disc. Comput. Geom. 51, 802–814 (2014)CrossRef MathSciNet
  29.Pironio, S., Navascués, M., Acín, A.: Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM J. Optim. 20(5), 2157–2180 (2010)CrossRef MathSciNet
  30.Prajna, S., Papachristodoulou, A., Seiler, P., Parrilo, P.A.: SOSTOOLS and its control applications. In: Positive polynomials in control, Volume 312 of Lecture Notes in Control and Inform. Sci., pp. 273–292. Springer, Berlin, (2005)
  31.Procesi, C.: The invariant theory of \(n\times n\) matrices. Adv. Math. 19(3), 306–381 (1976)CrossRef MathSciNet
  32.Procesi, C., Schacher, M.: A non-commutative real nullstellensatz and hilbert’s 17th problem. Ann. Math. 104(3), 395–406 (1976)CrossRef MathSciNet
  33.Powers, V., Scheiderer, C.: The moment problem for non-compact semialgebraic sets. Adv. Geom. 1(1), 71–88 (2001)CrossRef MathSciNet
  34.Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3), 969–984 (1993)CrossRef MathSciNet
  35.Rowen, L.H.: Polynomial Identities in Ring Theory Volume 84 of Pure and Applied Mathematics, vol. 84. Academic Press Inc., New York (1980)
  36.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). Available from http://​sedumi.​ie.​lehigh.​edu/​
  37.Takesaki, M.: Theory of Operator Algebras. III. Springer, Berlin (2003)CrossRef
  38.Toh, K.C., Todd, M.J., Tütüncü, R.H.: SDPT3—a MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Softw., 11/12(1–4), 545–581 (1999). Available from http://​www.​math.​nus.​edu.​sg/​mattohkc/​sdpt3.​html
  39.Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49–95 (1996)CrossRef MathSciNet
  40.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. Software, 35(2), Art. 15, 13 (2009)
  41.Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming. Kluwer, Dordrecht (2000)CrossRef
  42.Xu, S., Lam, J.: A survey of linear matrix inequality techniques in stability analysis of delay systems. Int. J. Syst. Sci. 39(12), 1095–1113 (2008)CrossRef MathSciNet
  43.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). Available from http://​sdpa.​sourceforge.​net/​
  
• 作者单位：Igor Klep (1)
  Janez Povh (2)
  
  1. Department of Mathematics, The University of Auckland, Auckland, New Zealand
  2. Faculty of information studies in Novo mesto, Novo mesto, Slovenia
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Computer Science, general
  Real Functions
  Optimization
  
• 出版者：Springer Netherlands
• ISSN：1573-2916

文摘

The study of matrix inequalities in a dimension-free setting is in the realm of free real algebraic geometry. In this paper we investigate constrained trace and eigenvalue optimization of noncommutative polynomials. We present Lasserre’s relaxation scheme for trace optimization based on semidefinite programming (SDP) and demonstrate its convergence properties. Finite convergence of this relaxation scheme is governed by flatness, i.e., a rank-preserving property for associated dual SDPs. If flatness is observed, then optimizers can be extracted using the Gelfand–Naimark–Segal construction and the Artin–Wedderburn theory verifying exactness of the relaxation. To enforce flatness we employ a noncommutative version of the randomization technique championed by Nie. The implementation of these procedures in our computer algebra system NCSOStoolsis presented and several examples are given to illustrate our results. Keywords Noncommutative polynomial Optimization Sum of squares Semidefinite programming Moment problem Hankel matrix Flat extension Matlab toolbox Real algebraic geometry Free positivity