Un algoritmo global con jacobiano suavizado para problemas de complementariedad no lineal

• Autores: Wilmer Sánchez, 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. 191-215
• Idioma: español
• DOI: 10.18273/revint.v39n2-20210004
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    En este artículo, usamos la estrategia del jacobiano suavizado para proponer un nuevo algoritmo para resolver problemas de complementariedad no lineal basado en su reformulación como un sistema de ecuaciones no lineales. Este algoritmo puede verse como una generalización del propuesto en [18]. Desarrollamos su teoría de convergencia global y bajo ciertas hipótesis, demostramos que el algoritmo converge local y q superlineal o q cuadráticamente a la solución del problema. Pruebas numéricas muestran un buen desempeño del algoritmo propuesto.

  • English

    In this paper, we use the smoothing Jacobian strategy to proposea new algorithm for solving complementarity problems based on its reformu-lation as a nonsmooth system of equations. This algorithm can be seen as ageneralization of the one proposed in [18]. We develop its global convergencetheory and under certain assumptions, we demonstrate that the proposedalgorithm converges locally and,q-superlinearly orq-quadratically to a solu-tion of the problem. Some numerical experiments show a good performanceof this algorithm.

• Referencias bibliográficas
  • Referencias Abaffy J., Broyden C. and Spedicato E., “A class of direct methods for linear systems”, Numer. Math., 45 (1984), No. 3, 361–376....
  • Ahn B.H., “Iterative methods for linear complementarity problems with upperbounds on primary variables”, Math. Program., 26 (1983) No. 3,...
  • Anitescu M., Cremer J.F. and Potra F.A., “On the existence of solutions to complementarity formulations of contact problems with friction”,...
  • Arenas F., Martínez H.J. and Pérez R., “A local Jacobian smoothing method for solving Nonlinear Complementarity Problems”, Universitas Scientiarum,...
  • Arias C.A., “Un algoritmo cuasi Newton global para problemas de complementariedad no lineal”, Thesis (MSc.), Universidad del Cauca, Popayán,...
  • Buhmiler S. and Krejić N., “A new smoothing quasi-Newton method for nonlinear complementarity problems”, J. Comput. Appl. Math., 211 (2008),...
  • Billups S.C., “Algorithms for Complementarity Problems and Generalized Equations”, Thesis (Ph.D.), University of Wisconsin, Madison, 1994....
  • Chen A., Oh J.S., Park D. and Recker W., “Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs”,...
  • Chen X., Qi L. and Sun D., “Global and superlinear convergence of the smoothing Newton method and its application to general box constrained...
  • Clarke F.H., “Generalized gradients and applications”, Trans. Amer. Math. Soc., 205 (1975), 247–262. doi:10.1090/S0002-9947-1975-0367131-6.
  • Clarke F.H., Optimization and Nonsmooth Analysis, SIAM, 1990.
  • Dennis J.E. and Schnabel R.B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM, 1st ed., Philadelphia, 1996.
  • Facchinei F. and Soares J., “A New Merit Function For Nonlinear Complementarity Problems And A Related Algorithm”, SIAM J. Optim., 7 (1997),...
  • Ferris M.C. and Pang J.S., “Engineering and Economic Applications of Complementarity Problems”, SIAM Rev., 39 (1997), No. 4, 669–713. doi:...
  • Geiger C. and Kanzow C., “On the resolution of monotone complementarity problems”, Comput. Optim. Appl., 5 (1996), No. 2, 155–173. doi: 10.1007/BF00249054.
  • Harker P.T., “Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities”,...
  • Kanzow C. and Kleinmichel H., “A New Class of Semismooth Newton-Type Methods for Nonlinear Complementarity Problems”, Comput. Optim. Appl.,...
  • Kanzow C. and Pieper H., “Jacobian Smoothing Methods for Nonlinear Complementarity Problems”, SIAM J. Optim., 9 (1999), No. 2, 342–373. doi:...
  • Kostreva M.M., “Elasto-hydrodynamic lubrication: A non-linear complementarity problem”, Internat. J. Numer. Methods Fluids., 4 (1984), No....
  • Li D.H. and Fukushima M., “Globally Convergent Broyden-Like Methods for Semismooth Equations and Applications to VIP, NCP and MCP”, Ann. Oper....
  • Lopes V.L., Martínez J.M. and Pérez R., “On the local convergence of quasi-Newton methods for nonlinear complementarity problems”, Appl. Numer....
  • Ma C., “A new smoothing quasi-Newton method for nonlinear complementarity problems”, Appl. Math. Comput., 171 (2005), No. 2, 807–823. doi:...
  • Moré J.J. and Sorensen D.C., “Computing a Trust Region Step”, SIAM J. Sci. and Stat. Comput., 4 (1983), No. 3, 553–572. doi: 10.1137/0904038.
  • Nocedal J. and Wright S., Numerical optimization, Springer Science & Business Media, 2nd ed., 2006.
  • Pang J.S. and Qi L., “Nonsmooth Equations: Motivation and Algorithms”, SIAM J. Optim., 3 (1993), No. 3, 443–465. doi: 10.1137/0803021.
  • Pérez R. and Lopes V.L., “Recent Applications and Numerical Implementation of QuasiNewton Methods for Solving Nonlinear Systems of Equations”,...
  • Qi L., “Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations”, Math. Oper. Res., 18 (1993), No. 1, 227–244. doi: 10.1287/moor.18.1.227.
  • Qi L., C-differentiability, C-differential operators and generalized Newton methods, School of Mathematics University of New South Wales,...