Revista UIS Ingenierías

Vol. 22 No. 4 (2023): Revista UIS Ingenierías
Articles

A local smoothing quasi-Newton algorithm for solving nonlinear complementarity problem

PDF (Español (España))
  • Camila Quirá Mosquera,
  • Rosana Pérez,
  • Favián Arenas,
  • Diego Correa
Camila Quirá Mosquera
Universidad Autónoma Indígena Intercultura
Rosana Pérez
Universidad del Cauca
Favián Arenas
Universidad del Cauca
Diego Correa
Universidad del Cauca
DOI: https://doi.org/10.18273/revuin.v22n4-2023013

Published 2023-11-30

Keywords

  • nonlinear complementarity,
  • minimun complementarity function,
  • Jacobian smoothing method,
  • smoothing quasi-Newton method,
  • quadratic convergence,
  • nonlinear complementarity problems,
  • nonlinear programming,
  • Quasi-Newton methods,
  • systems of nonlinear equations,
  • generalized jacobian
    • ...More
    Less

How to Cite

Quirá Mosquera, C., Pérez, R., Arenas, F. ., & Correa, D. (2023). A local smoothing quasi-Newton algorithm for solving nonlinear complementarity problem. Revista UIS Ingenierías, 22(4), 147–164. https://doi.org/10.18273/revuin.v22n4-2023013

Copyright (c) 2023 Revista UIS Ingenierías

Creative Commons License

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

Abstract

Due to the importance and effectiveness of a Jacobian smoothing method or smoothing quasi-Newton method for solving the nonlinear complementarity problem and that the Minimum complementarity function has not been used in connection with such methods, in the present work, we propose an algorithm of that type, which uses the minimum function and a smoothing of it. We show that under certain hypotheses the proposed algorithm converges locally and q-quadratically. In addition, we present numerical tests that show a good performance of the algorithm.

 

PDF (Español (España))

Downloads

Download data is not yet available.

References

  1. M. M. Kostreva, “Elasto-hydrodynamic lubrica- tion: A non-linear complementarity problem,” International Journal for Numerical Methods in Fluids, vol. 4, no. 4, pp. 377–397, 1984, doi: https://doi.org/10.1002/fld.1650040407
  2. M. Anitescu, J. F. Cremer, F. A. Potra, “On the existence of solutions to complemen- tarity formulations of contact problems with friction,” Complementarity and Variational Problems: State of the art. SIAM Publications, 1997, pp. 12–21.
  3. M. C. Ferris and J. S. Pang, “Engineering and economic applications of complementarity problems,” SIAM Review, vol. 39, pp. 669–713, 1997, doi: https://doi.org/10.1137/S0036144595285963
  4. A. Chen, J.-S. Oh, D. Park, W. Recker, “Solving the bicriteria traffic equilibrium pro- blem with variable demand and nonlinear path costs,” Applied Mathematics and Computation, vol. 217, no. 7, pp. 3020–3031, 2010, doi: https://doi.org/10.1016/j.amc.2010.08.035
  5. R. Pérez, F. Arenas, H. J. Martínez, C. Arias, El problema de complementariedad no lineal: Teoría, aplicaciones y nuevos algoritmos para su solución. Programa Editorial de la Universidad del Valle, 2019.
  6. C. Kanzow and H. Kleinmichel, “A new class of semismooth newton-type methods for nonlinear complementarity problems,” Computational Optimization and Applications, vol. 11, no. 3, pp. 227–251, 1998, doi: https://doi.org/10.1023/A:1026424918464
  7. S. L. Hu, Z. H. Huang, and J. S. Chen, “Pro- perties of a family of generalized ncp functions and a derivative free algorithm for complementarity problems,” Journal of Computational and Applied Mathematics, vol. 230, no. 1, pp. 69–82, 2009, doi: https://doi.org/10.1016/j.cam.2008.10.056
  8. L. Yong, “Nonlinear complementarity problem and solution methods,” in Artificial Intelligence and Computational Intelligence, F. L. Wang, H. Deng, Y. Gao, and J. Lei, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 461–469. doi: https://doi.org/10.1007/978-3-642-16530-6_55
  9. J. S. Pang and L. Qi, “Nonsmooth equations: Motivation and algorithms,” SIAM Journal on Optimization, vol. 3, no. 3, pp. 443–465, 1993, doi: https://doi.org/10.1137/0803021
  10. A. Fischer and C. Kanzow, “On finite termina- tion of an iterative method for linear comple- mentarity problems,” Math. Program., vol. 74, no. 3, pp. 279–292, 1996, doi: https://doi.org/10.1007/BF02592200
  11. A. Sherman, “On newton-iterative methods for the solution of systems of nonlinear equations,” SIAM Journal on Numerical Analysis, vol. 15, no. 4, pp. 755–711, 1978, doi: https://doi.org/10.1137/0715050
  12. C. G. Broyden, J. E. Dennis, and J. J. Moré, “On the Local and Superlinear Convergence of Quasi-Newton Methods,” IMA J. Appl. Math., vol. 12, no. 3, pp. 223–245, 1973, doi: https://doi.org/10.1093/imamat/12.3.223
  13. V. L. R. Lopes, J. M. Martínez, and R. Pérez, “On the local convergence of quasi-newton methods for nonlinear complementary problems,” Applied Numerical Mathematics, vol. 30, pp. 3–22, 1999, doi: https://doi.org/10.1016/S0168-9274(98)00080-4
  14. C. Kanzow and H. Pieper, “Jacobian smoothing methods for nonlinear complementarity pro- blems,” SIAM Journal on Optimization, vol. 9, no. 2, pp. 342–373, 1999, doi: https://doi.org/10.1137/S1052623497328781
  15. F. E. Arenas, H. J. Martínez, and R. Pérez, “A local jacobian smoothing method for solving nonlinear complementarity problems,” Universitas Scientiarum, vol. 25, no. 1, p. 149–174, May 2020, doi: https://doi.org/10.11144/JAVERIANA.SC25-1.ALJS
  16. F. H. Clarke, Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics, 1990.
  17. X. Chen, “Smoothing methods for complemen- tarity problems and their applications: a sur- vey,” J. Oper. Res. Soc. Japan, vol. 43, no. 1, pp. 32–47, 2000.
  18. J. E. Dennis and R. B. Schnabel, Numerical methods for unconstrained optimization and non-linear equations. Society for Industrial and Applied Mathematics, 1996.
  19. S. C. Billups, “Algorithms for complementarity problems and Generalized Equations,” Ph.D. dissertation, University of Wisconsin, 1995.
  20. P. T. Harker, “Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities,” Mathematical Programming, vol. 41, pp. 29–59, 1988, doi: https://doi.org/10.1007/BF01580752
  21. J. Zhu and B. Hao, “A new smoothing method for solving nonlinear complementarity problems,” Open Mathematics, vol. 17, no. 1, pp. 104–119, 2019, doi: https://doi.org/10.1515/math-2019-0011
  22. C. Geiger and C. Kanzow, “On the resolu- tion of monotone complementarity problems,” Computational Optimization and Applications, vol. 5, no. 2, pp. 155–173, 1996, doi: https://doi.org/10.1515/math-2019-0011
  23. A. Byong-Hun, “Iterative methods for linear complementarity problems with upperbounds on primary variables,” Mathematical Programming, vol. 26, no. 3, pp. 295–315, oct 1983.
  24. Y. Xia, H. Leung, and J. Wang, “A projection neural network and its application to constrai- ned optimization problems,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 49, no. 4, pp. 447–458, 2002, doi: https://doi.org/10.1109/81.995659
  25. S. Buhmiler and N. Krejić, “A new smoothing quasi-newton method for nonlinear complementarity problems,” Journal of Computational and Applied Mathematics, vol. 211, no. 2, pp. 141–155, feb 2008, doi: https://doi.org/10.1016/j.cam.2006.11.007
  26. C. Quirá, “Un algoritmo local cuasi-Newton suavizado para resolver el problema de com- plementariedad no lineal,” Ph.D. dissertation, Universidad del Cauca, Popayán, Colombia, Agosto 2021.