Un algoritmo Newton inexacto para complementariedad horizontal

• Autores: Carlos Arias, Rosana Pérez, Héctor Martínez
• Localización: Integración: Temas de matemáticas, ISSN 0120-419X, Vol. 39, Nº. 2, 2021, págs. 217-239
• Idioma: español
• DOI: 10.18273/revint.v39n2-20210005
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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.

  • English

    In this article, we proposed a new inexact Newton algorithm tosolve thehorizontal complementarity problemfrom its reformulation as a con-strained minimization problem. The algorithm uses an inexact Newton di-rection and it uses the orthogonal projection of that direction on the feasibleset only when it is necessary to guarantee feasibility. Moreover, we present atheoretical and numerical analysis of the proposed algorithm.

• Referencias bibliográficas
  • Referencias Andreani R., Júdice J.J., Martínez J.M. and Martini T., “Feasibility problems with complementarity constraints”, European J....
  • Andreani R., Birgin E.G., Martínez J.M. and Schuverdt M.L., “Augmented Lagrangian methods under the constant positive linear dependence constraint...
  • Andreani R., Friedlander A. and Martínez J.M., “On the solution of infinitedimensional variational inequalities using smooth optimization...
  • Andreani R., Júudice J.J., Martínez J.M. and Patricio J., “Projected-gradient interior-point algorithm for complementarity problems”, Numer....
  • Anitescu M., Tseng P. and Wright S.J., “Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence...
  • Arias C.A. and Martínez J.M., “Fast convergence of an inexact interior-point method for horizontal complementarity problems”, Numer. Algorithms.,...
  • Arias C.A., “Un algoritmo cuasi Newton inexacto para el problema de complementariedad no lineal”, Tesis (Ph.D.), Universidad del Valle, 2018,...
  • 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....
  • 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.
  • Cottle R., Pang J. and Stone R., The linear complementarity problem, SIAM classics in applied Mathematics, 1st ed., Philadelphia, 2009. 9–761.
  • 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.
  • Facchinei F., Fischer A. and Kanzow C., “A semismooth Newton method for variational inequalities: The case of box constraints”, Complementarity...
  • Facchinei F. and Kanzow C.A., “Nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems”, Math....
  • 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.
  • Ferris M. and Kanzow., “Complementarity and related problems: a survey”, Math. Program. Technical Report., (1998), 98-17.
  • Friedlander A., Martínez J. M. and Santos S.A., “Solution of linear complementarity problems using minimization with simple bounds”, J. Global...
  • Gabriel S.A. and Pang J.S., “An inexact NE/SQP method for solving the nonlinear complementarity problem”, Comput. Optim. Appl., 1 (1992),...
  • Ge Z., Ni Q. and Zhang X., “A smoothing inexact Newton method for variational inequalities with nonlinear constraints”, J. Inequal. Appl.,...
  • 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....
  • Haddou M. and Maheux P., “Smoothing methods for nonlinear complementarity problems”, J. Optim. Theory Appl., 160 (2014), No. 3, 711-729. doi:...
  • Harker P. T. and . Pang J.S., “Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms...
  • Harker P.T. and Xiao B., “Newton’s method for the nonlinear complementarity problem: A B-differentiable equation approach”, Math. Program.,...
  • Han J. and Sun D., “Newton-type Methods for Variational Inequalities”, in Advances in Nonlinear Programming (ed.Yuan.), Appl. Optim (1998),...
  • Marini L., Morini B. and Porcelli M., “Quasi-newton methods for convex constrained nonlinear systems and their application”, Available on...
  • Mezzadri F. and Galligani E., “Modulus-based matrix splittingmethods for a class of horizontal nonlinear complementarity problems,” Numer....
  • Morini B., Porcelli M. and Toint L., “Approximate norm descent methods for constrained nonlinear systems”, Math. Comp., 87 (2018), No. 311,...
  • 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:...
  • 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.
  • Pang J.S., “Inexact Newton methods for the nonlinear complementarity problem”, Math. Program., 36 (1986), No. 1, 54-71. doi: 10.1007/BF02591989.
  • Qi H.D. and Liao L., “A smoothing Newton method for extended vertical linear complementarity problems”, SIAM J. Matrix Anal. Appl., 21 (1999),...
  • Qi L. and Sun D., “A Survey of Some Nonsmooth Equations and Smoothing Newton Methods”, in Progress in Optimization (ed. Yang, Mess, Fisher...
  • Ralph D., “Mathematical programs with complementarity constraints in traffic and telecommunications networks”, Philos. Trans. Roy. Soc. A.,...
  • Yu Z., Liu Y. and Gan X., “Nonmonotone Inexact Newton Method for the Extended Linear Complementarity Problem”, Numer. Funct. Anal. Optim.,...