Abstract
In this paper, we consider the tensor generalized eigenvalue complementarity problem (TGEiCP), which is an interesting generalization of matrix eigenvalue complementarity problem (EiCP). First, we give an affirmative result showing that TGEiCP is solvable and has at least one solution under some reasonable assumptions. Then, we introduce two optimization reformulations of TGEiCP, thereby beneficially establishing an upper bound on cone eigenvalues of tensors. Moreover, some new results concerning the bounds on the number of eigenvalues of TGEiCP further enrich the theory of TGEiCP. Last but not least, an implementable projection algorithm for solving TGEiCP is also developed for the problem under consideration. As an illustration of our theoretical results, preliminary computational results are reported.
Similar content being viewed by others
References
Adly, S., Rammal, H.: A new method for solving Pareto eigenvalue complementarity problems. Comput. Optim. Appl. 55, 703–731 (2013)
Aubin, J.P., Frankowska, H.: Set-Valued Analysis. Springer, Berlin (2009)
Bloy, L., Verma, R.: On computing the underlying fiber directions from the diffusion orientation distribution function. In: Metaxas, D., Axel, L., Fichtinger, G., Székely, G. (eds.) Medical Image Computing and Computer-Assisted Intervention-MICCAI 2008, pp. 1–8. Springer, Berlin (2008)
Chang, K.C., Pearson, K., Zhang, T.: Perron-Frobenius theorem for nonnegative tensors. Commun. Math. Sci 6, 507–520 (2008)
Chang, K.C., Pearson, K., Zhang, T.: On eigenvalue problems of real symmetric tensors. J. Math. Anal. Appl. 350, 416–422 (2009)
Chung, S.J.: NP-completeness of the linear complementarity problem. J. Optim. Theory Appl. 60(3), 393–399 (1989)
Cox, D., Little, J., O’Shea, D.: Using Algebraic Geometry. Springer, New York (2005)
da Costa, A., Figueiredo, I., Júdice, J., Martins, J.: A complementarity eigenproblem in the stability analysis of finite dimensional elastic systems with frictional contact. In: Ferris, M., Pang, J.S., Mangasarian, O. (eds.) Complementarity: Applications, Algorithms and Extensions, pp. 67–83. Kluwer, New York (2001)
da Costa, A., Seeger, A.: Cone-constrained eigenvalue problems: theory and algorithms. Comput. Optim. Appl. 45(1), 25–57 (2010)
Facchinei, F., Pang, J.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
Ferris, M., Pang, J.: Engineering and economic applications of complementarity problems. SIAM Rev. 39(4), 669–713 (1997)
Golub, G.H., Van der Vorst, H.A.: Eigenvalue computation in the 20th century. J. Comput. Appl. Math. 123(1), 35–65 (2000)
Iusem, A., Seeger, A.: On convex cones with infinitely many critical angles. Optimization 56, 115–128 (2007)
Júdice, J.J., Raydan, M., Rosa, S.S., Santos, S.A.: On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm. Numer. Algor. 47(4), 391–407 (2008)
Júdice, J.J., Sherali, H.D., Ribeiro, I.M.: The eigenvalue complementarity problem. Comput. Optim. Appl. 37, 139–156 (2007)
Judice, J.J., Sherali, H.D., Ribeiro, I.M., Rosa, S.S.: On the asymmetric eigenvalue complementarity problem. Optim. Method Softw. 24(4–5), 549–568 (2009)
Lavilledieu, P., Seeger, A.: Existence de valeurs propres pour les systmes multivoques résultats anciens et nouveaux. Ann. Sci. Math. Que. 25, 47–70 (2001)
Lim, L.H.: Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Addaptive Processing. CAMSAP05, pp. 129–132. IEEE Computer Society Press, Piscataway (2005)
Ng, M., Qi, L., Zhou, G.: Finding the largest eigenvalue of a non-negative tensor. SIAM J. Matrix Anal. Appl. 31, 1090–1099 (2009)
Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40(6), 1302–1324 (2005)
Qi, L.: Symmetric nonnegative tensors and copositive tensors. Linear Alg. Appl. 439(1), 228–238 (2013)
Qi, L., Sun, W., Wang, Y.: Numerical multilinear algebra and its applications. Front. Math. China 2(4), 501–526 (2007)
Qi, L., Wang, F., Wang, Y.: Z-eigenvalue methods for a global polynomial optimization problem. Math. Program. 118(2), 301–316 (2009)
Qi, L., Yu, G., Wu, E.X.: Higher order positive semidefinite diffusion tensor imaging. SIAM J. Imaging Sci. 3, 416–433 (2010)
Queiroz, M., Judice, J., Humes Jr, C.: The symmetric eigenvalue complementarity problem. Math. Comput. 73, 1849–1863 (2004)
Rockafellar, R.: Convex processes and hamiltonian dynamical systems. Convex Analysis and Mathematical Economics. Lecture Notes in Econmics and Mathematical Systems, vol. 168, pp. 122–136. Springer, Berlin (1979)
Seeger, A.: Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions. Linear Alg. Appl. 292(1), 1–14 (1999)
Song, Y., Qi, L.: Eigenvalue analysis of constrained minimization problem for homogeneous polynomial. arXiv preprint arXiv:1302.6085 (2013)
Song, Y., Qi, L.: Necessary and sufficient conditions for copositive tensors. Linear Multilinear A. 63, 120–131 (2015)
Stewart, D.: Dynamics with Inequalities: Impacts and Hard Constraints. SIAM, Philadelphia (2011)
van der Vorst, H.A., Golub, G.H.: 150 years old and still alive: eigenproblems. In: The State of the Art in Numerical Analysis. Institute of Mathematics and its Applications, vol. 52, pp. 93–119. Oxford University Press, New York (1997)
Yang, Y., Yang, Q.: Further results for Perron-Frobenius theorem for nonnegative tensors. SIAM J. Matrix Anal. Appl. 31, 2517–2530 (2010)
Acknowledgments
The authors would like to thank the two anonymous referees for their close readings and valuable recommendations, which help us improve the presentation of this paper significantly. The first two authors were supported by National Natural Science Foundation of China (NSFC) at Grant Nos. (11171083, 11301123) and the Zhejiang Provincial NSFC at Grant No. LZ14A010003. The third author was supported by the Hong Kong Research Grant Council (Grant Nos. PolyU 502510, 502111, 501212 and 501913).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ling, C., He, H. & Qi, L. On the cone eigenvalue complementarity problem for higher-order tensors. Comput Optim Appl 63, 143–168 (2016). https://doi.org/10.1007/s10589-015-9767-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-015-9767-z
Keywords
- Higher order tensor
- Eigenvalue complementarity problem
- Cone eigenvalue
- Optimization reformulation
- Projection algorithm