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.

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.

Palabras clave: Complementariedad no lineal, función de complementariedad, método de Newton generalizado, Jacobiano suavizado, convergencia global, convergencia superlineal, convergencia cuadrática

Descargas

La descarga de datos todavía no está disponible.

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.
Publicado
2021-10-08