[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Scalable Relaxation Two-Sweep Modulus-Based Matrix Splitting Methods for Vertical LCP

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

Based on a new equivalent reformulation, a scalable modulus-based matrix splitting (SMMS) method is proposed to solve the vertical linear complementarity problem (VLCP). By introducing a relaxation parameter and employing the two-sweep technique, we further enhance the scalability of the method, leading to a framework of the scalable relaxation two-sweep modulus-based matrix splitting (SRTMMS) method. To theoretically demonstrate the acceleration of the convergence provided by the SMMS method, we present a comparison theorem for the case of \(s=2\). Furthermore, we establish the convergence of the SRTMMS method for arbitrary s. Preliminary numerical results indicate promising performance of the SRTMMS method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Axelsson, O.: Iterative Solution Methods. Cambridge University Press, Cambridge (1996)

    Google Scholar 

  2. Bai, Z.Z., Evans, D.J.: Matrix multisplitting relaxation methods for linear complementarity problems. Int. J. Comput. Math. 63, 309–326 (1997)

    Article  MathSciNet  Google Scholar 

  3. Bai, Z.Z.: Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 17, 917–933 (2010)

    Article  MathSciNet  Google Scholar 

  4. Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences. SIAM, Philadelphia (1994)

    Book  Google Scholar 

  5. Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, San Diego (1992)

  6. Dai, P.F., Li, J.C., Bai, J.C., Qi, J.M.: A preconditioned two-step modulus-based matrix splitting iteration method for linear complementarity problem. Appl. Math. Comput. 348, 542–551 (2019)

    MathSciNet  Google Scholar 

  7. Ebiefung, A.A.: Nonlinear mappings associated with the generalized linear complementarity problem. Math. Program. 69, 255–268 (1995)

    Article  MathSciNet  Google Scholar 

  8. Ebiefung, A.A.: The vertical linear complementarity problem associated with \(P_0\)-matrices. Optim. Methods Softw. 10, 747–761 (1999)

    Article  MathSciNet  Google Scholar 

  9. Frommer, A., Mayer, G.: Convergence of relaxed parallel multisplitting methods. Linear Algebra Appl. 119, 141–152 (1989)

    Article  MathSciNet  Google Scholar 

  10. Frommer, A., Szyld, D.B.: \(H\)-splittings and two-stage iterative methods. Numer. Math. 63, 345–356 (1992)

    Article  MathSciNet  Google Scholar 

  11. Guo, W.X., Zheng, H., Peng, X.F.: New convergence results of the modulus-based methods for vertical linear complementarity problems. Appl. Math. Lett. 135, 108444 (2023)

    Article  MathSciNet  Google Scholar 

  12. He, J.W., Vong, S.: A new kind of modulus-based matrix splitting methods for vertical linear complementarity problems. Appl. Math. Lett. 134, 108344 (2022)

    Article  MathSciNet  Google Scholar 

  13. Hong, J.T., Li, C.L.: Modulus-based matrix splitting iteration methods for a class of implicit complementarity problems. Numer. Linear Algebra Appl. 23, 629–641 (2016)

    Article  MathSciNet  Google Scholar 

  14. Hu, J.G.: Estimates of \(\Vert B^{-1}C\Vert _\infty \) and their applications. Math. Numer. Sin. 3, 272–282 (1982)

    Google Scholar 

  15. Huang, N., Ma, C.F.: The modulus-based matrix splitting algorithms for a class of weakly nonlinear complementarity problems. Numer. Linear Algebra Appl. 23, 558–569 (2016)

    Article  MathSciNet  Google Scholar 

  16. Mohan, S.R., Neogy, S.K.: Algorithms for the generalized linear complementarity problem with a vertical block \(Z\)-matrix. SIAM J. Optim. 6, 994–1006 (1996)

    Article  MathSciNet  Google Scholar 

  17. Mohan, S.R., Neogy, S.K.: Vertical block hidden \(Z\)-matrices and the generalized linear complementarity problem. SIAM J. Matrix Anal. Appl. 18, 181–190 (1997)

    Article  MathSciNet  Google Scholar 

  18. Mohan, S.R., Neogy, S.K., Sridhar, R.: The generalized linear complementarity problem revisited. Math. Program. 74, 197–218 (1996)

    Article  MathSciNet  Google Scholar 

  19. Mezzadri, F.: A modulus-based formulation for the vertical linear complementarity problem. Numer. Algorithms 90, 1547–1568 (2022)

    Article  MathSciNet  Google Scholar 

  20. Mezzadri, F., Galligani, E.: A generalization of irreducibility and diagonal dominance with applications to horizontal and vertical linear complementarity problems. Linear Algebra Appl. 621, 214–234 (2021)

    Article  MathSciNet  Google Scholar 

  21. Mezzadri, F., Galligani, E.: Modulus-based matrix splitting methods for horizontal linear complementarity problems. Numer. Algorithms 83, 201–219 (2020)

    Article  MathSciNet  Google Scholar 

  22. Nagae, T., Akamatsu, T.: A generalized complementarity approach to solving real option problems. J. Econom. Dynam. Control 32, 1754–1779 (2008)

    Article  MathSciNet  Google Scholar 

  23. Neumann, M., Plemmons, R.J.: Convergence of parallel multisplitting iterative methods for M-matrices. Linear Algebra Appl. 88–89, 559–573 (1987)

    Article  MathSciNet  Google Scholar 

  24. Ortega, J.M., Rheinboldt, W.C.: Monotone iterations for nonlinear equations with applications to Gauss-Seidel methods. SIAM J. Numer. Anal. 4, 171–196 (1967)

    Article  MathSciNet  Google Scholar 

  25. Peng, J.M., Lin, Z.H.: A non-interior continuation method for generalized linear complementarity problems. Math. Program. 86, 533–563 (1999)

    Article  MathSciNet  Google Scholar 

  26. Shen, S.Q., Huang, T.Z.: Convergence and comparison theorems for double splittings of matrices. Comput. Math. Appl. 51, 1751–1760 (2006)

    Article  MathSciNet  Google Scholar 

  27. Song, Y.L., Zheng, H., Lu, X.P., Vong, S.: A two-step iteration method for vertical linear complementarity problems. Symmetry 14, 1882 (2022)

    Article  Google Scholar 

  28. Sun, M.: Monotonicity of Mangasarian’s iterative algorithm for generalized linear complementarity problems. J. Math. Anal. Appl. 144, 474–485 (1989)

    Article  MathSciNet  Google Scholar 

  29. Sznajder, R., Gowda, M.S.: Generalizations of \(P_0\)-and \(P\)-properties; extended vertical and horizontal linear complementarity problems. Linear Algebra Appl. 223–224, 695–715 (1995)

    Article  Google Scholar 

  30. Wang, D., Li, J.C.: Relaxation modulus-based matrix splitting iteration method for vertical linear complementarity problem. J. Comput. Appl. Math. 437, 115430 (2024)

    Article  MathSciNet  Google Scholar 

  31. Wang, L., Song, Y.Z.: Preconditioned AOR iterative methods for \(M\)-matrices. J. Comput. Appl. Math. 226, 114–124 (2009)

    Article  MathSciNet  Google Scholar 

  32. Wu, S.L., Li, C.X.: Two-sweep modulus-based matrix splitting iteration methods for linear complementarity problems. J. Comput. Appl. Math. 302, 327–339 (2016)

    Article  MathSciNet  Google Scholar 

  33. Wu, S.L., Li, C.X.: A class of new modulus-based matrix splitting methods for linear complementarity problem. Optim. Lett. 16, 1427–1443 (2022)

    Article  MathSciNet  Google Scholar 

  34. Xia, Z.C., Li, C.L.: Modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problem. Appl. Math. Comput. 271, 34–42 (2015)

    MathSciNet  Google Scholar 

  35. Yang, C., Wang, A.: Two-step modulus-based matrix splitting iteration methods for implicit complementarity problems. Numer. Algorithms 82, 1377–1394 (2019)

    Article  MathSciNet  Google Scholar 

  36. Yu, D.M., Zhang, Y.M., Chen, C.R., Han, D.R.: A new relaxed acceleration two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems. AIMS Math. 8, 13368–13389 (2023)

    Article  MathSciNet  Google Scholar 

  37. Zhang, L.P., Gao, Z.Y.: Global linear and quadratic one-step smoothing newton method for vertical linear complementarity problems. Appl. Math. Mech. 24, 738–746 (2003)

    Article  MathSciNet  Google Scholar 

  38. Zheng, H., Vong, S.: A modified modulus-based matrix splitting iteration method for solving implicit complementarity problems. Numer. Algorithms 82, 573–592 (2019)

    Article  MathSciNet  Google Scholar 

  39. Zheng, H., Li, W., Vong, S.: A relaxation modulus-based matrix splitting iteration method for solving linear complementarity problems. Numer. Algorithms 74, 137–152 (2016)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work was partially supported by the Ministry of Science and Technology of China (No. 2021YFA1003600). D. Yu was partially supported by the National Natural Science Foundation of China (No. 12201275), the Natural Science Foundation of Liaoning Province (No. 2024-MS-206), the Ministry of Education in China of Humanities and Social Science Project (No. 21YJCZH204) and the Liaoning Provincial Department of Education (No. JYTZD2023072). C. Chen was partially supported by the Natural Science Foundation of Fujian Province (No. 2021J01661) and the Fujian Alliance of Mathematics (No. 2023SXLMQN03). D. Han was partially supported by the National Natural Science Foundation of China (Nos. 12126603 and 12131004). The authors are grateful to the reviewers and the editor for their helpful comments and suggestions that have helped to improve the paper.

Author information

Authors and Affiliations

  1. Institute for Optimization and Decision Analytics & College of Science, Liaoning Technical University, Fuxin, 123000, People’s Republic of China

    Dongmei Yu & Huiling Wei

  2. School of Mathematics and Statistics & Key Laboratory of Analytical Mathematics and Applications (Ministry of Education) & Fujian Provincial Key Laboratory of Statistics and Artificial Intelligence, Fujian Normal University, Fuzhou, 350117, People’s Republic of China

    Cairong Chen

  3. LMIB of the Ministry of Education, School of Mathematical Sciences, Beihang University, Beijing, 100191, People’s Republic of China

    Deren Han

Authors
  1. Dongmei Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Huiling Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Cairong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Deren Han
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Cairong Chen.

Additional information

Communicated by Tibor Illés.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yu, D., Wei, H., Chen, C. et al. Scalable Relaxation Two-Sweep Modulus-Based Matrix Splitting Methods for Vertical LCP. J Optim Theory Appl 203, 714–744 (2024). https://doi.org/10.1007/s10957-024-02529-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-024-02529-9

Keywords

Mathematics Subject Classification

Search

Navigation