A Newton-type algorithm for the tensor eigenvalue complementarity problem and some applications

Zhang, Liping; Chen, Chiyu

doi:10.1090/mcom/3558

A Newton-type algorithm for the tensor eigenvalue complementarity problem and some applications
HTML articles powered by AMS MathViewer

by Liping Zhang and Chiyu Chen HTML | PDF

Math. Comp. 90 (2021), 215-231 Request permission

Abstract:

We focus on establishing an algorithm to solve the tensor eigenvalue complementarity problem (TEiCP), and we have two contributions in this paper. First, a smoothing Newton-type algorithm is proposed for the TEiCP based on the CHKS smoothing function. Its global convergence is established under some mild conditions. Numerical experiments are reported to show that the proposed algorithm is efficient and could detect more solutions than some existing methods. Second, we apply the proposed algorithm to solve the eigenvalue problem of nonnegative tensors. We analyze the relationship between the TEiCP and the H-eigenpair and Z-eigenpair problems of an irreducible nonnegative tensor. We show that the TEiCP with an irreducible nonnegative tensor and unit tensor has a unique solution, which is just the unique positive H-eigenpair of the irreducible nonnegative tensor. We also show that the solution set of the TEiCP with an irreducible nonnegative tensor and identity tensor is nonempty and its solutions are positive. Moreover, we can obtain positive Z-eigenpairs of the irreducible nonnegative tensor from these solutions. Finally, we also apply the proposed algorithm to find the unique positive H-eigenpair and a positive Z-eigenpair of an irreducible nonnegative tensor; the numerical results indicate its efficiency and promising performance.

References

B. W. Bader, T. G. Kolda, et al., Matlab tensor toolbox version 2.6, 2015. http://www. sandia.gov/~tgkolda/TensorToolbox/
Dimitri P. Bertsekas, Constrained optimization and Lagrange multiplier methods, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 690767
K. C. Chang, Kelly Pearson, and Tan Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci. 6 (2008), no. 2, 507–520. MR 2435198, DOI 10.4310/CMS.2008.v6.n2.a12
K. C. Chang, K. J. Pearson, and Tan Zhang, Some variational principles for $Z$-eigenvalues of nonnegative tensors, Linear Algebra Appl. 438 (2013), no. 11, 4166–4182. MR 3034523, DOI 10.1016/j.laa.2013.02.013
Bintong Chen and Patrick T. Harker, A non-interior-point continuation method for linear complementarity problems, SIAM J. Matrix Anal. Appl. 14 (1993), no. 4, 1168–1190. MR 1238931, DOI 10.1137/0614081
Bintong Chen and Patrick T. Harker, Smooth approximations to nonlinear complementarity problems, SIAM J. Optim. 7 (1997), no. 2, 403–420. MR 1443626, DOI 10.1137/S1052623495280615
X. Chen, L. Qi, and D. Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Math. Comp. 67 (1998), no. 222, 519–540. MR 1458218, DOI 10.1090/S0025-5718-98-00932-6
Zhongming Chen and Liqun Qi, A semismooth Newton method for tensor eigenvalue complementarity problem, Comput. Optim. Appl. 65 (2016), no. 1, 109–126. MR 3529137, DOI 10.1007/s10589-016-9838-9
Zhongming Chen, Qingzhi Yang, and Lu Ye, Generalized eigenvalue complementarity problem for tensors, Pac. J. Optim. 13 (2017), no. 3, 527–545. MR 3731871
Francisco Facchinei and Jong-Shi Pang, Finite-dimensional variational inequalities and complementarity problems. Vol. I, Springer Series in Operations Research, Springer-Verlag, New York, 2003. MR 1955648
S. Friedland, S. Gaubert, and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl. 438 (2013), no. 2, 738–749. MR 2996365, DOI 10.1016/j.laa.2011.02.042
Christian Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl. 17 (1996), no. 4, 851–868. MR 1410705, DOI 10.1137/S0895479894273134
Eleftherios Kofidis and Phillip A. Regalia, On the best rank-1 approximation of higher-order supersymmetric tensors, SIAM J. Matrix Anal. Appl. 23 (2001/02), no. 3, 863–884. MR 1896822, DOI 10.1137/S0895479801387413
Tamara G. Kolda and Brett W. Bader, Tensor decompositions and applications, SIAM Rev. 51 (2009), no. 3, 455–500. MR 2535056, DOI 10.1137/07070111X
Tamara G. Kolda and Jackson R. Mayo, Shifted power method for computing tensor eigenpairs, SIAM J. Matrix Anal. Appl. 32 (2011), no. 4, 1095–1124. MR 2854605, DOI 10.1137/100801482
Chen Ling, Hongjin He, and Liqun Qi, On the cone eigenvalue complementarity problem for higher-order tensors, Comput. Optim. Appl. 63 (2016), no. 1, 143–168. MR 3441347, DOI 10.1007/s10589-015-9767-z
Ching-Sung Liu, Chun-Hua Guo, and Wen-Wei Lin, Newton-Noda iteration for finding the Perron pair of a weakly irreducible nonnegative tensor, Numer. Math. 137 (2017), no. 1, 63–90. MR 3679929, DOI 10.1007/s00211-017-0869-7
Michael Ng, Liqun Qi, and Guanglu Zhou, Finding the largest eigenvalue of a nonnegative tensor, SIAM J. Matrix Anal. Appl. 31 (2009), no. 3, 1090–1099. MR 2538668, DOI 10.1137/09074838X
Qin Ni and Liqun Qi, A quadratically convergent algorithm for finding the largest eigenvalue of a nonnegative homogeneous polynomial map, J. Global Optim. 61 (2015), no. 4, 627–641. MR 3324215, DOI 10.1007/s10898-014-0209-8
Liqun Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (2005), no. 6, 1302–1324. MR 2178089, DOI 10.1016/j.jsc.2005.05.007
Liqun Qi, Haibin Chen, and Yannan Chen, Tensor eigenvalues and their applications, Advances in Mechanics and Mathematics, vol. 39, Springer, Singapore, 2018. MR 3791481, DOI 10.1007/978-981-10-8058-6
Liqun Qi and Ziyan Luo, Tensor analysis, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017. Spectral theory and special tensors. MR 3660696, DOI 10.1137/1.9781611974751.ch1
Liqun Qi, Yiju Wang, and Ed X. Wu, $D$-eigenvalues of diffusion kurtosis tensors, J. Comput. Appl. Math. 221 (2008), no. 1, 150–157. MR 2458758, DOI 10.1016/j.cam.2007.10.012
Marcelo Queiroz, Joaquim Júdice, and Carlos Humes Jr., The symmetric eigenvalue complementarity problem, Math. Comp. 73 (2004), no. 248, 1849–1863. MR 2059739, DOI 10.1090/S0025-5718-03-01614-4
Yisheng Song and Liqun Qi, Eigenvalue analysis of constrained minimization problem for homogeneous polynomial, J. Global Optim. 64 (2016), no. 3, 563–575. MR 3461403, DOI 10.1007/s10898-015-0343-y
Liping Zhang and Ziyou Gao, Superlinear/quadratic one-step smoothing Newton method for $P_0$-NCP without strict complementarity, Math. Methods Oper. Res. 56 (2002), no. 2, 231–241. MR 1938212, DOI 10.1007/s001860200221
Liping Zhang, Liqun Qi, and Guanglu Zhou, $M$-tensors and some applications, SIAM J. Matrix Anal. Appl. 35 (2014), no. 2, 437–452. MR 3190753, DOI 10.1137/130915339