Revista Integración, temas de matemáticas.

Revista Integración, temas de matemáticas

Vol. 39 Núm. 2 (2021): Revista Integración, temas de matemáticas
Artículos científicos

Un algoritmo Newton inexacto para complementariedad horizontal

PDF
  • Carlos Arias,
  • Rosana Pérez,
  • Héctor Martínez
Carlos Arias
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-20210005

Publicado 2021-10-08

Palabras clave

  • Problema de complementariedad horizontal,
  • método de Newton inexacto,
  • proyección ortogonal

Cómo citar

Arias, C., Pérez, R., & Martínez, H. (2021). Un algoritmo Newton inexacto para complementariedad horizontal. Revista Integración, Temas De matemáticas, 39(2), 217–239. https://doi.org/10.18273/revint.v39n2-20210005

Derechos de autor 2021 Revista Integración, temas de matemáticas

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Resumen

En este artículo, proponemos un nuevo algoritmo tipo Newton inexacto para resolver el problema de complementariedad horizontal mediante su reformulación como un problema de minimización restricto. El algoritmo usa la estrategia de combinar una dirección Newton inexacta con su proyección sobre el conjunto factible; esta última opción solo se usa cuando se necesita garantizar factibilidad. Además, presentamos un análisis teórico y numérico del nuevo algoritmo.

PDF

Descargas

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

Referencias

  1. Andreani R., Júdice J.J., Martínez J.M. and Martini T., “Feasibility problems with complementarity constraints”, European J. Oper. Res., 249 (2015), No. 1, 41-54. doi: 10.1016/j.ejor.2015.09.030.
  2. Andreani R., Birgin E.G., Martínez J.M. and Schuverdt M.L., “Augmented Lagrangian methods under the constant positive linear dependence constraint qualification”, Math. Program., 111 (2008), No. 1, 5-32. doi: 10.1007/s10107-006-0077-1.
  3. Andreani R., Friedlander A. and Martínez J.M., “On the solution of infinitedimensional variational inequalities using smooth optimization with simple bounds”, J. Optim. Theory Appl., 94 (1997), No. 3, 635-657. doi: 10.1023/A:1022601017090.
  4. Andreani R., Júudice J.J., Martínez J.M. and Patricio J., “Projected-gradient interior-point algorithm for complementarity problems”, Numer. Algorithms., 57 (2011), No. 4, 457-485. doi: 10.1007/s11075-010-9439-0.
  5. Anitescu M., Tseng P. and Wright S.J., “Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties”, Math. Program., 110 (2007), No. 2, 337-371. doi: 10.1007/s10107-006-0005-4.
  6. Arias C.A. and Martínez J.M., “Fast convergence of an inexact interior-point method for horizontal complementarity problems”, Numer. Algorithms., 79 (2018), 1187– 1210. doi: 10.1007/s11075-018-0480-8.
  7. Arias C.A., “Un algoritmo cuasi Newton inexacto para el problema de complementariedad no lineal”, Tesis (Ph.D.), Universidad del Valle, 2018, 89 p.
  8. Bai Z.Z. and Dong J.L., “A modified damped Newton method for linear complementarity problems”, Numer Algorithms., 42 (2006), No. 3-4, 207-228. doi: 10.1007/s11075-006-9028-4.
  9. Billups S. and Murty K., “Complementarity problems”, J. Comput. Appl. Math., 124 (2000), No. 1-2, 303-318. doi: 10.1016/S0377-0427(00)00432-5.
  10. Cottle R., Pang J. and Stone R., The linear complementarity problem, SIAM classics in applied Mathematics, 1st ed., Philadelphia, 2009. 9–761.
  11. Eisenstat S.C. and Walker H.F., “Globally convergent inexact newton methods”, SIAM J. Optim., 4 (1994), No. 2, 393-422. doi: 10.1137/0804022.
  12. Facchinei F., Fischer A. and Kanzow C., “A semismooth Newton method for variational inequalities: The case of box constraints”, Complementarity and Variational Problems: State of the Art., 92 (1997), 76-90.
  13. Facchinei F. and Kanzow C.A., “Nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems”, Math. Program., 76 (1997), No. 3, 493-512. doi: 10.1007/BF02614395.
  14. Ferris M.C. and Pang J., “Engineering and economic applications of complementarity problems”, SIAM Rev., 39 (1997), No. 4, 669-713. doi: 10.1137/S0036144595285963.
  15. Ferris M. and Kanzow., “Complementarity and related problems: a survey”, Math. Program. Technical Report., (1998), 98-17.
  16. Friedlander A., Martínez J. M. and Santos S.A., “Solution of linear complementarity problems using minimization with simple bounds”, J. Global Optim., 6 (1995), No. 3, 253-267. doi: 10.1007/BF01099464.
  17. Gabriel S.A. and Pang J.S., “An inexact NE/SQP method for solving the nonlinear complementarity problem”, Comput. Optim. Appl., 1 (1992), No. 1, 67-91. doi: 10.1007/BF00247654.
  18. Ge Z., Ni Q. and Zhang X., “A smoothing inexact Newton method for variational inequalities with nonlinear constraints”, J. Inequal. Appl., 160 (2017), 2-12. doi: 10.1186/s13660-017-1433-9.
  19. Guo L., Lin G.H., Zhang D. and Zhu D., “An mpec reformulation of an epec model for electricity markets”, Oper. Res. Lett., 43 (2015), No. 3, 262-267. doi: 10.1016/j.orl.2015.03.001.
  20. Haddou M. and Maheux P., “Smoothing methods for nonlinear complementarity problems”, J. Optim. Theory Appl., 160 (2014), No. 3, 711-729. doi: 10.1007/s10957- 013-0398-1.
  21. Harker P. T. and . Pang J.S., “Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications”, Math. Program., 48 (1990), No. 1, 161-220. doi: 10.1007/BF01582255.
  22. Harker P.T. and Xiao B., “Newton’s method for the nonlinear complementarity problem: A B-differentiable equation approach”, Math. Program., 48 (1990), No. 1, 339-357. doi: 10.1007/BF01582262.
  23. Han J. and Sun D., “Newton-type Methods for Variational Inequalities”, in Advances in Nonlinear Programming (ed.Yuan.), Appl. Optim (1998), 105–118.
  24. Marini L., Morini B. and Porcelli M., “Quasi-newton methods for convex constrained nonlinear systems and their application”, Available on http://www.optimizationonline.org, (2017).
  25. Mezzadri F. and Galligani E., “Modulus-based matrix splittingmethods for a class of horizontal nonlinear complementarity problems,” Numer. Algorithms., 87 (2021), No. 2, 667-687. doi: 10.1007/s11075-020-00983-w.
  26. Morini B., Porcelli M. and Toint L., “Approximate norm descent methods for constrained nonlinear systems”, Math. Comp., 87 (2018), No. 311, 1327-1351. doi: 10.1090/mcom/3251.
  27. Outrata J.V. and Zowe J., “A Newton method for a class of quasi-variational inequalities”, Comput. Optim. Appl., 4 (1995), No. 1, 5-21. doi: 10.1007/BF01299156.
  28. Pang J.S., “Partially b-regular optimization and equilibrium problems”, Math. Oper. Res., 32 (2007), No. 3, 687-699. doi: 10.1287/moor.1070.0262.
  29. Pang J.S., “Inexact Newton methods for the nonlinear complementarity problem”, Math. Program., 36 (1986), No. 1, 54-71. doi: 10.1007/BF02591989.
  30. Qi H.D. and Liao L., “A smoothing Newton method for extended vertical linear complementarity problems”, SIAM J. Matrix Anal. Appl., 21 (1999), No. 1, 45-66. doi: 10.1137/S0895479897329837.
  31. Qi L. and Sun D., “A Survey of Some Nonsmooth Equations and Smoothing Newton Methods”, in Progress in Optimization (ed. Yang, Mess, Fisher and Jennings.), Springer (1999), 121–146.
  32. Ralph D., “Mathematical programs with complementarity constraints in traffic and telecommunications networks”, Philos. Trans. Roy. Soc. A., 366 (2007), No. 1872, 1973-1987. doi: 10.098/rsta.2008.0026.
  33. Yu Z., Liu Y. and Gan X., “Nonmonotone Inexact Newton Method for the Extended Linear Complementarity Problem”, Numer. Funct. Anal. Optim., 38 (2017), No. 11, 1458-1472. doi: 10.1080/01630563.2017.1338731.