Un algoritmo local cuasi-Newton suavizado para resolver el problema de complementariedad no lineal
Publicado 2023-11-30
Palabras clave
- complementariedad no lineal,
- función de complementariedad,
- jacobiano suavizado,
- cuasi-Newton suavizado,
- convergencia cuadrática
- problemas de complementariedad no lineal,
- programación no lineal,
- métodos cuasi Newton,
- sistemas de ecuaciones no lineales,
- jacobiano generalizado ...Más
Cómo citar
Derechos de autor 2023 Revista UIS Ingenierías
Esta obra está bajo una licencia internacional Creative Commons Atribución-SinDerivadas 4.0.
Resumen
Debido a la importancia y efectividad del método con jacobiano suavizado o cuasi-Newton suavizado para resolver indirectamente el problema de complementariedad no lineal, y que la función de complementariedad Mínimo no ha sido usada en conexión con dichos métodos, en el presente trabajo se propone un algoritmo de ese tipo, con dicha función y una suavización de la misma. Se demuestra que bajo ciertas hipótesis el algoritmo propuesto converge local y q-cuadráticamente. Además, se presentan pruebas numéricas que muestran un buen desempeño del algoritmo.
Descargas
Referencias
- M. M. Kostreva, “Elasto-hydrodynamic lubrica- tion: A non-linear complementarity problem,” International Journal for Numerical Methods in Fluids, vol. 4, no. 4, pp. 377–397, 1984, doi: https://doi.org/10.1002/fld.1650040407
- M. Anitescu, J. F. Cremer, F. A. Potra, “On the existence of solutions to complemen- tarity formulations of contact problems with friction,” Complementarity and Variational Problems: State of the art. SIAM Publications, 1997, pp. 12–21.
- M. C. Ferris and J. S. Pang, “Engineering and economic applications of complementarity problems,” SIAM Review, vol. 39, pp. 669–713, 1997, doi: https://doi.org/10.1137/S0036144595285963
- A. Chen, J.-S. Oh, D. Park, W. Recker, “Solving the bicriteria traffic equilibrium pro- blem with variable demand and nonlinear path costs,” Applied Mathematics and Computation, vol. 217, no. 7, pp. 3020–3031, 2010, doi: https://doi.org/10.1016/j.amc.2010.08.035
- R. Pérez, F. Arenas, H. J. Martínez, C. Arias, El problema de complementariedad no lineal: Teoría, aplicaciones y nuevos algoritmos para su solución. Programa Editorial de la Universidad del Valle, 2019.
- C. Kanzow and H. Kleinmichel, “A new class of semismooth newton-type methods for nonlinear complementarity problems,” Computational Optimization and Applications, vol. 11, no. 3, pp. 227–251, 1998, doi: https://doi.org/10.1023/A:1026424918464
- S. L. Hu, Z. H. Huang, and J. S. Chen, “Pro- perties of a family of generalized ncp functions and a derivative free algorithm for complementarity problems,” Journal of Computational and Applied Mathematics, vol. 230, no. 1, pp. 69–82, 2009, doi: https://doi.org/10.1016/j.cam.2008.10.056
- L. Yong, “Nonlinear complementarity problem and solution methods,” in Artificial Intelligence and Computational Intelligence, F. L. Wang, H. Deng, Y. Gao, and J. Lei, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 461–469. doi: https://doi.org/10.1007/978-3-642-16530-6_55
- J. S. Pang and L. Qi, “Nonsmooth equations: Motivation and algorithms,” SIAM Journal on Optimization, vol. 3, no. 3, pp. 443–465, 1993, doi: https://doi.org/10.1137/0803021
- A. Fischer and C. Kanzow, “On finite termina- tion of an iterative method for linear comple- mentarity problems,” Math. Program., vol. 74, no. 3, pp. 279–292, 1996, doi: https://doi.org/10.1007/BF02592200
- A. Sherman, “On newton-iterative methods for the solution of systems of nonlinear equations,” SIAM Journal on Numerical Analysis, vol. 15, no. 4, pp. 755–711, 1978, doi: https://doi.org/10.1137/0715050
- C. G. Broyden, J. E. Dennis, and J. J. Moré, “On the Local and Superlinear Convergence of Quasi-Newton Methods,” IMA J. Appl. Math., vol. 12, no. 3, pp. 223–245, 1973, doi: https://doi.org/10.1093/imamat/12.3.223
- V. L. R. Lopes, J. M. Martínez, and R. Pérez, “On the local convergence of quasi-newton methods for nonlinear complementary problems,” Applied Numerical Mathematics, vol. 30, pp. 3–22, 1999, doi: https://doi.org/10.1016/S0168-9274(98)00080-4
- C. Kanzow and H. Pieper, “Jacobian smoothing methods for nonlinear complementarity pro- blems,” SIAM Journal on Optimization, vol. 9, no. 2, pp. 342–373, 1999, doi: https://doi.org/10.1137/S1052623497328781
- F. E. Arenas, H. J. Martínez, and R. Pérez, “A local jacobian smoothing method for solving nonlinear complementarity problems,” Universitas Scientiarum, vol. 25, no. 1, p. 149–174, May 2020, doi: https://doi.org/10.11144/JAVERIANA.SC25-1.ALJS
- F. H. Clarke, Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics, 1990.
- X. Chen, “Smoothing methods for complemen- tarity problems and their applications: a sur- vey,” J. Oper. Res. Soc. Japan, vol. 43, no. 1, pp. 32–47, 2000.
- J. E. Dennis and R. B. Schnabel, Numerical methods for unconstrained optimization and non-linear equations. Society for Industrial and Applied Mathematics, 1996.
- S. C. Billups, “Algorithms for complementarity problems and Generalized Equations,” Ph.D. dissertation, University of Wisconsin, 1995.
- P. T. Harker, “Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities,” Mathematical Programming, vol. 41, pp. 29–59, 1988, doi: https://doi.org/10.1007/BF01580752
- J. Zhu and B. Hao, “A new smoothing method for solving nonlinear complementarity problems,” Open Mathematics, vol. 17, no. 1, pp. 104–119, 2019, doi: https://doi.org/10.1515/math-2019-0011
- C. Geiger and C. Kanzow, “On the resolu- tion of monotone complementarity problems,” Computational Optimization and Applications, vol. 5, no. 2, pp. 155–173, 1996, doi: https://doi.org/10.1515/math-2019-0011
- A. Byong-Hun, “Iterative methods for linear complementarity problems with upperbounds on primary variables,” Mathematical Programming, vol. 26, no. 3, pp. 295–315, oct 1983.
- Y. Xia, H. Leung, and J. Wang, “A projection neural network and its application to constrai- ned optimization problems,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 49, no. 4, pp. 447–458, 2002, doi: https://doi.org/10.1109/81.995659
- S. Buhmiler and N. Krejić, “A new smoothing quasi-newton method for nonlinear complementarity problems,” Journal of Computational and Applied Mathematics, vol. 211, no. 2, pp. 141–155, feb 2008, doi: https://doi.org/10.1016/j.cam.2006.11.007
- C. Quirá, “Un algoritmo local cuasi-Newton suavizado para resolver el problema de com- plementariedad no lineal,” Ph.D. dissertation, Universidad del Cauca, Popayán, Colombia, Agosto 2021.