Research article

A new relaxed acceleration two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems

  • Received: 26 January 2023 Revised: 13 March 2023 Accepted: 15 March 2023 Published: 06 April 2023
  • MSC : 65F10, 65H10, 90C30

  • A new relaxed acceleration two-sweep modulus-based matrix splitting (NRATMMS) iteration method is developed to solve linear complementarity problems. The convergence of the NRATMMS method is established with the system matrix $ A $ being an $ H_{+} $-matrix. Numerical experiments show that the proposed method is superior to some existing algorithms under appropriate conditions.

    Citation: Dongmei Yu, Yiming Zhang, Cairong Chen, Deren Han. A new relaxed acceleration two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems[J]. AIMS Mathematics, 2023, 8(6): 13368-13389. doi: 10.3934/math.2023677

    Related Papers:

  • A new relaxed acceleration two-sweep modulus-based matrix splitting (NRATMMS) iteration method is developed to solve linear complementarity problems. The convergence of the NRATMMS method is established with the system matrix $ A $ being an $ H_{+} $-matrix. Numerical experiments show that the proposed method is superior to some existing algorithms under appropriate conditions.



    加载中


    [1] R. W. Cottle, J. S. Pang, R. E. Stone, The linear complementarity problem, San Diego: Academic Press, 1992. http://doi.org/10.1137/1.9780898719000
    [2] K. G. Murty, Linear complementarity, linear and nonlinear programming, Berlin: Heldermann, 1988.
    [3] U. Schäfer, A linear complementarity problem with a $P$-matrix, SIAM Rev., 46 (2004), 189–201. http://dx.doi.org/10.1137/S0036144502420083 doi: 10.1137/S0036144502420083
    [4] N. W. Kappel, L. T. Watson, Iterative algorithms for the linear complementarity problem, Int. J. Comput. Math., 19 (1986), 273–297. http://dx.doi.org/10.1080/00207168608803522 doi: 10.1080/00207168608803522
    [5] Z. Z. Bai, On the monotone convergence of the projected iteration methods for linear complementarity problem, Numer. Math. J. Chinese Univ. (English Ser.), 5 (1996), 228–233.
    [6] Y. Li, P. Dai, Generalized AOR methods for linear complementarity problem, Appl. Math. Comput., 188 (2007), 7–18. http://dx.doi.org/10.1016/j.amc.2006.09.067 doi: 10.1016/j.amc.2006.09.067
    [7] O. L. Mangasarian, Solution of symmetric linear complementarity problems by iterative methods, J. Optim. Theory Appl., 22 (1977), 465–485. http://dx.doi.org/10.1007/BF01268170 doi: 10.1007/BF01268170
    [8] H. S. 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. http://dx.doi.org/10.1007/s10957-012-0135-1 doi: 10.1007/s10957-012-0135-1
    [9] 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://dx.doi.org/10.1137/S0895479897324032 doi: 10.1137/S0895479897324032
    [10] Z. Z. Bai, Parallel chaotic multisplitting iterative methods for the large sparse linear complementarity problem, J. Comput. Math., 19 (2001), 281–292.
    [11] Z. Z. Bai, L. L. Zhang, Modulus-based synchronous multisplitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 20 (2013), 425–439. https://dx.doi.org/10.1002/nla.1835 doi: 10.1002/nla.1835
    [12] 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://dx.doi.org/10.1080/00207160211927 doi: 10.1080/00207160211927
    [13] 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://dx.doi.org/10.1007/s11075-012-9566-x doi: 10.1007/s11075-012-9566-x
    [14] N. Machida, M. Fukushima, T. Ibaraki, A multisplitting method for symmetric linear complementarity problems, J. Comput. Appl. Math., 62 (1995), 217–227. http://dx.doi.org/10.1016/0377-0427(94)00103-2 doi: 10.1016/0377-0427(94)00103-2
    [15] C. Kanzow, Inexact semismooth Newton methods for large-scale complementarity problems, Optim. Methods Softw., 19 (2004), 309–325. http://dx.doi.org/10.1080/10556780310001636369 doi: 10.1080/10556780310001636369
    [16] 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. http://dx.doi.org/10.1016/j.cam.2010.08.012 doi: 10.1016/j.cam.2010.08.012
    [17] Z. Z. Bai, L. L. Zhang, Modulus-based multigrid methods for linear complementarity problems, Numer. Linear Algebra Appl., 24 (2017), e2105. https://dx.doi.org/10.1002/nla.2105 doi: 10.1002/nla.2105
    [18] L. Jia, X. Wang, X. Y. Xiao, The nonlinear lopsided HSS-like modulus-based matrix splitting iteration method for linear complementarity problems with positive-definite matrices, Commun. Appl. Math. Comput., 3 (2021), 109–122. http://dx.doi.org/10.1007/s42967-019-00038-5 doi: 10.1007/s42967-019-00038-5
    [19] L. L. Zhang, Two-stage multisplitting iteration methods using modulus-based matrix splitting as inner iteration for linear complementarity problems, J. Optim. Theory Appl., 160 (2014), 189–203. http://dx.doi.org/10.1007/s10957-013-0362-0 doi: 10.1007/s10957-013-0362-0
    [20] Z. Z. Bai, Modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 17 (2010), 917–933. https://dx.doi.org/10.1002/nla.680 doi: 10.1002/nla.680
    [21] A. Hadjidimos, M. Tzoumas, Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem, Linear Algebra Appl., 431 (2009), 197–210. http://dx.doi.org/10.1016/j.laa.2009.02.024 doi: 10.1016/j.laa.2009.02.024
    [22] J. L. Dong, M. Q. Jiang, A modified modulus method for symmetric positive-definite linear complementarity problems, Numer. Linear Algebra Appl., 16 (2009), 129–143. http://dx.doi.org/10.1002/nla.609 doi: 10.1002/nla.609
    [23] N. Zheng, J. F. Yin, Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem, Numer. Algorithms, 64 (2013), 245–262. http://dx.doi.org/10.1007/s11075-012-9664-9 doi: 10.1007/s11075-012-9664-9
    [24] H. Zheng, W. Li, S. Vong, A relaxation modulus-based matrix splitting iteration method for solving linear complementarity problems, Numer. Algorithms, 74 (2016), 137–152. http://dx.doi.org/10.1007/s11075-016-0142-7 doi: 10.1007/s11075-016-0142-7
    [25] W. Li, A general modulus-based matrix splitting method for linear complementarity problems of $H$-matrices, Appl. Math. Lett., 26 (2013), 1159–1164. http://dx.doi.org/10.1016/j.aml.2013.06.015 doi: 10.1016/j.aml.2013.06.015
    [26] S. Q. Shen, T. Z. Huang, Convergence and comparison theorems for double splittings of matrices, Comput. Math. Appl., 51 (2006), 1751–1760. http://dx.doi.org/10.1016/j.camwa.2006.02.006 doi: 10.1016/j.camwa.2006.02.006
    [27] Z. I. Woźnicki, Estimation of the optimum relaxation factors in partial factorization iterative methods, SIAM J. Matrix Anal. Appl., 14 (1993), 59–73. http://dx.doi.org/10.1137/0614005 doi: 10.1137/0614005
    [28] S. L. Wu, C. X. Li, Two-sweep modulus-based matrix splitting iteration methods for linear complementarity problems, J. Comput. Appl. Math., 302 (2016), 327–339. http://dx.doi.org/10.1016/j.cam.2016.02.011 doi: 10.1016/j.cam.2016.02.011
    [29] 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 (2019), 1071–1081. http://dx.doi.org/10.1016/j.camwa.2018.10.040 doi: 10.1016/j.camwa.2018.10.040
    [30] X. 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. http://dx.doi.org/10.4208/eajam.020318.220618 doi: 10.4208/eajam.020318.220618
    [31] 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. http://dx.doi.org/10.1007/s40840-020-01049-9 doi: 10.1007/s40840-020-01049-9
    [32] P. F. Dai, J. Li, J. Bai, J. Qiu, A preconditioned two-step modulus-based matrix splitting iteration method for linear complementarity problem, Appl. Math. Comput., 348 (2019), 542–551. http://dx.doi.org/10.1016/j.amc.2018.12.012 doi: 10.1016/j.amc.2018.12.012
    [33] B. Huang, C. Ma, Accelerated modulus-based matrix splitting iteration method for a class of nonlinear complementarity problems, Comput. Appl. Math., 37 (2018), 3053–3076. http://dx.doi.org/10.1007/s40314-017-0496-z doi: 10.1007/s40314-017-0496-z
    [34] N. Li, J. Ding, J. F. Yin, Modified relaxation two-sweep modulus-based matrix splitting iteration method for solving a class of implicit complementarity problems, J. Comput. Appl. Math., 413 (2022), 114370. http://dx.doi.org/10.1016/j.cam.2022.114370 doi: 10.1016/j.cam.2022.114370
    [35] S. Liu, H. Zheng, W. Li, A general accelerated modulus-based matrix splitting iteration method for solving linear complementarity problems, Calcolo, 53 (2015), 189–199. http://dx.doi.org/10.1007/s10092-015-0143-2 doi: 10.1007/s10092-015-0143-2
    [36] F. Mezzadri, On the equivalence between some projected and modulus-based splitting methods for linear complementarity problems, Calcolo, 56 (2019), 41. http://dx.doi.org/10.1007/s10092-019-0337-0 doi: 10.1007/s10092-019-0337-0
    [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. http://dx.doi.org/10.1007/s11075-018-0637-5 doi: 10.1007/s11075-018-0637-5
    [38] Y. J. Wu, W. H. Zhang, A. L. Yang, Modulus-based inexact non-alternating preconditioned splitting method for linear complementarity problems, Linear Multilinear Algebra, in press. http://dx.doi.org/10.1080/03081087.2021.1991874
    [39] L. L. Zhang, Two-step modulus-based matrix splitting iteration method for linear complementarity problems, Numer. Algorithms, 57 (2011), 83–99. http://dx.doi.org/10.1007/s11075-010-9416-7 doi: 10.1007/s11075-010-9416-7
    [40] 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. http://dx.doi.org/10.1016/j.aml.2013.01.001 doi: 10.1016/j.aml.2013.01.001
    [41] N. Zheng, J. F. Yin, Convergence of accelerated modulus-based matrix splitting iteration methods for linear complementarity problem with an $H_+$-matrix, J. Comput. Appl. Math., 260 (2014), 281–293. http://dx.doi.org/10.1016/j.cam.2013.09.079 doi: 10.1016/j.cam.2013.09.079
    [42] Z. Z. Bai, P. L. Tong, Iterative methods for linear complementarity problem, J. UEST China, 22 (1993), 420–424.
    [43] Z. Z. Bai, T. Z. Huang, Accelerated overrelaxation methods for solving linear complementarity problem, J. UEST China, 23 (1994), 428–432.
    [44] 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. http://dx.doi.org/10.1007/s11590-021-01781-6 doi: 10.1007/s11590-021-01781-6
    [45] A. Frommer, D. B. Szyld, H-splittings and two-stage iterative methods, Numer. Math., 63 (1992), 345–356. http://dx.doi.org/10.1007/BF01385865 doi: 10.1007/BF01385865
    [46] Z. Z. Bai, D. J. Evans, Matrix multisplitting relaxation methods for linear complementarity problems, Int. J. Comput. Math., 63 (1997), 309–326. https://dx.doi.org/10.1080/00207169708804569 doi: 10.1080/00207169708804569
    [47] J. G. Hu, Estimates of $\|B^{-1}A\|_{\infty}$ and their applications, Math. Numer. Sin., 3 (1982), 272–282.
    [48] A. Frommer, G. Mayer, Convergence of relaxed parallel multisplitting methods, Linear Algebra Appl., 119 (1989), 141–152. http://dx.doi.org/10.1016/0024-3795(89)90074-8 doi: 10.1016/0024-3795(89)90074-8
    [49] A. Berman, R. J. Plemmons, Nonnegative matrices in the mathematical sciences, Philadelphia: SIAM, 1994. http://dx.doi.org/10.1137/1.9781611971262
    [50] X. J. Shi, Y. Lei, 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. http://dx.doi.org/10.1007/s10255-016-0613-6 doi: 10.1007/s10255-016-0613-6
  • Reader Comments
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(869) PDF downloads(74) Cited by(0)

Article outline

Figures and Tables

Tables(3)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog