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;
- Math. Comp. 90 (2021), 215-231
- DOI: https://doi.org/10.1090/mcom/3558
- Published electronically: August 4, 2020
- HTML | PDF | 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
Bibliographic Information
- Liping Zhang
- Affiliation: Department of Mathematical Sciences, Tsinghua University, Beijing, 100084, People’s Republic of China
- Email: lipingzhang@tsinghua.edu.cn
- Chiyu Chen
- Affiliation: Department of Mathematical Sciences, Tsinghua University, Beijing, 100084, People’s Republic of China
- Email: ccyjust@mails.tsinghua.edu.cn
- Received by editor(s): August 26, 2019
- Received by editor(s) in revised form: March 5, 2020
- Published electronically: August 4, 2020
- Additional Notes: The first author was supported by the National Nature Science Foundation of China (Grant No. 11771244).
- © Copyright 2020 American Mathematical Society
- Journal: Math. Comp. 90 (2021), 215-231
- MSC (2010): Primary 90C33, 15A18; Secondary 90C30, 15A69
- DOI: https://doi.org/10.1090/mcom/3558
- MathSciNet review: 4166459