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

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

Wilmer Sánchez
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.

Publicado 2021-10-08

Palabras clave

  • Complementariedad no lineal,
  • función de complementariedad,
  • método de Newton generalizado,
  • Jacobiano suavizado,
  • convergencia global,
  • convergencia superlineal,
  • convergencia cuadrática
  • ...Más
    Menos

Cómo citar

Sánchez, W., Pérez, R., & Martínez, H. (2021). Un algoritmo global con jacobiano suavizado para problemas de complementariedad no lineal. Revista Integración, Temas De matemáticas, 39(2), 191–215. https://doi.org/10.18273/revint.v39n2-20210004

Resumen

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.

Descargas

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

Referencias

Abaffy J., Broyden C. and Spedicato E., “A class of direct methods for linear systems”, Numer. Math., 45 (1984), No. 3, 361–376. doi:10.1007/BF01391414.

Ahn B.H., “Iterative methods for linear complementarity problems with upperbounds on primary variables”, Math. Program., 26 (1983) No. 3, 295-315. doi:10.1007/BF02591868.

Anitescu M., Cremer J.F. and Potra F.A., “On the existence of solutions to complementarity formulations of contact problems with friction”, Complementary and Variational Problems: State of the Art., 92 (1997), 12–21.

Arenas F., Martínez H.J. and Pérez R., “A local Jacobian smoothing method for solving Nonlinear Complementarity Problems”, Universitas Scientiarum, 25 (2020), No. 1, 149– 174. doi: 10.11144/Javeriana.SC25-1.aljs.

Arias C.A., “Un algoritmo cuasi Newton global para problemas de complementariedad no lineal”, Thesis (MSc.), Universidad del Cauca, Popayán, 2014, 44 p.

Buhmiler S. and Krejić N., “A new smoothing quasi-Newton method for nonlinear complementarity problems”, J. Comput. Appl. Math., 211 (2008), No. 2, 141–155. doi: 10.1016/j.cam.2006.11.007.

Billups S.C., “Algorithms for Complementarity Problems and Generalized Equations”, Thesis (Ph.D.), University of Wisconsin, Madison, 1994. 159 p.

Chen A., Oh J.S., Park D. and Recker W., “Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs”, Appl. Math. Comput., 217 (2010), No. 7, 3020–3031. doi: 10.1016/j.amc.2010.08.035.

Chen X., Qi L. and Sun D., “Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities”, Math. Comp., 67 (1998), No. 222, 519–540. doi: 10.1090/S0025-5718-98-00932-6.

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), No. 1, 225–247. doi: 10.1137/S1052623494279110.

Ferris M.C. and Pang J.S., “Engineering and Economic Applications of Complementarity Problems”, SIAM Rev., 39 (1997), No. 4, 669–713. doi: 10.1137/S0036144595285963.

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”, Math. Program., 41 (1988), No. 1, 29–59. doi: 10.1007/BF01580752.

Kanzow C. and Kleinmichel H., “A New Class of Semismooth Newton-Type Methods for Nonlinear Complementarity Problems”, Comput. Optim. Appl., 11 (1998), No. 3, 227–251. doi:10.1023/A:1026424918464.

Kanzow C. and Pieper H., “Jacobian Smoothing Methods for Nonlinear Complementarity Problems”, SIAM J. Optim., 9 (1999), No. 2, 342–373. doi: 10.1137/S1052623497328781.

Kostreva M.M., “Elasto-hydrodynamic lubrication: A non-linear complementarity problem”, Internat. J. Numer. Methods Fluids., 4 (1984), No. 4, 377–397. doi: 10.1002/fld.1650040407.

Li D.H. and Fukushima M., “Globally Convergent Broyden-Like Methods for Semismooth Equations and Applications to VIP, NCP and MCP”, Ann. Oper. Res., 103 (2001), No. 1, 71–97. doi: 10.1023/A:1012996232707.

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. Math., 30 (1999), No. 1, 3–22. doi:10.1016/S0168-9274(98)00080-4.

Ma C., “A new smoothing quasi-Newton method for nonlinear complementarity problems”, Appl. Math. Comput., 171 (2005), No. 2, 807–823. doi: 10.1016/j.amc.2005.01.088.

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”, Numer. Algorithms., 35 (2004), No. 2, 261–285. doi: 10.1023/B:NUMA.0000021762.83420.40.

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, Sydney, 1996.