A preconditioned new modulus-based matrix splitting method for solving linear complementarity problem of $ H_+ $-matrices

Dongmei Yu; Yifei Yuan; Yiming Zhang; Dongmei Yu; Yifei Yuan; Yiming Zhang

doi:10.3934/era.2023007

Electronic Research Archive

2023, Volume 31, Issue 1: 123-146. doi: 10.3934/era.2023007

Previous Article Next Article

Research article Special Issues

A preconditioned new modulus-based matrix splitting method for solving linear complementarity problem of $ H_+ $-matrices

1.
Institute for Optimization and Decision Analytics, Liaoning Technical University, Fuxin, 123000, China
2.
College of Science, Liaoning Technical University, Fuxin, 123000, China

Received: 21 June 2022 Revised: 08 September 2022 Accepted: 19 September 2022 Published: 24 October 2022

For solving the linear complementarity problem (LCP), we propose a preconditioned new modulus-based matrix splitting (PNMMS) iteration method by extending the state-of-the-art new modulus-based matrix splitting (NMMS) iteration method to a more general framework with a customized preconditioner. We devise a generalized preconditioner that is associated with both $ H_+ $-matrix $ A $ and vector $ q $ of the LCP. The convergence analysis is conducted under some mild conditions. In particular, we provide a comparison theorem to theoretically show the PNMMS method accelerates the convergence rate. Numerical experiments further illustrate that the PNMMS method is efficient and has better performance for solving the large and sparse LCP.
- linear complementarity problem,
- preconditioner,
- modulus-based matrix splitting method,
- comparison theorem,
- convergence analysis
Citation: Dongmei Yu, Yifei Yuan, Yiming Zhang. A preconditioned new modulus-based matrix splitting method for solving linear complementarity problem of $ H_+ $-matrices[J]. Electronic Research Archive, 2023, 31(1): 123-146. doi: 10.3934/era.2023007

Related Papers:

Abstract

For solving the linear complementarity problem (LCP), we propose a preconditioned new modulus-based matrix splitting (PNMMS) iteration method by extending the state-of-the-art new modulus-based matrix splitting (NMMS) iteration method to a more general framework with a customized preconditioner. We devise a generalized preconditioner that is associated with both $ H_+ $-matrix $ A $ and vector $ q $ of the LCP. The convergence analysis is conducted under some mild conditions. In particular, we provide a comparison theorem to theoretically show the PNMMS method accelerates the convergence rate. Numerical experiments further illustrate that the PNMMS method is efficient and has better performance for solving the large and sparse LCP.

References

[1]	N. W. Kappel, L. T. Watson, Iterative algorithms for the linear complementarity problem, Int. J. Comput. Math., 19 (1986), 273–297. https://doi.org/10.1080/00207168608803522 doi: 10.1080/00207168608803522
[2]	K. G. Murty, F.-T. Yu, Linear Complementarity, Linear and Nonlinear Programming, Heldermann: Berlin, Germany, 1988.
[3]	Y. Li, P. Dai, Generalized AOR methods for linear complementarity problem, Appl. Math. Comput., 188 (2007), 7–18. https://doi.org/10.1016/j.amc.2006.09.067 doi: 10.1016/j.amc.2006.09.067
[4]	O. L. Mangasarian, Solution of symmetric linear complementarity problems by iterative methods, J. Optim. Theory Appl., 22 (1977), 465–485. https://doi.org/10.1007/bf01268170 doi: 10.1007/bf01268170
[5]	H. Saberi Najafi, S. A. Edalatpanah, On the convergence regions of generalized accelerated overrelaxation method for linear complementarity problems, J. Optim. Theory Appl., 156 (2013), 859–866. https://doi.org/10.1007/s10957-012-0135-1 doi: 10.1007/s10957-012-0135-1
[6]	Y.-F. Ke, C.-F. Ma, On SOR-like iteration methods for solving weakly nonlinear systems, Optim. Methods Softw., 37 (2020), 320–337. https://doi.org/10.1080/10556788.2020.1755861 doi: 10.1080/10556788.2020.1755861
[7]	Y.-F. Ke, The new iteration algorithm for absolute value equation, Appl. Math. Lett., 99 (2020), 105990. https://doi.org/10.1016/j.aml.2019.07.021 doi: 10.1016/j.aml.2019.07.021
[8]	Z.-Z. Bai, On the convergence of the multisplitting methods for the linear complementarity problem, SIAM J. Matrix Anal. Appl., 21 (1999), 67–78. https://doi.org/10.1137/s0895479897324032 doi: 10.1137/s0895479897324032
[9]	Z.-Z. Bai, Parallel chaotic multisplitting iterative methods for the large sparse linear complementarity problem, J. Comput. Math., 19 (2001), 281–292.
[10]	Z.-Z. Bai, L.-L. Zhang, Modulus-based synchronous multisplitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 20 (2012), 425–439. https://doi.org/10.1007/s11075-012-9566-x doi: 10.1007/s11075-012-9566-x
[11]	Z.-Z. Bai, L.-L. Zhang, Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems, Numer. Algorithms, 62 (2013), 59–77. https://doi.org/10.1007/s11075-012-9566-x doi: 10.1007/s11075-012-9566-x
[12]	Z.-Z. Bai, D. J. Evans, Matrix multisplitting methods with applications to linear complementarity problems: Parallel synchronous and chaotic methods, Calculateurs Paralleles Reseaux et systemes repartis, 13 (2001), 125–141.
[13]	Z.-Z. Bai, D. J. Evans, Matrix multisplitting methods with applications to linear complementarity problems: parallel asynchronous methods, Int. J. Comput. Math., 79 (2002), 205–232. https://doi.org/10.1080/00207160211927 doi: 10.1080/00207160211927
[14]	Z.-Z. Bai, Modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 17 (2010), 917–933. https://doi.org/10.1002/nla.680 doi: 10.1002/nla.680
[15]	L.-L. Zhang, Z.-R. Ren, Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems, Appl. Math. Lett., 26 (2013), 638–642. https://doi.org/10.1016/j.aml.2013.01.001 doi: 10.1016/j.aml.2013.01.001
[16]	C. Kanzow, Inexact semismooth Newton methods for large-scale complementarity problems, Optim. Methods Softw., 19 (2004), 309–325. https://doi.org/10.1080/10556780310001636369 doi: 10.1080/10556780310001636369
[17]	Z. Sun, J.-P. Zeng, A monotone semismooth Newton type method for a class of complementarity problems, J. Comput. Appl. Math., 235 (2011), 1261–1274. https://doi.org/10.1016/j.cam.2010.08.012 doi: 10.1016/j.cam.2010.08.012
[18]	Z.-Z. Bai, L.-L. Zhang, Modulus-based multigrid methods for linear complementarity problems, Numer. Linear Algebra Appl., 24 (2017), e2105. https://doi.org/10.1002/nla.2105 doi: 10.1002/nla.2105
[19]	Z.-G. Huang, J.-J. Cui, Accelerated relaxation modulus-based matrix splitting iteration method for linear complementarity problems, Bull. Malays. Math. Sci. Soc., 44 (2021), 2175–2213. https://doi.org/10.1007/s40840-020-01049-9 doi: 10.1007/s40840-020-01049-9
[20]	D.-K. Li, L. Wang, Y.-Y. Liu, A relaxation general two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems, J. Comput. Appl. Math., 409 (2022), 114140. https://doi.org/10.1016/j.cam.2022.114140 doi: 10.1016/j.cam.2022.114140
[21]	X.-F. Peng, M. Wang, W. Li, A relaxation two-sweep modulus-based matrix splitting iteration method for linear complementarity problems, East Asian J. Appl. Math., 9 (2019), 102–121. https://doi.org/10.4208/eajam.020318.220618 doi: 10.4208/eajam.020318.220618
[22]	H. Ren, X. Wang, X.-B. Tang, T. Wang, The general two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems, Comput. Math. Appl., 77 (2018), 1–11. https://doi.org/10.1016/j.camwa.2018.10.040 doi: 10.1016/j.camwa.2018.10.040
[23]	S.-L. Wu, C.-X. Li, P. Agarwal, Relaxed modulus-based matrix splitting methods for the linear complementarity problem, Symmetry, 13 (2021), 503. https://doi.org/10.3390/sym13030503 doi: 10.3390/sym13030503
[24]	B.-H. Huang, C.-F. Ma, Accelerated modulus-based matrix splitting iteration method for a class of nonlinear complementarity problems, Comp. Appl. Math., 37 (2018), 3053–3076. https://doi.org/10.1007/s40314-017-0496-z doi: 10.1007/s40314-017-0496-z
[25]	S.-L. Xie, H.-R. Xu, J.-P. Zeng, Two-step modulus-based matrix splitting iteration method for a class of nonlinear complementarity problems, Linear Algebra Appl., 494 (2016), 1–10. https://doi.org/10.1016/j.laa.2016.01.002 doi: 10.1016/j.laa.2016.01.002
[26]	H. Zheng, S. Vong, L. Liu, The relaxation modulus-based matrix splitting iteration method for solving a class of nonlinear complementarity problems, Int. J. Comput. Math., 96 (2019), 1648–1667. https://doi.org/10.1080/00207160.2018.1504928 doi: 10.1080/00207160.2018.1504928
[27]	H. Zheng, S. Vong, A two-step modulus-based matrix splitting iteration method for horizontal linear complementarity problems, Numer. Algorithms, 86 (2021), 1791–1810. https://doi.org/10.1007/s11075-020-00954-1 doi: 10.1007/s11075-020-00954-1
[28]	Y. Cao, A. Wang, Two-step modulus-based matrix splitting iteration methods for implicit complementarity problems, Numer. Algorithms, 82 (2019), 1377–1394. https://doi.org/10.1007/s11075-019-00660-7 doi: 10.1007/s11075-019-00660-7
[29]	J. Lu, W. Xiang, A generalized two-step modulus-based matrix splitting iteration method for implicit complementarity problems of $H_+$-matrices, Filomat, 33 (2019), 4875–4888. https://doi.org/10.2298/fil1915875j doi: 10.2298/fil1915875j
[30]	Y. Wang, J.-F. Yin, Q.-Y. Dou, R. Li, Two-step modulus-based matrix splitting iteration methods for a class of implicit complementarity problems, Numer. Math. Theor. Meth. Appl., 12 (2019), 867–883. https://doi.org/10.4208/nmtma.oa-2018-0034 doi: 10.4208/nmtma.oa-2018-0034
[31]	Y.-F. Ke, C.-F. Ma, H. Zhang, The modulus-based matrix splitting iteration methods for second-order cone linear complementarity problems, Numer. Algorithms, 79 (2018), 1283–1303. https://doi.org/10.1007/s11075-018-0484-4 doi: 10.1007/s11075-018-0484-4
[32]	Y.-F. Ke, C.-F. Ma, H. Zhang, The relaxation modulus-based matrix splitting iteration methods for circular cone nonlinear complementarity problems, J. Comput. Appl. Math., 37 (2018), 6795–6820. https://doi.org/10.1007/s40314-018-0687-2 doi: 10.1007/s40314-018-0687-2
[33]	Y.-F. Ke, Convergence analysis on matrix splitting iteration algorithm for semidefinite linear complementarity problems, Numer. Algorithms, 86 (2021), 257–279. https://doi.org/10.1007/s11075-020-00888-8 doi: 10.1007/s11075-020-00888-8
[34]	S.-L. Wu, C.-X. Li, A class of new modulus-based matrix splitting methods for linear complementarity problem, Optim. Lett., 16 (2022), 1427–1443. https://doi.org/10.1007/s11590-021-01781-6 doi: 10.1007/s11590-021-01781-6
[35]	W. Li, H. Zheng, A preconditioned modulus-based iteration method for solving linear complementarity problems of $H$-matrices, Linear Multilinear Algebra, 64 (2016), 1390–1403. https://doi.org/10.1080/03081087.2015.1087457 doi: 10.1080/03081087.2015.1087457
[36]	H. Zheng, J. Luo, A preconditioned two-step modulus-based matrix splitting iteration method for linear complementarity problems of $H$-matrices, Math. Numer. Sin., 40 (2018), 24–32. (in Chinese)
[37]	H. Ren, X. Wang, X.-B. Tang, T. Wang, A preconditioned general two-step modulus-based matrix splitting iteration method for linear complementarity problems of $H_+$-matrices, Numer. Algorithms, 82 (2019), 969–986. https://doi.org/10.1007/s11075-018-0637-5 doi: 10.1007/s11075-018-0637-5
[38]	L.-L. Zhang, Two-step modulus-based matrix splitting iteration method for linear complementarity problems, Numer. Algorithms, 57 (2011), 83–99. https://doi.org/10.1007/s11075-010-9416-7 doi: 10.1007/s11075-010-9416-7
[39]	X.-P. Wu, X.-F. Peng, W. Li, A preconditioned general modulus-based matrix splitting iteration method for linear complementarity problems of $H$-matrices, Numer. Algorithms, 79 (2018), 1131–1146. https://doi.org/10.1007/s11075-018-0477-3 doi: 10.1007/s11075-018-0477-3
[40]	P.-F. Dai, J.-C. Li, J.-C. Bai, J.-M. Qiu, A preconditioned two-step modulus-based matrix splitting iteration method for linear complementarity problem, Appl. Math. Comput., 348 (2019), 542–551. https://doi.org/10.1016/j.amc.2018.12.012 doi: 10.1016/j.amc.2018.12.012
[41]	Z.-Z. Bai, J.-Y. Pan, Matrix Analysis and Computations, Philadelphia(PA): SIAM, 2021. https://doi.org/10.1137/1.9781611976632
[42]	R. S. Varga, Matrix Iterative Analysis, $2^{nd}$ edition, Springer Berlin, Heidelberg, 1962. https://doi.org/10.1007/978-3-642-05156-2
[43]	A. Frommer, G. Mayer, Convergence of relaxed parallel multisplitting methods, Linear Algebra Appl., 119 (1989), 141–152. https://doi.org/10.1016/0024-3795(89)90074-8 doi: 10.1016/0024-3795(89)90074-8
[44]	A. Berman, R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Philadelphia(PA): SIAM, 1994. https://doi.org/10.1137/1.9781611971262
[45]	O. Axelsson, Iterative Solution Methods, Cambridge University Press, 1996.
[46]	M. Neumann, R. J. Plemmons, Convergence of parallel multisplitting iterative methods for $M$-matrices, Linear Algebra Appl., 88–89 (1987), 559–573. https://doi.org/10.1016/0024-3795(87)90125-x doi: 10.1016/0024-3795(87)90125-x
[47]	L. Wang, Y.-Z. Song, Preconditioned AOR iterative methods for $M$-matrices, J. Comput. Appl. Math., 226 (2009), 114–124. https://doi.org/10.1016/j.cam.2008.05.022 doi: 10.1016/j.cam.2008.05.022
[48]	P.-F. Dai, J.-C. Li, J.-C. Bai, A preconditioned accelerated modulus-based Gauss-Seidel iterative method for linear complementarity problems, Math. Numer. Sin., 41 (2019), 308–319. (in Chinese)
[49]	G. Isac, Complementarity Problems and Variational Inequalities, Springer, Boston, MA, 2006. https://doi.org/10.1007/0-387-32900-5-2
[50]	X.-J. Shi, L. Yang, Z.-H. Huang, A fixed point method for the linear complementarity problem arising from american option pricing, Acta Math. Appl. Sin. Engl. Ser., 32 (2016), 921–932. https://doi.org/10.1007/s10255-016-0613-6 doi: 10.1007/s10255-016-0613-6

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)