Abstract
In this paper, we focus on a class of horizontal tensor complementarity problems (HTCPs). By introducing the block representative tensor, we show that finding a solution of HTCP is equivalent to finding a nonnegative solution of a related tensor equation. We establish the theory of the existence and uniqueness of solution of HTCPs under the proper assumptions. In particular, in the case of the concerned block representative tensor possessing the strong M-property, we propose an algorithm to solve HTCPs by efficiently exploiting the beneficial properties of block representative tensor, and show that the iterative sequence generated by the algorithm is monotone decreasing and converges to a solution of HTCPs. The final numerical experiments verify the correctness of the theory in this paper and show the effectiveness of the proposed algorithm.
Similar content being viewed by others
Data Availibility
The data used to support the findings of this study are available from the corresponding author upon request.
References
Berman, A., Plemmons, R.: Nonnegative Matrices in the Mathematical Sciences. SIAM, Philadelphia (1994)
Demoor, B., Vandenberghe, L., Vandervalle, J.: The generalized linear complementarity problem and an algorithm to find all its solutions. Math. Program. 57, 415–426 (1992)
Dai, P.F.: A fixed point iterative method for tensor complementarity problems. J. Sci. Comput. 84, 49 (2020)
Ding, W.Y., Qi, L.Q., Wei, Y.M.: \(M\)-tensors and nonsingular \(M\)-tensors. Linear Algebra Appl. 439(10), 3264–3278 (2013)
Du, S.Q., Zhang, L.P.: A mixed integer programming approach to the tensor complementarity problem. J. Glob. Optim. 73, 789–800 (2019)
Ding, W.Y., Wei, Y.M.: Solving multi-linear systems with \(M\)-tensors. J. Sci. Comput. 68(2), 683–715 (2016)
Guan, H.B., Li, D.H.: Linearized methods for tensor complementarity problems. J. Optim. Theory Appl. 184, 972–987 (2020)
Gao, X., Wang, J.: Analysis and application of a one-layer neural network for solving horizontal linear complementarity problems. Int. J. Comput. Intell. Syst. 7(4), 724–732 (2014)
Gowda, M., Luo, Z.Y., Qi, L.Q., Xiu, N.H.: \(Z\)-tensors and complementarity problems. arXiv:1510.07933v2
Huang, Z.H., Li, Y.F., Miao, X.H.: Finding the least element of a nonnegative solution set of a class of polynomial inequalities. SIAM J. Matrix Anal. Appl. 44(2), 530–558 (2023)
Huang, Z.H., Qi, L.Q.: Formulating an \(n\)-person noncooperative game as a tensor complementarity problem. Comput. Optim. Appl. 66, 557–576 (2017)
Huang, Z.H., Qi, L.: Tensor complementarity problems-part I: basic theory. J. Optim. Theory Appl. 183(1), 1–23 (2019)
Huang, Z.H., Li, Y.F., Wang, Y.: A fixed point iterative method for tensor complementarity problems with the implicit \(Z\)-tensors. J. Glob. Optim. 86, 495–520 (2023)
He, H.J., Bai, X.L., Ling, C., Zhou, G.L.: An index detecting algorithm for a class of TCP(\(\mathscr {A}\), q) equipped with nonsingular \(M\)-tensors. J. Comput. Appl. Math. 394, 113548 (2021)
Luo, Z.Y., Qi, L.Q., Xiu, N.H.: The sparsest solution to \(Z\)-tensor complementarity problems. Optim. Lett. 11, 471–482 (2017)
Lim, L.: Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of the IEEE International Workshop on Computational Advances in Multi-sensor Adaptive Processing, CAMSAP05, pp. 129–132. IEEE Computer Society Press, Piscataway (2005)
Li, D.H., Guan, H.B., Wang, X.Z.: Finding a nonnegative solution to an \(M\)-tensor equation. Pac. J. Optim. 16(3), 419–440 (2020)
Meyer, G.H.: Free boundary problems with nonlinear source terms. Numer. Math. 43, 463–482 (1984)
Mezzadri, F., Galligani, E.: Splitting methods for a class of horizontal linear complementarity problems. J. Optim. Theory Appl. 180(2), 500–517 (2019)
Mezzadri, F., Galligani, E.: Modulus-based matrix splitting methods for horizontal linear complementarity problems. Numer. Algorithms 83, 201–219 (2020)
Mezzadri, F.: Modulus-based synchronous multisplitting methods for solving horizontal linear complementarity problems on parallel computers. Numer. Linear Algebra Appl. 27(5), e2319 (2020)
Mezzadri, F., Galligani, E.: A modulus-based nonsmooth Newton’s method for solving horizontal linear complementarity problems. Optim. Lett. 15, 1785–1798 (2021)
Mezzadri, F., Galligani, E.: An inexact Newton method for solving complementarity problems in hydrodynamic lubrication. Calcolo 55, 1 (2018)
Qi, L.Q.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40(6), 1302–1324 (2005)
Sznajder, R., Gowda, M.S.: Generalizations of \(P_0\)- and \(P\)-properties; extended vertical and horizontal linear complementarity problems. Linear Algebra Appl. 224, 695–715 (1995)
Tian, L.Y., Wang, Y.: Solving tensor complementarity problems with \(Z\)-tensors via a weighted fixed point method. J. Ind. Manag. Optim. 19(5), 3444–3458 (2023)
Vandenberghe, L., Demoor, B., Vandervalle, J.: The generalized linear complementarity problem applied to the complete analysis of restrictive piecewise-linear circuits. IEEE Trans. Circuits Syst. 11, 1382–1391 (1989)
Wang, X.Y., Jiang, X.W.: A homotopy method for solving the horizontal linear complementarity problem. Comput. Appl. Math. 33, 1–11 (2014)
Xie, S.L., Li, D.H., Xu, H.R.: An iterative method for finding the least solution to the tensor complementarity problem. J. Optim. Theory Appl. 175, 119–136 (2017)
Zhang, Y.: On the convergence of a class on infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optim. 4(1), 208–227 (1994)
Zheng, H., Vong, S.: On convergence of the modulus-based matrix splitting iteartion method for horizontal linear complementarity problem of \(H_+\)-matrices. Appl. Math. Comput. 369, 1–6 (2020)
Zhang, L.P., Qi, L.Q., Zhou, G.L.: \(M\)-tensors and some applications. SIAM J. Matrix Anal. Appl. 35, 437–452 (2014)
Zheng, H., Vong, S.: A two-step modulus-based matrix splitting iteration method for horizontal linear complementarity problems. Numer. Algorithms 86, 1791–1810 (2021)
Zheng, X.H., Wang, Y., Huang, Z.H.: A linearized method for solving tensor complementarity problems with implicit \(Z\)-tensors. Optim. Lett. (2023). https://doi.org/10.1007/s11590-023-02043-3
Acknowledgements
This work was partially supported by the National Natural Science Foundation of China (Grant Nos. 12171357 and 12371309).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have no conflict of interest to declare that are relevant to the content of this article.
Additional information
Communicated by Emanuele Galligani.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Sun, C., Wang, Y. & Huang, ZH. An Iterative Method for Horizontal Tensor Complementarity Problems. J Optim Theory Appl 202, 854–877 (2024). https://doi.org/10.1007/s10957-024-02450-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-024-02450-1
Keywords
- Horizontal tensor complementarity problem
- Tensor equation
- Block representative tensor
- Monotonically decreasing sequence
- Strong M-property