Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A modulus-based nonsmooth Newton’s method for solving horizontal linear complementarity problems

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

In this paper, we introduce and analyze a modulus-based nonsmooth Newton’s method for solving horizontal linear complementarity problems. In particular, we propose both a standard and a parametrized formulation of the method, proving the local convergence of the approaches. The proposed procedures generalize the existing modulus-based nonsmooth Newton’s method for standard linear complementarity problems. Then, we present an implementation of the methods, analyzing also the coupling with a modulus-based matrix splitting iteration. Finally, numerical experiments demonstrate the effectiveness of the proposed approaches in several situations.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem, Classics in Applied Mathematics. SIAM, Philadelphia (2019)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  3. Mangasarian, O.: Solution of symmetric linear complementarity problems by iterative methods. J. Optim. Theory App. 22, 465–485 (1977)

    Article  MathSciNet  Google Scholar 

  4. 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 

  5. 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  Google Scholar 

  6. 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  Google Scholar 

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

  8. Bai, Z.-Z., Zhang, L.-L.: Modulus-based multigrid methods for linear complementarity problems. Numer. Linear Algebra Appl. 24(e2105), 1–15 (2017)

    MathSciNet  MATH  Google Scholar 

  9. Wu, X., Peng, X., Li, W.: A preconditioned general modulus-based matrix splitting iteration method for linear complementarity problems of H-matrices. Numer. Algorithm 79(4), 1131–1146 (2018)

    Article  MathSciNet  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  11. Ren, H., Wang, X., Tang, X.-B., Wang, T.: The general two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems. Comput. Math. Appl. 77(4), 1071–1081 (2019)

    Article  MathSciNet  Google Scholar 

  12. Mezzadri, F.: On the equivalence between some projected and modulus-based splitting methods for linear complementarity problems. Calcolo 56(41), 1–20 (2019)

    MathSciNet  MATH  Google Scholar 

  13. Gowda, M.: Reducing a monotone horizontal LCP to an LCP. Appl. Math. Lett. 8(1), 97–100 (1995)

    Article  MathSciNet  Google Scholar 

  14. Tütüncü, R.H., Todd, M.J.: Reducing horizontal linear complementarity problems. Linear Algebra Appl. 223(224), 717–729 (1995)

    Article  MathSciNet  Google Scholar 

  15. Schutter, B.D., Heemels, W., Bemporad, A.: On the equivalence of linear complementarity problems. Oper. Res. Lett. 30, 211–222 (2002)

    Article  MathSciNet  Google Scholar 

  16. Zhang, Y.: On the convergence of a class on infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optimiz. 4(1), 208–227 (1994)

    Article  MathSciNet  Google Scholar 

  17. Mezzadri, F., Galligani, E.: An intexact Newton methods for solving complementarity problems in hydrodynamic lubrication. Calcolo 55(1), 1 (2018)

    Article  Google Scholar 

  18. Mezzadri, F., Galligani, E.: Splitting methods for a class of horizontal linear complementarity problems. J. Optim. Theory Appl. 180(2), 500–517 (2019)

    Article  MathSciNet  Google Scholar 

  19. Mezzadri, F., Galligani, E.: Modulus-based matrix splitting methods for horizontal linear complementarity problems. Numer. Algor. (In Press). https://doi.org/10.1007/s11075-019-00677-y

  20. Zheng, H., Vong, S.: On convergence of the modulus-based matrix splitting iteartion method for horizontal linear complementarity problem of \({H}_+\)-matrices. Appl. Math. Comput 369, 124890 (2020). https://www.sciencedirect.com/science/article/pii/S0096300319308823?dgcid=rss_sd_all

  21. Zheng, H., Vong, S.: The modulus-based nonsmooth newton’s method for solving a class of nonlinear complementarity problems of P-matrices. Calcolo 55, 37 (2018)

    Article  MathSciNet  Google Scholar 

  22. Chen, X., Qi, L.: A parametrized Newton method and a quasi-Newton method for nonsmooth equations. Comput. Optim. Appl. 3, 157–179 (1994)

    Article  MathSciNet  Google Scholar 

  23. van Bokhoven, W.: Piecewise-Linear Modelling and Analysis. Proefschrift, Eindhoven (1981)

    Google Scholar 

  24. 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 

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

    Article  MathSciNet  Google Scholar 

  26. Ortega, J.M.: Numerical Analysis: A Second Course, Computer Science and Applied Mathematics. Academic Press, New York (1972)

    Google Scholar 

  27. Gao, X., Wang, J.: A neural network for a class of horizontal linear complementarity problems. In: Society, I.C. (Ed.) Seventh International Conference on Computational Intelligence and Security (2011)

  28. Gao, X., Wang, J.: Analysis and application of a one-layer neural network for solving horizontal linear complementarity problems. Int. J. Comput. Int. Sys. 7(4), 724–732 (2014)

    Article  Google Scholar 

Download references

Acknowledgements

The authors desire to thank the anonymous referees for their valuable remarks and suggestions.

Author information

Authors and Affiliations

  1. Department of Engineering “Enzo Ferrari”, University of Modena and Reggio Emilia, Via P. Vivarelli 10/1, Building 26, 41125, Modena, Italy

    F. Mezzadri & E. Galligani

Authors
  1. F. Mezzadri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E. Galligani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to F. Mezzadri.

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

Mezzadri, F., Galligani, E. A modulus-based nonsmooth Newton’s method for solving horizontal linear complementarity problems. Optim Lett 15, 1785–1798 (2021). https://doi.org/10.1007/s11590-019-01515-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-019-01515-9

Keywords

Search

Navigation