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 inexact Newton algorithm for horizontal complementarity

PDF (Español (España))
  • 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

Published 2021-10-08

Keywords

  • Horizontal complementarity problem,
  • inexact Newton method,
  • orthogonal projection

How to Cite

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

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 article, we proposed a new inexact Newton algorithm to solve the horizontal complementarity problem from its reformulation as a constrained minimization problem. The algorithm uses an inexact Newton direction and it uses the orthogonal projection of that direction on the feasible set only when it is necessary to guarantee feasibility. Moreover, we present a theoretical and numerical analysis of the proposed algorithm.

PDF (Español (España))

Downloads

Download data is not yet available.

References

  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.