Column sufficient tensors and tensor complementarity problems

Abstract

Stimulated by the study of sufficient matrices in linear complementarity problems, we study column sufficient tensors and tensor complementarity problems. Column sufficient tensors constitute a wide range of tensors that include positive semi-definite tensors as special cases. The inheritance property and invariant property of column sufficient tensors are presented. Then, various spectral properties of symmetric column sufficient tensors are given. It is proved that all H-eigenvalues of an even-order symmetric column sufficient tensor are nonnegative, and all its Z-eigenvalues are nonnegative even in the odd order case. After that, a new subclass of column sufficient tensors and the handicap of tensors are defined. We prove that a tensor belongs to the subclass if and only if its handicap is a finite number. Moreover, several optimization models that are equivalent with the handicap of tensors are presented. Finally, as an application of column sufficient tensors, several results on tensor complementarity problems are established.

Keywords

Column sufficient tensor / H-eigenvalue / tensor complementarity problems / handicap

References

[1] Bai X, Huang Z, Wang Y. Global uniqueness and solvability for tensor complementarity problems. J Optim Theory Appl, 2016, 170: 1–13

[2] Bu C, Zhang X, Zhou J, Wang W, Wei Y. The inverse, rank and product of tensors. Linear Algebra Appl, 2014, 446: 269–280

[3] Che M, Qi L, Wei Y. Positive definite tensors to nonlinear complementarity problems. J Optim Theory Appl, 2016, 168(2): 475–487

[4] Chen H, Chen Y, Li G, Qi L. A semi-definite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test. Numer Linear Algebra Appl, 2018, 25: e2125

[5] Chen H, Huang Z, Qi L. Copositivity detection of tensors: theory and algorithm. J Optim Theory Appl, 2017, 174: 746–761

[6] Chen H, Huang Z, Qi L. Copositive tensor detection and its applications in physics and hypergraphs. Comput Optim Appl, 2017, https://doi.org/10.1007/s10589-017-9938-1

[7] Chen H, Li G, Qi L. SOS tensor decomposition: theory and applications. Commun Math Sci, 2016, 14(8): 2073–2100

[8] Chen H, Qi L. Positive definiteness and semi-definiteness of even order symmetric Cauchy tensors. J Ind Manag Optim, 2015, 11: 1263–1274

[9] Chen H, Wang Y. On computing minimal H-eigenvalue of sign-structured tensors. Front Math China, 2017, 12(6): 1289–1302

[10] Chen Z, Qi L. Circulant tensors with applications to spectral hypergraph theory and stochastic process. J Ind Manag Optim, 2016, 12: 1227–1247

[11] Cooper J, Dutle A. Spectra of uniform hypergraphs. Linear Algebra Appl, 2012, 436: 3268–3292

[12] Cottle R W, Guu S M. Are P_∗-matrices just sufficient? Presented at the 36th Joint National Meeting of Operations Research Society of America and the Institute of Management Science, Phoenix, AZ, 1 Nov, 1993

[13] Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problem.Boston: Academic Press, 1992

[14] Cottle R W, Pang J S, Venkateswaran V. Sufficient matrices and the linear complementarity problem. Linear Algebra Appl, 1989, 114: 231–249

[15] Ding W, Qi L, Wei Y. M-Tensors and nonsingular M-tensors. Linear Algebra Appl, 2013, 439: 3264–3278

[16] Ding W, Qi L, Wei Y. Fast Hankel tensor-vector products and application to exponential data fitting. Numer Linear Algebra Appl, 2015, 22: 814–832

[17] Gowda M S, Luo Z, Qi L, Xiu N. Z-tensors and complementarity problems. 2015, arXiv: 1510.07933

[18] Guu S M, Cottle R W. On a subclass of P₀.Linear Algebra Appl, 1995, 223: 325–335

[19] Han J Y, Xiu N H, Qi H D. Nonlinear Complementary Theory and Algorithm.Shanghai: Shanghai Science and Technology Press, 2006

[20] Huang Z, Qi L. Formulating an n-person noncooperative game as a tensor complementarity problems. Comput Optim Appl, 2017, 66: 557–576

[21] Kannan M R, Shaked-Monderer N, Berman A. Some properties of strong H-tensors and general H-tensors. Linear Algebra Appl, 2015, 476: 42–55

[22] Klerk E D, Nagy M E. On the complexity of computing the handicap of a sufficient matrix. Math Program, 2011, 129(2): 383–402

[23] Kojima M, Megiddo N, Noma T, Yoshise A. A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems.Berlin: Springer-Verlag, 1991

[24] Li C, Li Y. Double B tensors and quasi-double B tensors. Linear Algebra Appl, 2015, 466: 343–356

[25] Li C, Wang F, Zhao J, Zhu Y, Li Y. Criterions for the positive definiteness of real supersymmetric tensors. J Comput Appl Math, 2014, 255: 1–14

[26] Lim L H. Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of the IEEE InternationalWorkshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP05), Vol 1. 2005, 129–132

[27] Luo Z, Qi L, Xiu N. The sparsest solutions to Z-tensor complementarity problems. Optim Lett, 2017, 11(3): 471–482

[28] Ng M, Qi L, Zhou G. Finding the largest eigenvalue of a non-negative tensor. SIAM J Matrix Anal Appl, 2009, 31: 1090–1099

[29] Ni Q, Qi L. A quadratically convergent algorithm for finding the largest eigenvalue of a nonnegative homogeneous polynomial map. J Global Optim, 2015, 61: 627–641

[30] Qi L. Eigenvalue of a real supersymmetric tensor. J Symbolic Comput, 2005, 40: 1302–1324

[31] Qi L. H⁺-eigenvalues of Laplacian and signless Laplacian tensors. Commun Math Sci, 2014, 12: 1045–1064

[32] Qi L. Hankel tensors: associated Hankel matrices and Vandermonde decomposition. Commun Math Sci, 2015, 13: 113–125

[33] Qi L, Song Y. An even order symmetric B tensor is positive definite. Linear Algebra Appl, 2014, 457: 303–312

[34] Qi L, Wei Y, Xu C, Zhang T. Linear algebra and multi-linear algebra. Front Math China, 2016, 11(3): 509–510

[35] Qi L, Yu G, Wu E X. Higher order positive semi-definite diffusion tensor imaging. SIAM J Imaging Sci, 2010, 3: 416–433

[36] Shao J Y. A general product of tensors with applications. Linear Algebra Appl, 2013, 439: 2350–2366

[37] Shao J Y, Shan H Y, Zhang L. On some properties of the determinants of tensors. Linear Algebra Appl, 2013, 439: 3057–3069

[38] Song Y, Qi L. Infinite and finite dimensional Hilbert tensors. Linear Algebra Appl, 2014, 451: 1–14

[39] Song Y, Qi L. Properties of some classes of structured tensors. J Optim Theory Appl, 2015, 165: 854–873

[40] Song Y, Qi L. Tensor complementarity problems and semi-positive tensors. J Optim Theory Appl, 2016, 169(3): 1069–1078

[41] Song Y, Qi L. Strictly semi-positive tensors and the boundedness of tensor complementarity problems. Optim Lett, 2017, 11(7): 1407–1426

[42] Song Y, Qi L. Properties of tensor complementarity problem and some classes of structured tensors. Ann of Appl Math, 2017, 33(3): 308–323

[43] Sun J, Huang Z. A smoothing Newton algorithm for the LCP with a sufficient matrix that terminates finitely at a maximally complementary solution. Optim Methods Softw, 2006, 21: 597–615

[44] Väliaho H. P_∗-matrices are just sufficient. Linear Algebra Appl, 1996, 239: 103–108

[45] Zhang L, Qi L, Zhou G. M-tensors and some applications. SIAM J Matrix Anal Appl, 2014, 35: 437–452

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature