• Original Articles •

### LINEAR CONVERGENCE OF THE LZI ALGORITHM FOR WEAKLY POSITIVE TENSORS

Liping Zhang1, Liqun Qi2, Yi Xu2

1. 1. Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China;
2. Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong
• Received:2011-02-14 Revised:2011-06-09 Online:2012-01-15 Published:2012-01-15
• Supported by:

This first author’s work was supported by the National Natural Science Foundation of China (Grant No. 10871113). This second author’s work was supported by the Hong Kong Research Grant Council.

Liping Zhang, Liqun Qi, Yi Xu. LINEAR CONVERGENCE OF THE LZI ALGORITHM FOR WEAKLY POSITIVE TENSORS[J]. Journal of Computational Mathematics, 2012, 30(1): 24-33.

We define weakly positive tensors and study the relations among essentially positive tensors, weakly positive tensors, and primitive tensors. In particular, an explicit linear convergence rate of the Liu-Zhou-Ibrahim(LZI) algorithm for finding the largest eigenvalue of an irreducible nonnegative tensor, is established for weakly positive tensors. Numerical results are given to demonstrate linear convergence of the LZI algorithm for weakly positive tensors.

CLC Number:

 [1] S.R. Bulo and M. Pelillo, New bounds on the clique number of graphs based on spectral hypergraph theory, in: T. Stützle ed., Learning and Intelligent Optimization, Springer Verlag, Berlin, (2009), 45-48.[2] K.C. Chang, K. Pearson and T. Zhang, Perron Frobenius Theorem for nonnegative tensors, Commu. Math. Sci., 6 (2008), 507-520.[3] K.C. Chang, K. Pearson and T. Zhang, On eigenvalue problems of real symmetric tensors, J. Math. Anal. Appl., 350(2009), 416-422.[4] K.C. Chang, K. Pearson and T. Zhang, Primitivity, the convergence of the NZQ method, and the largest eigenvalue for nonnegative tensors, SIAM J. Matrix Anal. A., 32 (2011), 806-819.[5] S. Friedland, S. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, to appear in: Linear Algebra Appl.[6] C. Hillar and L.-H. Lim, Most tensor problems are NP hard, arXiv:0911.1393, 10 Nov 2009.[7] L.-H. Lim, Singular values and eigenvalues of tensors: a variational approach, in Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Addaptive Processing (CAMSAP’05), Vol. 1, IEEE Computer Society Press, Piscataway, NJ, 2005, 129-132.[8] C. Ling, J. Nie, L. Qi and Y. Ye, Bi-quadratic optimization over unit spheres and semidefinite programming relaxations, SIAM J. Optimiz., 20 (2009), 1286-1310.[9] Y. Liu, G. Zhou and N.F. Ibrahim, An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor, J. Comput. Appl. Math., 235 (2010), 286-292.[10] M. Ng, L. Qi and G. Zhou, Finding the largest eigenvalue of a nonnegative tensor, SIAM J. Matrix Anal. A., 31 (2009), 1090-1099.[11] K. Pearson, Essentially Positive Tensors, International Journal of Algebra, 4 (2010), 421-427.[12] L. Qi, Eigenvalues of a real supersymmetric tensor,J. Symb. Comput., 40 (2005), 1302-1324.[13] L. Qi, Eigenvalues and invariants of tensor, J. Math. Anal. Appl., 325 (2007), 1363-1377.[14] L. Qi, W. Sun and Y. Wang, Numerical multilinear algebra and its applications, Frontiers Math. China, 2 (2007), 501-526.[15] L. Qi, Y. Wang and E.X. Wu, D-eigenvalues of diffusion kurtosis tensor, J. Comput. Appl. Math., 221 (2008), 150-157.[16] C. Van Loan, Future dirctions in tensor-based computation and modeling, Workshop Report in Arlington, Virginia at National Science Foundation, February 20-21, 2009. http://www.cs.cornell.edu/cv/TenWork/Home.htm.[17] Y.N. Yang and Q.Z. Yang, Further results for Perron-Frobenius Theorem for nonnegative tensors, SIAM J. Matrix Anal. A., 31 (2010), 2517-2530.
 [1] Ernest K. Ryu, Wotao Yin. PROXIMAL-PROXIMAL-GRADIENT METHOD [J]. Journal of Computational Mathematics, 2019, 37(6): 778-812. [2] Yunfeng Cai, Zhaojun Bai, John E. Pask, N. Sukumar. CONVERGENCE ANALYSIS OF A LOCALLY ACCELERATED PRECONDITIONED STEEPEST DESCENT METHOD FOR HERMITIAN-DEFINITE GENERALIZED EIGENVALUE PROBLEMS [J]. Journal of Computational Mathematics, 2018, 36(5): 739-760. [3] Cong D. Dang, Guanghui Lan, Zaiwen Wen. LINEARLY CONVERGENT FIRST-ORDER ALGORITHMS FOR SEMIDEFINITE PROGRAMMING [J]. Journal of Computational Mathematics, 2017, 35(4): 452-468. [4] Jinyan Fan, Jianyu Pan, Hongyan Song. A RETROSPECTIVE TRUST REGION ALGORITHM WITH TRUST REGION CONVERGING TO ZERO [J]. Journal of Computational Mathematics, 2016, 34(4): 421-436. [5] Jinghui Liu, Changfeng Ma. A NEW NONMONOTONE TRUST REGION ALGORITHM FOR SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(4): 476-490. [6] Fusheng Wang, Chuanlong Wang, Li Wang. A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM [J]. Journal of Computational Mathematics, 2012, 30(3): 262-278. [7] Xuebin Wang, Changfeng Ma, Meiyan Li. A SMOOTHING TRUST REGION METHOD FOR NCPS BASED ON THE SMOOTHING GENERALIZED FISCHER-BURMEISTER FUNCTION [J]. Journal of Computational Mathematics, 2011, 29(3): 261-286. [8] Chang-yin Zhou,Guo-ping He,Yong-li Wang . A NEW CONSTRAINTS IDENTIFICATION TECHNIQUE-BASED QP-FREE ALGORITHM FOR THE SOLUTION OF INEQUALITY CONSTRAINED MINIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2006, 24(5): 591-608. [9] Cheng-xian Xu, Yue-ting Yang. Convergence Properties of Multi-directional Parallel Algorithms for Unconstrained Minimization [J]. Journal of Computational Mathematics, 2005, 23(4): 357-372. [10] Xin-long Luo. Singly Diagonally Implicit Runge-Kutta Methods Combining Line Search Techniques for Unconstrained Optimization [J]. Journal of Computational Mathematics, 2005, 23(2): 153-164. [11] Wei Wang, Lian-sheng Zhang, Yi-fan Xu . A Revised Conjugate Gradient Projection Algorithm for Inequality Constrained Optimizations [J]. Journal of Computational Mathematics, 2005, 23(2): 217-224. [12] Ju Liang ZHANG, Jian CHEN. A SMOOTHING LEVENBERG-MARQUARDT TYPE METHOD FOR LCP [J]. Journal of Computational Mathematics, 2004, 22(5): 735-752. [13] Ju Liang ZHANG, Jian CHEN,Xin Jian ZHUO. A CONSTRAINED OPTIMIZATION APPROACH FOR LCP [J]. Journal of Computational Mathematics, 2004, 22(4): 509-522. [14] De Ren HAN. A TRULY GLOBALLY CONVERGENT FEASIBLE NEWTON-TYPE METHOD FOR MIXED COMPLEMENTARITY PROBLEMS [J]. Journal of Computational Mathematics, 2004, 22(3): 347-360. [15] Chang Feng MA,Pu Yan NIE,Guo Ping LIANG. A NEW SMOOTHING EQUATIONS QPPROACH TO THE NONLINEAR COMPLEMENTARITY PROBLEMS$^*1$ [J]. Journal of Computational Mathematics, 2003, 21(6): 747-758.
Viewed
Full text

Abstract