Published 2021-10-08
Keywords
- Horizontal complementarity problem,
- inexact Newton method,
- orthogonal projection
How to Cite
Copyright (c) 2021 Revista Integración, temas de matemáticas
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.
Downloads
References
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Arias C.A., “Un algoritmo cuasi Newton inexacto para el problema de complementariedad no lineal”, Tesis (Ph.D.), Universidad del Valle, 2018, 89 p.
- 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.
- 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 and Variational Problems: State of the Art., 92 (1997), 76-90.
- 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.
- 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 Optim., 6 (1995), No. 3, 253-267. doi: 10.1007/BF01099464.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Han J. and Sun D., “Newton-type Methods for Variational Inequalities”, in Advances in Nonlinear Programming (ed.Yuan.), Appl. Optim (1998), 105–118.
- 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).
- 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.
- 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.
- 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.
- 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), No. 1, 45-66. doi: 10.1137/S0895479897329837.
- 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.
- 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.
- 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.