Column sufficient tensors and tensor complementarity problems

doi:10.1007/s11464-018-0681-4

Front. Math. China

2018, Vol. 13

Issue (2) : 255-276 https://doi.org/10.1007/s11464-018-0681-4

RESEARCH ARTICLE

Column sufficient tensors and tensor complementarity problems

Haibin CHEN¹, Liqun QI², Yisheng SONG³(

)

¹. School of Management Science, Qufu Normal University, Rizhao 276826, China
². Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China
³. School of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China

Download: PDF(232 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Yisheng SONG

Issue Date: 28 March 2018

Cite this article:

Haibin CHEN,Liqun QI,Yisheng SONG. Column sufficient tensors and tensor complementarity problems[J]. Front. Math. China, 2018, 13(2): 255-276.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-018-0681-4
https://academic.hep.com.cn/fmc/EN/Y2018/V13/I2/255

1	Bai X, Huang Z, Wang Y. Global uniqueness and solvability for tensor complementarity problems. J Optim Theory Appl, 2016, 170: 1–13 https://doi.org/10.1007/s10957-016-0903-4
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 https://doi.org/10.1016/j.laa.2013.12.015
3	Che M, Qi L, Wei Y. Positive definite tensors to nonlinear complementarity problems. J Optim Theory Appl, 2016, 168(2): 475–487 https://doi.org/10.1007/s10957-015-0773-1
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 https://doi.org/10.1002/nla.2125
5	Chen H, Huang Z, Qi L. Copositivity detection of tensors: theory and algorithm. J Optim Theory Appl, 2017, 174: 746–761 https://doi.org/10.1007/s10957-017-1131-2
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 https://doi.org/10.4310/CMS.2016.v14.n8.a1
8	Chen H, Qi L. Positive definiteness and semi-definiteness of even order symmetric Cauchy tensors. J Ind Manag Optim, 2015, 11: 1263–1274 https://doi.org/10.3934/jimo.2015.11.1263
9	Chen H, Wang Y. On computing minimal H-eigenvalue of sign-structured tensors. Front Math China, 2017, 12(6): 1289–1302 https://doi.org/10.1007/s11464-017-0645-0
10	Chen Z, Qi L. Circulant tensors with applications to spectral hypergraph theory and stochastic process. J Ind Manag Optim, 2016, 12: 1227–1247 https://doi.org/10.3934/jimo.2016.12.1227
11	Cooper J, Dutle A. Spectra of uniform hypergraphs. Linear Algebra Appl, 2012, 436: 3268–3292 https://doi.org/10.1016/j.laa.2011.11.018
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 https://doi.org/10.1016/0024-3795(89)90463-1
15	Ding W, Qi L, Wei Y. M-Tensors and nonsingular M-tensors. Linear Algebra Appl, 2013, 439: 3264–3278 https://doi.org/10.1016/j.laa.2013.08.038
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 https://doi.org/10.1002/nla.1970
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 P0.Linear Algebra Appl, 1995, 223: 325–335 https://doi.org/10.1016/0024-3795(93)00271-Z
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 https://doi.org/10.1007/s10589-016-9872-7
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 https://doi.org/10.1016/j.laa.2015.02.034
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 https://doi.org/10.1007/s10107-011-0465-z
23	Kojima M, Megiddo N, Noma T, Yoshise A. A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems.Berlin: Springer-Verlag, 1991 https://doi.org/10.1007/3-540-54509-3
24	Li C, Li Y. Double B tensors and quasi-double B tensors. Linear Algebra Appl, 2015, 466: 343–356 https://doi.org/10.1016/j.laa.2014.10.027
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 https://doi.org/10.1016/j.cam.2013.04.022
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 https://doi.org/10.1007/s11590-016-1013-9
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 https://doi.org/10.1137/09074838X
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 https://doi.org/10.1007/s10898-014-0209-8
30	Qi L. Eigenvalue of a real supersymmetric tensor. J Symbolic Comput, 2005, 40: 1302–1324 https://doi.org/10.1016/j.jsc.2005.05.007
31	Qi L. H+-eigenvalues of Laplacian and signless Laplacian tensors. Commun Math Sci, 2014, 12: 1045–1064 https://doi.org/10.4310/CMS.2014.v12.n6.a3
32	Qi L. Hankel tensors: associated Hankel matrices and Vandermonde decomposition. Commun Math Sci, 2015, 13: 113–125 https://doi.org/10.4310/CMS.2015.v13.n1.a6
33	Qi L, Song Y. An even order symmetric B tensor is positive definite. Linear Algebra Appl, 2014, 457: 303–312 https://doi.org/10.1016/j.laa.2014.05.026
34	Qi L, Wei Y, Xu C, Zhang T. Linear algebra and multi-linear algebra. Front Math China, 2016, 11(3): 509–510 https://doi.org/10.1007/s11464-016-0540-0
35	Qi L, Yu G, Wu E X. Higher order positive semi-definite diffusion tensor imaging. SIAM J Imaging Sci, 2010, 3: 416–433 https://doi.org/10.1137/090755138
36	Shao J Y. A general product of tensors with applications. Linear Algebra Appl, 2013, 439: 2350–2366 https://doi.org/10.1016/j.laa.2013.07.010
37	Shao J Y, Shan H Y, Zhang L. On some properties of the determinants of tensors. Linear Algebra Appl, 2013, 439: 3057–3069 https://doi.org/10.1016/j.laa.2013.08.014
38	Song Y, Qi L. Infinite and finite dimensional Hilbert tensors. Linear Algebra Appl, 2014, 451: 1–14 https://doi.org/10.1016/j.laa.2014.03.023
39	Song Y, Qi L. Properties of some classes of structured tensors. J Optim Theory Appl, 2015, 165: 854–873 https://doi.org/10.1007/s10957-014-0616-5
40	Song Y, Qi L. Tensor complementarity problems and semi-positive tensors. J Optim Theory Appl, 2016, 169(3): 1069–1078 https://doi.org/10.1007/s10957-015-0800-2
41	Song Y, Qi L. Strictly semi-positive tensors and the boundedness of tensor complementarity problems. Optim Lett, 2017, 11(7): 1407–1426 https://doi.org/10.1007/s11590-016-1104-7
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 https://doi.org/10.1080/10556780600627727
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 https://doi.org/10.1137/130915339

[1]	Yizheng FAN, Zhu ZHU, Yi WANG. Least H-eigenvalue of adjacency tensor of hypergraphs with cut vertices[J]. Front. Math. China, 2020, 15(3): 451-465.
[2]	Haibin CHEN, Yiju WANG, Guanglu ZHOU. High-order sum-of-squares structured tensors: theory and applications[J]. Front. Math. China, 2020, 15(2): 255-284.
[3]	Junjie YUE,Liping ZHANG,Mei LU. Largest adjacency, signless Laplacian, and Laplacian H-eigenvalues of loose paths[J]. Front. Math. China, 2016, 11(3): 623-645.
[4]	Haibin CHEN,Liqun QI. Spectral properties of odd-bipartite Z-tensors and their absolute tensors[J]. Front. Math. China, 2016, 11(3): 539-556.
[5]	Jinshan XIE, An CHANG. H-Eigenvalues of signless Laplacian tensor for an even uniform hypergraph[J]. Front Math Chin, 2013, 8(1): 107-127.

Viewed

Full text

Abstract

Cited

Shared

Discussed