Vol. 22 Núm. 4 (2023): Revista UIS Ingenierías
Artículos

Un algoritmo local cuasi-Newton suavizado para resolver el problema de complementariedad no lineal

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

Publicado 2023-11-30

Palabras clave

  • complementariedad no lineal,
  • función de complementariedad,
  • jacobiano suavizado,
  • cuasi-Newton suavizado,
  • convergencia cuadrática,
  • problemas de complementariedad no lineal,
  • programación no lineal,
  • métodos cuasi Newton,
  • sistemas de ecuaciones no lineales,
  • jacobiano generalizado
  • ...Más
    Menos

Cómo citar

Quirá Mosquera, C., Pérez, R., Arenas, F. ., & Correa, D. (2023). Un algoritmo local cuasi-Newton suavizado para resolver el problema de complementariedad no lineal. Revista UIS Ingenierías, 22(4), 147–164. https://doi.org/10.18273/revuin.v22n4-2023013

Resumen

Debido a la importancia y efectividad del método con jacobiano suavizado o cuasi-Newton suavizado para resolver indirectamente el problema de complementariedad no lineal, y que la función de complementariedad Mínimo no ha sido usada en conexión con dichos métodos, en el presente trabajo se propone un algoritmo de ese tipo, con dicha función y una suavización de la misma. Se demuestra que bajo ciertas hipótesis el algoritmo propuesto converge local y q-cuadráticamente. Además, se presentan pruebas numéricas que muestran un buen desempeño del algoritmo.

 

Descargas

Los datos de descargas todavía no están disponibles.

Referencias

  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.