Article Contents
Article Contents

Dehomogenization for completely positive tensors

• Suhan Zhong

Jiawang Nie and Suhan Zhong are partially supported by NSF grant DMS-2110780

• A real symmetric tensor is completely positive (CP) if it is a sum of symmetric tensor powers of nonnegative vectors. We propose a dehomogenization approach for studying CP tensors. This gives new Moment-SOS relaxations for CP tensors. Detection for CP tensors and the linear conic optimization with CP tensor cones can be solved more efficiently by the dehomogenization approach.

Mathematics Subject Classification: Primary: 90C23, 15A69, 44A60, 90C22.

 Citation:

• Table 1.  Comparison of some dimensions

 (n, k) $\binom{n+2k}{2k}$ $\binom{n-1+2k}{2k}$ $\binom{n+k}{k}$ $\binom{n-1+k}{k}$ (2, 2) 15 5 6 3 (2, 3) 28 7 10 4 (2, 4) 45 9 15 5 (3, 2) 35 15 10 6 (3, 3) 84 28 20 10 (3, 4) 165 45 35 15 (4, 2) 70 35 15 10 (4, 3) 210 84 35 20 (4, 4) 495 165 70 35 (5, 2) 126 70 21 15 (5, 3) 462 210 56 35 (5, 4) 1287 495 126 70

Table 2.  Comparison between relaxations (28) and (34)

 With Dehomogenization Relaxation (28) No Dehomogenization Relaxation (34) Example time accuracy order time accuracy order 5.1(A) 1.03 $1.38\cdot 10^{-6}$ 3 2.77 $1.71\cdot 10^{-6}$ 3 5.1(B) 0.52 $1.97\cdot 10^{-6}$ 2 0.39 $2.05\cdot 10^{-6}$ 2 5.1(C) 0.11 not CP 2 0.14 not CP 2 5.2 (ⅰ) 0.22 not CP 4 0.58 not CP 4 5.2(ⅱ) 0.49 $4.13\cdot 10^{-6}$ 3 1.05 $1.54\cdot 10^{-6}$ 3 5.3 (ⅰ) 2.22 $4.96\cdot 10^{-6}$ 3 2.44 $5.51\cdot 10^{-6}$ 3 5.3(ⅱ) 1.48 $9.17\cdot 10^{-8}$ 3 2.14 $2.10\cdot 10^{-5}$ 4 5.4 3.77 $1.06\cdot 10^{-9}$ 6 36.69 $5.54\cdot 10^{-6}$ 6
•  [1] A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific, 2003. doi: 10.1142/9789812795212. [2] I. M. Bomze, Copositive optimization–Recent developments and applications, European J. Oper. Res., 216 (2012), 509-520.  doi: 10.1016/j.ejor.2011.04.026. [3] A. Cichocki, R. Zdunek, A. H. Phan and S. Amari, Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multiway Data Analysis and Blind Source Separation, Wiley, New York, 2009. [4] P. Comon, G. Golub, L.-H. Lim and B. Mourrain, Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl., 30 (2008), 1254-1279.  doi: 10.1137/060661569. [5] E. De. Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12 (2002), 875-892.  doi: 10.1137/S1052623401383248. [6] P. J. Dickinson and L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, Comput. Optim. Appl., 57 (2014), 403-415.  doi: 10.1007/s10589-013-9594-z. [7] M. Dür, Copositive programming–A survey, in Recent Advances in Optimization and Its Applications in Engineering (eds. M. Diehl, F. Glineur, E. Jarlebring, and W. Michiels), Springer, Berlin, 2010, 3-20. [8] J. Fan, J. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Mathematical Programming, 170 (2018), 507-539.  doi: 10.1007/s10107-017-1167-y. [9] J. Fan, J. Nie and A. Zhou, Completely positive binary tensors, Math. Oper. Res., 44 (2019), 1087-1100.  doi: 10.1287/moor.2018.0963. [10] J. Fan and A. Zhou, The CP-matrix approximation problem, SIAM J. Matrix Anal. Appl., 37 (2016), 171-194.  doi: 10.1137/15M1012086. [11] J. Fan and A. Zhou, A semidefinite algorithm for completely positive tensor decomposition, Comput. Optim. Appl., 66 (2017), 267-283.  doi: 10.1007/s10589-016-9870-9. [12] M. Hall and M. Newman, Copositive and completely positive quadratic forms, Proceedings of the Cambridge Philosophical Society, 59 (1963), 32933. [13] D. Henrion and J. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, Positive Polynomials in Control, Springer, Berlin, Heidelberg, (2005), 293-310. doi: 10.1007/10997703_15. [14] D. Henrion, J. Lasserre and J. Löfberg, Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24 (2009), 761-779.  doi: 10.1080/10556780802699201. [15] D. Henrion, M. Korda and J. Lasserre, The Moment-SOS Hierarchy, World Scientific, Singapore, 2020. [16] C. Hillar and J. Nie, An elementary and constructive solution to Hilbert's 17th problem for matrices, Proc. Amer. Math. Soc., 136 (2008), 73-76.  doi: 10.1090/S0002-9939-07-09068-5. [17] J. Landsberg, Tensors: Geometry and Applications, Graduate Studies in Mathematics, 128, AMS, Providence, RI, 2012. doi: 10.1090/gsm/128. [18] J. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2000), 796-817.  doi: 10.1137/S1052623400366802. [19] J. Lasserre,  An Introduction to Polynomial and Semi-algebraic Optimization, Cambridge University Press, 2015.  doi: 10.1017/CBO9781107447226. [20] M. Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Applications, 149, pp. 157–270, Springer, 2009. doi: 10.1007/978-0-387-09686-5_7. [21] L. H. Lim, Tensors and Hypermatrices, in Handbook of Linear Algebra (eds. L. Hogben), 2nd edition, CRC Press, Boca Raton, FL, 2013. [22] Z. Luo and L. Qi, Completely positive tensors: properties, easily checkable subclasses, and tractable relaxations, SIAM J. Matrix Anal. Appl., 37 (2016), 1675-1698.  doi: 10.1137/15M1025220. [23] O. Mason and R. Shorten, On linear copositive Lyapunov functions and the stability of switched positive linear systems, IEEE Trans. Automat. Control, 52 (2007), 1346-1349.  doi: 10.1109/TAC.2007.900857. [24] J. Nie, Polynomial matrix inequality and semidefinite representation, Math. Oper. Res., 36 (2011), 398-415.  doi: 10.1287/moor.1110.0498. [25] J. Nie, Certifying convergence of Lasserre's hierarchy via flat truncation, Math. Program., 142 (2013), 485-510.  doi: 10.1007/s10107-012-0589-9. [26] J. Nie, The $\mathcal{{A}}$-truncated $K$-moment problem, Found. Comput. Math., 14 (2014), 1243-1276.  doi: 10.1007/s10208-014-9225-9. [27] J. Nie, Optimality conditions and finite convergence of Lasserre's hierarchy, Math. Program., 146 (2014), 97-121.  doi: 10.1007/s10107-013-0680-x. [28] J. Nie, Linear optimization with cones of moments and nonnegative polynomials, Math. Program., 153 (2015), 247-274.  doi: 10.1007/s10107-014-0797-6. [29] J. Nie, Tight relaxations for polynomial optimization and Lagrange multiplier expressions, Math. Program., 178 (2019), 1-37.  doi: 10.1007/s10107-018-1276-2. [30] J. Nie and X. Zhang, Real eigenvalues of nonsymmetric tensors, Comput. Optim. Appl., 70 (2018), 1-32.  doi: 10.1007/s10589-017-9973-y. [31] J. Nie, Z. Yang and X. Zhang, A complete semidefinite algorithm for detecting copositive matrices and tensors, SIAM J. Optim., 28 (2018), 2902-2921.  doi: 10.1137/17M115308X. [32] M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42 (1993), 969-984.  doi: 10.1512/iumj.1993.42.42045. [33] L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238.  doi: 10.1016/j.laa.2013.03.015. [34] L. Qi, C. Xu and and Y. Xu, Nonnegative tensor factorization, completely positive tensors, and a hierarchical elimination algorithm, SIAM J. Matrix Anal. Appl., 35 (2014), 1227-1241.  doi: 10.1137/13092232X. [35] A. Shashua and T. Hazan, Non-negative tensor factorization with applications to statistics and computer vision, ACM International Conference Proceeding Series: Proceedings of the 22nd International Conference on Machine Learning, 119 (2005), 792-799. [36] J. Sponsel and M. Dür, Factorization and cutting planes for completely positive matrices by copositive projection, Math. Program., 143 (2014), 211-229.  doi: 10.1007/s10107-012-0601-4. [37] J. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11/12 (1999), 625-653.  doi: 10.1080/10556789908805766. [38] C. Xu, Z. Luo, L. Qi and Z. Chen, $\{0, 1\}$ completely positive tensors and multi-hypergraphs, Linear Algebra Appl., 510 (2016), 110-123.  doi: 10.1016/j.laa.2016.08.016. [39] T. Zhang and G. H. Golub, Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl., 23 (2001), 534-550.  doi: 10.1137/S0895479899352045. [40] A. Zhou and J. Fan, The CP-matrix completion problem, SIAM J. Matrix Anal. Appl., 35 (2014), 127-142.  doi: 10.1137/130919490. [41] A. Zhou and J. Fan, Completely positive tensor recovery with minimal nuclear value, Comput. Optim. Appl., 70 (2018), 419-441.  doi: 10.1007/s10589-018-0003-5.

Tables(2)