Revista Integración, temas de matemáticas.

Revista Integración, temas de matemáticas

Vol. 39 No. 2 (2021): Revista Integración, temas de matemáticas
Research and Innovation Articles

An global Jacobian smoothing algorithm for nonlinear complementarity problems

PDF (Español (España))
  • Wilmer Sánchez,
  • Rosana Pérez,
  • Héctor Martínez
Wilmer Sánchez
Universidad del Cauca, Departamento de Matemáticas, Popayán, Colombia.
Rosana Pérez
Universidad del Cauca, Departamento de Matemáticas, Popayán, Colombia.
Héctor Martínez
Universidad del Valle, Departamento de Matemáticas, Cali, Colombia.
DOI: https://doi.org/10.18273/revint.v39n2-20210004

Published 2021-10-08

Keywords

  • Nonlinear complementarity problems,
  • complementarity function,
  • generalized Newton methods,
  • Jacobian smoothing method,
  • global convergence,
  • superlinear convergence,
  • quadratic convergence
    • ...More
    Less

How to Cite

Sánchez, W., Pérez, R., & Martínez, H. (2021). An global Jacobian smoothing algorithm for nonlinear complementarity problems. Revista Integración, Temas De matemáticas, 39(2), 191–215. https://doi.org/10.18273/revint.v39n2-20210004

Copyright (c) 2021 Revista Integración, temas de matemáticas

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Abstract

 In this paper, we use the smoothing Jacobian strategy to propose a new algorithm for solving complementarity problems based on its reformulation as a nonsmooth system of equations. This algorithm can be seen as a generalization of the one proposed in [18]. We develop its global convergence theory and under certain assumptions, we demonstrate that the proposed algorithm converges locally and, q-superlinearly or q-quadratically to a solution of the problem. Some numerical experiments show a good performance of this algorithm.

PDF (Español (España))

Downloads

Download data is not yet available.

References

  1. Abaffy J., Broyden C. and Spedicato E., “A class of direct methods for linear systems”, Numer. Math., 45 (1984), No. 3, 361–376. doi:10.1007/BF01391414.
  2. Ahn B.H., “Iterative methods for linear complementarity problems with upperbounds on primary variables”, Math. Program., 26 (1983) No. 3, 295-315. doi:10.1007/BF02591868.
  3. Anitescu M., Cremer J.F. and Potra F.A., “On the existence of solutions to complementarity formulations of contact problems with friction”, Complementary and Variational Problems: State of the Art., 92 (1997), 12–21.
  4. Arenas F., Martínez H.J. and Pérez R., “A local Jacobian smoothing method for solving Nonlinear Complementarity Problems”, Universitas Scientiarum, 25 (2020), No. 1, 149– 174. doi: 10.11144/Javeriana.SC25-1.aljs.
  5. Arias C.A., “Un algoritmo cuasi Newton global para problemas de complementariedad no lineal”, Thesis (MSc.), Universidad del Cauca, Popayán, 2014, 44 p.
  6. Buhmiler S. and Krejić N., “A new smoothing quasi-Newton method for nonlinear complementarity problems”, J. Comput. Appl. Math., 211 (2008), No. 2, 141–155. doi: 10.1016/j.cam.2006.11.007.
  7. Billups S.C., “Algorithms for Complementarity Problems and Generalized Equations”, Thesis (Ph.D.), University of Wisconsin, Madison, 1994. 159 p.
  8. Chen A., Oh J.S., Park D. and Recker W., “Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs”, Appl. Math. Comput., 217 (2010), No. 7, 3020–3031. doi: 10.1016/j.amc.2010.08.035.
  9. Chen X., Qi L. and Sun D., “Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities”, Math. Comp., 67 (1998), No. 222, 519–540. doi: 10.1090/S0025-5718-98-00932-6.
  10. Clarke F.H., “Generalized gradients and applications”, Trans. Amer. Math. Soc., 205 (1975), 247–262. doi:10.1090/S0002-9947-1975-0367131-6.
  11. Clarke F.H., Optimization and Nonsmooth Analysis, SIAM, 1990.
  12. Dennis J.E. and Schnabel R.B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM, 1st ed., Philadelphia, 1996.
  13. Facchinei F. and Soares J., “A New Merit Function For Nonlinear Complementarity Problems And A Related Algorithm”, SIAM J. Optim., 7 (1997), No. 1, 225–247. doi: 10.1137/S1052623494279110.
  14. Ferris M.C. and Pang J.S., “Engineering and Economic Applications of Complementarity Problems”, SIAM Rev., 39 (1997), No. 4, 669–713. doi: 10.1137/S0036144595285963.
  15. Geiger C. and Kanzow C., “On the resolution of monotone complementarity problems”, Comput. Optim. Appl., 5 (1996), No. 2, 155–173. doi: 10.1007/BF00249054.
  16. Harker P.T., “Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities”, Math. Program., 41 (1988), No. 1, 29–59. doi: 10.1007/BF01580752.
  17. Kanzow C. and Kleinmichel H., “A New Class of Semismooth Newton-Type Methods for Nonlinear Complementarity Problems”, Comput. Optim. Appl., 11 (1998), No. 3, 227–251. doi:10.1023/A:1026424918464.
  18. Kanzow C. and Pieper H., “Jacobian Smoothing Methods for Nonlinear Complementarity Problems”, SIAM J. Optim., 9 (1999), No. 2, 342–373. doi: 10.1137/S1052623497328781.
  19. Kostreva M.M., “Elasto-hydrodynamic lubrication: A non-linear complementarity problem”, Internat. J. Numer. Methods Fluids., 4 (1984), No. 4, 377–397. doi: 10.1002/fld.1650040407.
  20. Li D.H. and Fukushima M., “Globally Convergent Broyden-Like Methods for Semismooth Equations and Applications to VIP, NCP and MCP”, Ann. Oper. Res., 103 (2001), No. 1, 71–97. doi: 10.1023/A:1012996232707.
  21. Lopes V.L., Martínez J.M. and Pérez R., “On the local convergence of quasi-Newton methods for nonlinear complementarity problems”, Appl. Numer. Math., 30 (1999), No. 1, 3–22. doi:10.1016/S0168-9274(98)00080-4.
  22. Ma C., “A new smoothing quasi-Newton method for nonlinear complementarity problems”, Appl. Math. Comput., 171 (2005), No. 2, 807–823. doi: 10.1016/j.amc.2005.01.088.
  23. Moré J.J. and Sorensen D.C., “Computing a Trust Region Step”, SIAM J. Sci. and Stat. Comput., 4 (1983), No. 3, 553–572. doi: 10.1137/0904038.
  24. Nocedal J. and Wright S., Numerical optimization, Springer Science & Business Media, 2nd ed., 2006.
  25. Pang J.S. and Qi L., “Nonsmooth Equations: Motivation and Algorithms”, SIAM J. Optim., 3 (1993), No. 3, 443–465. doi: 10.1137/0803021.
  26. Pérez R. and Lopes V.L., “Recent Applications and Numerical Implementation of QuasiNewton Methods for Solving Nonlinear Systems of Equations”, Numer. Algorithms., 35 (2004), No. 2, 261–285. doi: 10.1023/B:NUMA.0000021762.83420.40.
  27. Qi L., “Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations”, Math. Oper. Res., 18 (1993), No. 1, 227–244. doi: 10.1287/moor.18.1.227.
  28. Qi L., C-differentiability, C-differential operators and generalized Newton methods, School of Mathematics University of New South Wales, Sydney, 1996.