New accelerated modulus-based iteration method for solving large and sparse linear complementarity problem

Bharat Kumar; Deepmala; A. K. Das

doi:10.33993/jnaat531-1370

Authors

Bharat Kumar PDPM-Indian Institute of Information Technology, Design and Manufacturing, Jabalpur, M.P., India https://orcid.org/0000-0003-3026-1378
Deepmala PDPM-Indian Institute of Information Technology, Design and Manufacturing, Jabalpur, M.P., India
A. K. Das Indian Statistical Institute, Kolkata, India https://orcid.org/0000-0003-2508-7563

DOI:

https://doi.org/10.33993/jnaat531-1370

Keywords:

Linear complementarity problem, $P$-matrix, $H_{ }$-matrix, matrix splitting, convergence

Abstract views: 90

Abstract

For the large and sparse linear complementarity problem, we provide a family of new accelerated modulus-based iteration methods in this article. We provide some sufficient criteria for the convergence analysis when the system matrix is a $P$-matrix or an $H_+$-matrix. In addition, we provide some numerical examples of the different parameters to illustrate the efficacy of our proposed methods. These methods help us reduce the number of iterations and the time required by the CPU, which improves convergence performance.

Downloads

Download data is not yet available.

References

A Berman and R J Plemmons, Nonnegative Matrices in the Mathematical Science, (New York: Academic Press) (1979). DOI: https://doi.org/10.1016/B978-0-12-092250-5.50009-6

A Frommer and D B Szyl, H-splittings and two-stage iteration methods, Numer. Math., 63 (1992) 345-356. https://doi.org/10.1007/BF01385865 DOI: https://doi.org/10.1007/BF01385865

A Hadjidimos and L.L. Zhang, Comparison of three classes of algorithms for the solution of the linear complementarity problem with an H+-matrix. Journal of Computational and Applied Mathematics, 336 (2018) 175-191. https://doi.org/10.1016/j.cam.2017.12.028 DOI: https://doi.org/10.1016/j.cam.2017.12.028

A Hadjidimos and M Tzoumas, Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem, Linear Algebra Appl.431 (2009) 197-210. DOI: https://doi.org/10.1016/j.laa.2009.02.024

B H Ahn, Solutions of nonsymmetric linear complementarity problems by iterative methods, J. Opt.Theory Appl. 33 (1981) 175-185. https://doi.org/10.1007/BF00935545 DOI: https://doi.org/10.1007/BF00935545

B Kumar, Deepmala, A Dutta, and AK Das. More on matrix splitting modulus-based iterative methods for solving linear complementarity problem. OPSEARCH, (2023) 1–18. https://doi.org/10.1007/s12597-023-00634-3 DOI: https://doi.org/10.1007/s12597-023-00634-3

B Kumar, Deepmala and A K Das, Projected fixed point iterative method for large and sparse horizontal linear complementarity problem. Indian Journal of Pure and Applied Mathematics (2023) 1-10. https://doi.org10.1007/s13226-023-00403-4 DOI: https://doi.org/10.1007/s13226-023-00403-4

C F Ma and N Huang, Modified modulus-based matrix splitting algorithms for a class of weakly nondifferentiable nonlinear complementarity problems, Appl. Numer. Math., 108 (2016) 116-124. urlhttps://doi.org/10.1016/j.apnum.2016.05.004 DOI: https://doi.org/10.1016/j.apnum.2016.05.004

D Yuan and Y Song, Modified AOR methods for linear complementarity problems, Applied Mathematics and Comput., 140(1) (2003) 53-67. https://doi.org/10.1016/S0096-3003(02)00194-7 DOI: https://doi.org/10.1016/S0096-3003(02)00194-7

F Mezzadri and E Galligani, Modulus-based matrix splitting methods for horizontal linear complementarity problems, Numer. Alg., 83 (2020) 201-219. https://doi.org/10.1007/s11075-019-00677-y DOI: https://doi.org/10.1007/s11075-019-00677-y

H S Najafi and S A Edalatpanah, Modification of iterative methods for solving linear complementarity problems. Engineering Computations, 30(7) (2013) 910-923. https://doi.org/10.1108/EC-10-2011-0131 DOI: https://doi.org/10.1108/EC-10-2011-0131

J L Dong and M Q Jiang, A modified modulus method for symmetric positive definite linear complementarity problems, Numerical Linear Algebra with Appl., 16(2) (2009) 129-143. https://doi.org/https://doi.org/10.1002/nla.609 DOI: https://doi.org/10.1002/nla.609

J T Hong and C L Li, Modulus-based matrix splitting iteration methods for a class of implicit complementarity problems, Numer. Linear Algebra Appl., 23 (2016) 629-641. DOI: https://doi.org/10.1002/nla.2044

K G. Murty, On the number of solutions to the complementarity problem and spanning properties of complementary cones, Linear Algebra Appl., 5 (1972), 65–108. https://doi.org/10.1016/0024-3795(72)90019-5 DOI: https://doi.org/10.1016/0024-3795(72)90019-5

L L Zhang, Two-step modulus-based matrix splitting iteration method for linear complementarity problems, Numer. Alg., 57 (2011) 83-99. https://doi.org/10.1007/s11075-010-9416-7 DOI: https://doi.org/10.1007/s11075-010-9416-7

L L Zhang and Z R Ren, Improved convergence theorems of Modulus-based matrix splitting iteration methods for linear complementarity problems, Applied Mathematics Lett., 26(6) (2013) 638-642. https://doi.org/10.1016/j.aml.2013.01.001 DOI: https://doi.org/10.1016/j.aml.2013.01.001

M J Alves and J. Judice, On the use of a tabu pivoting technique for solving the linear complementarity problem, AMO-Advanced Modeling and Optimization 13 (2011) 111-140.

N Huang and C F Ma, The modulus-based matrix splitting algorithms for a class of weakly nondifferentiable nonlinear complementarity problems, Numer. Linear Algebra Appl., 23 (2016) 558-569. https://doi.org/10.1002/nla.2039 DOI: https://doi.org/10.1002/nla.2039

N W Kappel and L T Watson, Iterative algorithms for the linear complementarity problems, Int. J. Comput. Math., 19 (1986) 273-297. DOI: https://doi.org/10.1080/00207168608803522

N Zheng and J F Yin, Accelerated modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Alg., 64 (2013) 245-262. https://doi.org/10.1007/s11075-012-9664-9 DOI: https://doi.org/10.1007/s11075-012-9664-9

O L Mangasarian, Solution of symmetric linear complementarity problems by iterative methods, Journal of Optimization Theory and Appl., 22 (1977) 465-485. https://doi.org/10.1007/BF01268170 DOI: https://doi.org/10.1007/BF01268170

R Ali, I Khan, A Ali and A Mohamed, Two new generalized iteration methods for solving absolute value equations using M -matrix, AIMS Math., 7(5) (2022) 8176-8187. DOI: https://doi.org/10.3934/math.2022455

R Jana, A.K. Das and A. Dutta, On hidden Z-matrix and interior point algorithm.OPSEARCH, 56(09) (2019) https://doi.org/10.1007/s12597-019-00412-0 DOI: https://doi.org/10.1007/s12597-019-00412-0

S K Neogy, A K Das and A Gupta, Generalized principal pivot transforms, complementarity theory and their applications in stochastic games, Optimization Lett.,6(2) (2012) 339-356. DOI: https://doi.org/10.1007/s11590-010-0261-3

R W Cottle, Complementary pivoting algorithm, Encyclopedia of Operations, Research and Management Science 92 (2012).

S L Wu and P Guo, Modulus-based matrix splitting algorithms for the quasi-complementarity problems, Appl. Numer. Math., 132 (2018) 127-137. https://doi.org/10.1016/j.apnum.2018.05.017 DOI: https://doi.org/10.1016/j.apnum.2018.05.017

V W M G Bokhoven, A Class of Linear Complementarity Problems is Solvable in Polynomial Time, University of Technology, The Netherlands, Unpublished Paper, Dept. of Electrical Engineering (1980).

W Li, A general modulus-based matrix splitting method for linear complementarity problems of H-matrices, Appl. Math. Lett., 26 (2013) 1159-1164. https://doi.org/10.1016/j.aml.2013.06.015 DOI: https://doi.org/10.1016/j.aml.2013.06.015

W Shilang and L Cuixia, A class of new modulus-based matrix splitting methods for linear complementarity problem, Optimization Lett., 16 (2021) 1427-1443. https://doi.org/10.1007/s11590-021-01781-6 DOI: https://doi.org/10.1007/s11590-021-01781-6

W W Xu, Modified modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 22 (2015) 748-760. https://doi.org/10.1002/nla.1985 DOI: https://doi.org/10.1002/nla.1985

X M Fang, General fixed point method for solving the linear complementarity problem, AIMS Mathematics, 6(11) (2021) 11904-11920. https://doi.org/10.3934/math.2021691 DOI: https://doi.org/10.3934/math.2021691

Z C Xia and C L Li, Modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problem, Appl. Math. Comput., 271 (2015) 34-42. http://dx.doi.org/10.1016/j.amc.2015.08.108 DOI: https://doi.org/10.1016/j.amc.2015.08.108

Z Z Bai, Modulus-based matrix splitting iteration methods for linear complementarity problems, Numerical Linear Algebra with Appl., 17(6) (2010) 917-933. https://doi.org/10.1002/nla.680 DOI: https://doi.org/10.1002/nla.680

Z Z Bai and D Evans, Matrix multisplitting relaxation methods for linear complementarity problems, International Journal of Computer Math., 63(3-4) (1997) 309-326. https://doi.org/10.1080/00207169708804569 DOI: https://doi.org/10.1080/00207169708804569