Quadratic convergence analysis of a nonmonotone Levenberg–Marquardt type method for the weighted nonlinear complementarity problem | Computational Optimization and Applications Skip to main content
Springer Nature Link
Log in

Quadratic convergence analysis of a nonmonotone Levenberg–Marquardt type method for the weighted nonlinear complementarity problem

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper we consider the weighted nonlinear complementarity problem (denoted by wNCP) which contains a wide class of optimization problems. We introduce a family of new weighted complementarity functions and show that it is continuously differentiable everywhere and has several favorable properties. Based on this function, we reformulate the wNCP as a smooth nonlinear equation and propose a nonmonotone Levenberg–Marquardt type method to solve it. We show that the proposed method is well-defined and it is globally convergent without any additional condition. Moreover, we prove that the whole iteration sequence converges to a solution of the wNCP locally superlinearly or quadratically under the nonsingularity condition. In addition, we establish the local quadratic convergence of the proposed method under the local error bound condition. Some numerical results are also reported.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Asadi, S., Darvay, Z., Lesaja, G., Mahdavi-Amiri, N., Potra, F.A.: A full-Newton step interior-point method for monotone weighted linear complementarity problems. J. Optim. Theory Appl. 186, 864–878 (2020)

    Article  MathSciNet  Google Scholar 

  2. Andreani, R., Friedlander, A., Santos, S.A.: On the resolution of the generalized nonlinear complementarity problem. SIAM J. Optim. 12, 303–321 (2001)

    Article  MathSciNet  Google Scholar 

  3. Anstreicher, K.M.: Interior-point algorithms for a generalization of linear programming and weighted centering. Optim. Methods Softw. 27, 605–612 (2012)

    Article  MathSciNet  Google Scholar 

  4. Bai, Y.Q., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15(1), 101–128 (2004)

    Article  MathSciNet  Google Scholar 

  5. Bai, Y.Q., Lesaja, G., Roos, C., Wang, G.Q., El Ghami, M.: A class of large-update and small-update primal-dual interior-point algorithms for linear optimization. J. Optim. Theory Appl. 138(3), 341–359 (2008)

    Article  MathSciNet  Google Scholar 

  6. Cai, X.Z., Wang, G.Q., Zhang, Z.H.: Complexity analysis and numerical implementation of primal-dual interior-point methods for convex quadratic optimization based on a finite barrier. Numer. Algorithm 62, 289–306 (2013)

    Article  MathSciNet  Google Scholar 

  7. Chen, J.S., Pan, S.H.: A regularization semismooth Newton method based on the generalized Fischer–Burmeister function for \(P_0\)-NCPs. J. Comput. Appl. Math. 220, 464–479 (2008)

    Article  MathSciNet  Google Scholar 

  8. Chi, X.N., Liu, S.Y.: A one-step smoothing Newton method for second-order cone programming. J. Comput. Appl. Math. 223, 114–123 (2009)

    Article  MathSciNet  Google Scholar 

  9. Chi, X.N., Liu, S.Y.: A non-interior continuation method for second-order cone optimization. Optimization 58, 965–979 (2009)

    Article  MathSciNet  Google Scholar 

  10. Fernandes, L., Friedlander, A., Guedes, M., Júdice, J.: Solution of a general linear complementarity problem using smooth optimization and its application to bilinear programming and LCP. Appl. Math. Optim. 43, 1–19 (2001)

    Article  MathSciNet  Google Scholar 

  11. Fan, J.Y.: Accelerating the modified Levenberg–Marquardt method for nonlinear equations. Math. Comput. 83, 1173–1187 (2014)

    Article  MathSciNet  Google Scholar 

  12. Fan, J.Y., Yuan, Y.X.: On the convergence of a new Levenberg–Marquardt method. Report No. 005, AMSS, Chinese Academy of Science (2001)

  13. Fan, J.Y., Yuan, Y.X.: On the quadratic convergence of the Levenberg–Marquardt method without nonsingularity assumption. Computing 74, 23–39 (2005)

    Article  MathSciNet  Google Scholar 

  14. Huang, Z.H., Han, J., Chen, Z.: Predictor–corrector smoothing Newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a \(P_0\) function. J. Optim. Theory Appl. 117, 39–68 (2003)

    Article  MathSciNet  Google Scholar 

  15. Jiang, H., Fukushima, M., Qi, L., Sun, D.: A trust region method for solving generalized complementarity problems. SIAM J. Optim. 8, 140–157 (1998)

    Article  MathSciNet  Google Scholar 

  16. Jin, P., Ling, C., Shen, H.F.: A smoothing Levenberg–Marquardt algorithm for semi-infinite programming. Comput. Optim. Appl. 60, 675–695 (2015)

    Article  MathSciNet  Google Scholar 

  17. Kanzow, C., Fukushima, M.: Equivalence of the generalized complementarity problem to differentiable unconstrained minimization. J. Optim. Theory Appl. 90, 581–603 (1996)

    Article  MathSciNet  Google Scholar 

  18. Liu, W.A., Wang, C.Y.: A smoothing Levenberg–Marquardt method for generalized semi-infinite programming. Comput. Appl. Math. 32, 89–105 (2013)

    Article  MathSciNet  Google Scholar 

  19. Luo, Z.Q., Pang, J.S.: Error bounds for analysis systems and their applications. Math. Program. 67, 1–28 (1994)

    Article  Google Scholar 

  20. Ma, C.F.: A new smoothing and regularization Newton method for \(P_0\)-NCP. J. Glob. Optim. 48, 241–261 (2010)

    Article  Google Scholar 

  21. Ma, C.F., Chen, X.H.: The convergence of a one-step smoothing Newton method for \(P_0\)-NCP based on a new smoothing NCP-function. J. Comput. Appl. Math. 216, 1–13 (2008)

    Article  MathSciNet  Google Scholar 

  22. Pang, J.S.: Error bounds in mathematical programming. Math. Program. 79, 299–332 (1997)

    MathSciNet  MATH  Google Scholar 

  23. Potra, F.A.: Weighted complementarity problems—a new paradigm for computing equilibria. SIAM J. Optim. 22(4), 1634–1654 (2012)

    Article  MathSciNet  Google Scholar 

  24. Potra, F.A.: Sufficient weighted complementarity problems. Comput. Optim. Appl. 64(2), 467–488 (2016)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  26. Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Math. Program. 87(1), 1–35 (2000)

    Article  MathSciNet  Google Scholar 

  27. Sun, D.F.: A regularization Newton method for solving nonlinear cmplementarity problems. Appl. Math. Optim. 40, 315–339 (1999)

    Article  MathSciNet  Google Scholar 

  28. Tang, J.Y.: A variant nonmonotone smoothing algorithm with improved numerical results for large-scale LWCPs. Comput. Appl. Math. 37, 3927–3939 (2018)

    Article  MathSciNet  Google Scholar 

  29. Tang, J.Y., Zhou, J.C., Fang, L.: A one-parametric class of smoothing functions and an improved regularization Newton method for the NCP. Optimization 65(5), 977–1001 (2016)

    Article  MathSciNet  Google Scholar 

  30. Tang, J.Y., Zhang, H.C.: A nonmonotone smoothing Newton algorithm for weighted complementarity problems. J. Optim. Theory Appl. (2021). https://doi.org/10.1007/s10957-021-01839-6

    Article  MathSciNet  Google Scholar 

  31. Wang, Y., Zhang, X., Qi, L.: Unconstrained optimization reformulation of the generalized nonlinear complementarity problem and related method. Optimization 54(6), 563–577 (2005)

    Article  MathSciNet  Google Scholar 

  32. Ye, Y.: A fully polynomial-time approximation algorithm for computing a stationary point of the general linear complementarity problem. Math. Oper. Res. 18, 334–345 (1994)

    Article  MathSciNet  Google Scholar 

  33. Zhang, J.: A smoothing Newton algorithm for weighted linear complementarity problem. Optim. Lett. 10, 499–509 (2016)

    Article  MathSciNet  Google Scholar 

  34. Zhang, H.C., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14, 1043–1056 (2004)

    Article  MathSciNet  Google Scholar 

  35. Zhang, X.Z., Jiang, H.F., Wang, Y.J.: A smoothing Newton-type method for generalized nonlinear complementarity problem. J. Comput. Appl. Math. 212, 75–85 (2008)

    Article  MathSciNet  Google Scholar 

  36. Zhang, J.L., Chen, J.: A smoothing Levenberg–Marquardt type method for LCP. J. Comput. Math. 22, 735–752 (2004)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This paper was partly supported by National Natural Science Foundation of China (11771255), Young Innovation Teams of Shandong Province (2019KJI013), Program of Science and Technology Activities for Overseas Students in Henan Province in 2020 and Nanhu Scholars Program for Young Scholars of Xinyang Normal University. The authors are grateful to Professor Hongchao Zhang for his suggestion on testing wLCP with a noise and thank for the referees for their careful reading and helpful suggestions.

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Xinyang Normal University, Xinyang, 464000, China

    Jingyong Tang

  2. Department of Statistics, School of Mathematics and Statistics, Shandong University of Technology, Zibo, 255049, China

    Jinchuan Zhou

Authors
  1. Jingyong Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jinchuan Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jingyong Tang.

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

Tang, J., Zhou, J. Quadratic convergence analysis of a nonmonotone Levenberg–Marquardt type method for the weighted nonlinear complementarity problem. Comput Optim Appl 80, 213–244 (2021). https://doi.org/10.1007/s10589-021-00300-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-021-00300-8

Keywords

Search

Navigation