A generalized modulus-based Newton method for solving a class of non-linear complementarity problems with P-matrices | Numerical Algorithms Skip to main content
Springer Nature Link
Log in

A generalized modulus-based Newton method for solving a class of non-linear complementarity problems with P-matrices

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

Motivated by the modulus-based Newton method for solving linear complementarity problems (Zheng and Li, J. Comput. Appl. Math. 288, 116–126 2015; Wu and Li, Calcolo 54, 43–56 2017), we propose a generalized modulus-based Newton method to solve a class of non-linear complementarity problems with P-matrices. A sufficient condition to guarantee the convergence of the proposed method is obtained. Numerical experiments further demonstrate that the proposed method is efficient and has better performance than the existing modulus-based iteration method and the Newton 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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Zheng, H., Li, W.: The modulus-based nonsmooth Newton’s method for solving linear complementarity problems. J. Comput. Appl. Math. 288, 116–126 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  2. Wu, S.-L., Li, C.-X.: A generalized Newton method for non-Hermitian positive definite linear complementarity problem. Calcolo 54, 43–56 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  3. Ortega, J.M., Rheinboldt, W.C.: Iterative solution of nonlinear equations in several variables. Academic, New York (1970)

    MATH  Google Scholar 

  4. Bai, Z.-Z.: Parallel nonlinear AOR method and its convergence. Comput. Math. Appl. 31, 21–31 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  5. Ferris, M.C., Pang, J.-S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669–713 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  6. Facchinei, F., Pang, J.-S.: Finite-dimensional variational inequalities and complementarity problems. Springer, New York (2003)

    MATH  Google Scholar 

  7. Cottle, R.W., Pang, J.-S., Stone, R.E.: The linear complementarity problem. Academic, San Diego (2009)

    Book  MATH  Google Scholar 

  8. Cryer, C.W.: The solution of a quadratic programming problem using systematic overrelaxation. SIAM J. Control Optim. 9, 385–392 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bai, Z.-Z.: On the monotone convergence of the projected iteration methods for linear complementarity problems. Numer. Math. J. Chinese Univ. (English Ser.) 5, 228–233 (1996)

    MathSciNet  MATH  Google Scholar 

  10. Hadjidimos, A., Tzoumas, M.: On the solution of the linear complementarity problem by the generalized accelerated overrelaxation iterative method. J. Optim. Theory Appl. 165, 545–562 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  11. Bai, Z.-Z., Wang, D.-R.: A class of parallel nonlinear multisplitting relaxation methods for the large sparse nonlinear complementarity problems. Comput. Math. Appl. 32, 79–95 (1996)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  13. Bai, Z.-Z.: On the convergence of the multisplitting methods for the linear complementarity problem. SIAM. J. Matrix Anal. Appl. 21, 67–78 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  14. Jiang, Y.-J., Zeng, J.-P.: A multiplicative Schwarz algorithm for the nonlinear complementarity problem with an M-function. B. Aust. Math. Soc. 28, 353–366 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  15. Kanzow, C.: Inexact semismooth Newton methods for large-scale complementarity problems. Optim. Method Softw. 19, 309–325 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  16. Sun, Z., Zeng, J.-P.: A monotone semismooth Newton type method for a class of complementarity problems. J. Comput. Appl. Math. 235, 1261–1274 (2011)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. van Bokhoven, W.M.G.: Piecewise-linear modelling and analysis. Proeschrift, Eindhoven (1981)

    Google Scholar 

  19. Dong, J.-L., Jiang, M.-Q.: A modified modulus method for symmetric positive-definite linear complementarity problems. Numer. Linear Algebra Appl. 16, 129–143 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  20. Hadjidimos, A., Tzoumas, M.: Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem. Linear Algebra Appl. 431, 197–210 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Zhang, L.-L., Ren, Z.-R.: Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems. Appl. Math. Lett. 26, 638–642 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  22. Zhang, L.-L.: Two-step modulus-based matrix splitting iteration method for linear complementarity problems. Numer. Algorithms. 57, 83–99 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  23. Zheng, N., Yin, J.-F.: Accelerated modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Algorithms. 64, 245–261 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  24. Zheng, N., Yin, J.-F.: Convergence of accelerated modulus-based matrix splitting iteration methods for linear complementarity problem with an h+-matrix. J. Comput. Appl. Math. 260, 281–293 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  25. Li, W.: A general modulus-based matrix splitting method for linear complementarity problems of H-matrices. Appl. Math. Lett. 26, 1159–1164 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Xu, W.-W., Liu, H.: A modified general modulus-based matrix splitting method for linear complementarity problems with H-matrices. Linear Algebra Appl. 458, 626–637 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  27. Xu, W.-W.: Modified modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 22, 748–760 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  28. Bai, Z.-Z., Zhang, L.-L.: Modulus-based synchronous multisplitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 20, 425–439 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  29. Zhang, L.-L., Zhang, Y.-P., Ren, Z.-R.: New convergence proofs of modulus-based synchronous multisplitting iteration methods for linear complementarity problems. Linear Algebra Appl. 481, 83–93 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  30. Bai, Z.-Z., Zhang, L.-L.: Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems. Numer. Algorithms. 62, 59–77 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  31. Zhang, L.-T., Li, J.-L.: The weaker convergence of modulus-based synchronous multisplitting multi-parameters methods for linear complementarity problems. Comput. Math. Appl. 67, 1954–1959 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  32. Zhang, L.-L.: Two-step modulus-based synchronous multisplitting iteration methods for linear complementarity problems. J. Comput. Math. 33, 100–112 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  33. 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  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  35. Li, R., Yin, J.-F.: On the convergence of modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problems with h+-matrices. J. Comput. Appl. Math. 342, 202–209 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  36. Xie, S.-L., Xu, X.-R., Zeng, J.-P.: Two-step modulus-based matrix splitting iteration method for a class of nonlinear complementarity problems. Linear Algebra Appl. 494, 1–10 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  37. Li, R., Wang, Y., Yin, J.-F.: On the convergence of two-step modulus-based matrix splitting iteration methods for a restricted class of nonlinear complementarity problems with h+-matrices. Numer. Math.-Theory Me. 11, 128–139 (2018)

    MathSciNet  MATH  Google Scholar 

  38. Zheng, H., Liu, L.: A two-step modulus-based matrix splitting iteration method for solving nonlinear complementarity problems with h+-matrices. Comput. Appl. Math. 37, 5410–5423 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  39. Li, R., Yin, J.-F.: Accelerated modulus-based matrix splitting iteration methods for a class of restricted nonlinear complementarity problems. Numer. Algorithms. 75, 339–358 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  40. Huang, B.-H., Ma, C.-F.: Accelerated modulus-based matrix splitting iteration method for a class of nonlinear complementarity problems. Comput. Appl. Math. 37, 3053–3076 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  41. Zheng, H., Vong, S., Liu, L.: A direct preconditioned modulus-based iteration method for sovling nonlinear complementarity problems of H-matrices. Appl. Math. Comput. 353, 396–405 (2019)

    MathSciNet  MATH  Google Scholar 

  42. Zheng, H., Vong, S., Liu, L.: The relaxation modulus-based matrix splitting iteration method for sovling a class of nonlinear complementarity problems. Int. J. Comput. Math. 96, 1648–1667 (2019)

    Article  MathSciNet  Google Scholar 

  43. Wu, Y.-J., Yan, G.-L., Yang, A.-L.: Modulus-based synchronous multisplitting iteration methods for a restricted class of nonlinear complementarity problems. Numer. Math.-Theory Me. 12, 709–726 (2019)

    MathSciNet  MATH  Google Scholar 

  44. Zheng, H., Seakweng, V.: The modulus-based nonsmooth Newton’s method for solving a class of nonlinear complementarity problems of P-matrices. Calcolo 55, 1–17 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  45. Zheng, H., Liu, L.: The sign-based methods for solving a class of nonlinear complementarity problems. J. Optimiz. Theory Appl. 180, 480–499 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  46. Qi, L.-Q., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  47. Varga, R.S.: Matrix iterative analysis. Prentice-Hall, Englewood Cliffs (1962)

    MATH  Google Scholar 

  48. Berman, A., Plemmons, R.J.: Nonnegative matrices in the mathematical sciences. SIAM Publisher, Philadelphia (1994)

    Book  MATH  Google Scholar 

Download references

Acknowledgements

The authors are very indebted to the anonymous referees for their helpful comments and valuable suggestions, which have improved the presentation of this paper signicantly. This work is completed while the first author visited North Carolina State University.

Funding

This study is funded by the China Scholarship Council with file number being 201808330668 and the National Natural Science Foundation of China under grant no. 11701221. The third author is funded by the National Natural Science Foundation of China under grant no. 11971354.

Author information

Authors and Affiliations

  1. College of Data Science, Jiaxing University, Zhejiang, 314001, People’s Republic of China

    Rui Li

  2. Center for Research in Scientific Computation and Department of Mathematics, North Carolina State University, Raleigh, NC, 27695, USA

    Zhi-Lin Li

  3. School of Mathematical Sciences, Tongji University, Shanghai, 200092, People’s Republic of China

    Jun-Feng Yin

Authors
  1. Rui Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zhi-Lin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jun-Feng Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rui Li.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, R., Li, ZL. & Yin, JF. A generalized modulus-based Newton method for solving a class of non-linear complementarity problems with P-matrices. Numer Algor 89, 839–853 (2022). https://doi.org/10.1007/s11075-021-01136-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-021-01136-3

Keywords

Mathematics Subject Classification (2010)

Search

Navigation