Métodos secantes de cambio mínimo para el problema de complementariedad no lineal
Main Article Content
Keywords
sistemas no diferenciables, complementariedad no lineal, métodos cuasi-Newton
Resumen
En este trabajo generamos una familia de métodos secante de cambio mínimo para resolver Problemas de Complementariedad no Lineal vía su reformulación como un sistema de ecuaciones no lineales no diferenciable usando una clase de funciones de complementariedad propuesta por Kanzow and Kleinmichel. Bajo ciertas hipótesis demostramos que esta familia proporciona algoritmos local y superlinealmente convergentes. Experimentos numéricos preliminares demuestran un buen desempeño de los algoritmos propuestos.
Descargas
Los datos de descargas todavía no están disponibles.
Referencias
M. Anitescu, J. F. Cremer, and F. A. Potra, "On the existence of solutionsto complementarity formulations of contact problems with friction," in In:Complementarity and Variational Problems: State of the art. SIAM Publications,1997, pp. 12–21
M. Kostreva, "Elasto-hydrodynamic lubrication: A non-linear complementarityproblem," International Journal for Numerical Methods in Fluids, vol. 4,no. 4, pp. 377–397, 1984 http://dx.doi.org/10.1002/fld.1650040407
A. Chen, J.-S. Oh, D. Park, and W. Recker, "Solving the bicriteria trafficequilibrium problem with variable demand and nonlinear path costs," AppliedMathematics and Computation, vol. 217, no. 7, pp. 3020–3031, 2010 http://dx.doi.org/10.1016/j.amc.2010.08.035
M. C. Ferris and J.-S. Pang, "Engineering and economic applications of complementarityproblems," SIAM Review, vol. 39, pp. 669–713, 1997
http://dx.doi.org/10.1137/S0036144595285963
L. Yong, "Nonlinear complementarity problem and solution methods," inProceedings of the 2010 international conference on Artificial intelligenceand computational intelligence: Part I. Springer-Verlag, 2010, pp. 461–469
L. Qi, "Convergence analysis of some algorithms for solving nonsmooth equations,"Math. Oper. Res., vol. 18, no. 1, pp. 227–244, 1993 http://dx.doi.org/10.1287/moor.18.1.227
V. L. R. Lopes, J. M. Martínez, and R. Pérez, "On the local convergenceof quasi-newton methods for nonlinear complementary problems," AppliedNumerical Mathematics, vol. 30, pp. 3–22, 1999 http://dx.doi.org/10.1016/S0168-9274(98)00080-4
C. G. Broyden, J. E. Dennis, and J. J. Moré, On the Local and SuperlinearConvergence of Quasi-Newton Methods, ser. PB 211 923. Department ofComputer Science, Cornell University, 1972.
D.-H. Li and M. Fukushima, "Globally convergent broyden-like methods forsemismooth equations and applications to vip, ncp and mcp," Annals ofOperations Research, vol. 103, no. 1-4, pp. 71–97, 2001.
J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimizationand Nonlinear Equations. Society for Industrial and AppliedMathematics, 1996. http://dx.doi.org/10.1137/1.9781611971200
R. Pérez and V. L. R. Lopes, "Recent applications and numerical implementationof quasi-newton methods for solving nonlinear systems of equations,"Numerical Algorithms, vol. 35, pp. 261–285, 2004. http://dx.doi.org/10.1023/B:NUMA.0000021762.83420.40
C. Ma, "A new smoothing quasi-newton method for nonlinear complementarityproblems," Applied Mathematics and Computation, vol. 171, no. 2, pp.807–823, 2005. http://dx.doi.org/10.1016/j.amc.2005.01.088
S. Buhmiler and N. Krejic, "A new smoothing quasi-newton method for nonlinearcomplementarity problems," Journal of Computational and AppliedMathematics, vol. 211, no. 2, pp. 141 – 155, 2008. http://dx.doi.org/10.1016/j.cam.2006.11.007
J.-S. Pang and L. Qi, "Nonsmooth equations: Motivation and algorithms,"SIAM Journal on Optimization, vol. 3, no. 3, pp. 443–465, 1993. http://dx.doi.org/10.1137/0803021
C. Kanzow and H. Kleinmichel, "A new class of semismooth newton-typemethods for nonlinear complementarity problems," Comput. Optim. Appl.,vol. 11, no. 3, pp. 227–251, 1998. http://dx.doi.org/10.1023/A:1026424918464
F. E. Arenas A., "Métodos secantes de cambio mínimo," Master's thesis,Universidad del Cauca, 2013.
J. M. Martínez, "Practical quasi-newton methods for solving nonlinear systems,"Journal of Computational and Applied Mathematics, vol. 124, no. 1,pp. 97 – 121, 2000. http://dx.doi.org/10.1016/S0377-0427(00)00434-9
L. Lukšan, "Inexact trust region method for large sparse systems of nonlinearequations," Journal of Optimization Theory and Applications, vol. 81, pp. 569–590, 1994. http://dx.doi.org/10.1007/BF02193101
F. H. Clarke, Optimization and Nonsmooth Analysis. Society for Industrialand Applied Mathematics, 1990. http://dx.doi.org/10.1137/1.9781611971309
T. De Luca, F. Facchinei, and C. Kanzow, "A semismooth equation approachto the solution of nonlinear complementarity problems," Mathematical Programming,vol. 75, pp. 407–439, 1996. http://dx.doi.org/10.1016/S0025-5610(96)00028-7 http://dx.doi.org/10.1007/BF02592192
J. E. Dennis, Jr. and J. J. More, "A characterization of superlinear convergenceand its application to quasi-newton methods," Mathematics of Computation,vol. 28, no. 126, pp. 549–560, 1974. http://dx.doi.org/10.1090/S0025-5718-1974-0343581-1
C. G. Broyden, "A Class of Methods for Solving Nonlinear SimultaneousEquations," Mathematics of Computation, vol. 19, no. 92, pp. 577–593, 1965. http://dx.doi.org/10.1090/S0025-5718-1965-0198670-6
T. F. Coleman, B. S. Garbow, and J. J. More, "Software for estimating sparsejacobian matrices," ACM Trans. Math. Softw., vol. 10, no. 3, pp. 329–345,Aug. 1984. http://dx.doi.org/10.1145/1271.1610
J. M. Martínez, "On the relation between two local convergence theories ofleast change secant update methods," Mathematics of Computation, vol. 59,no. 200, pp. pp. 457–481, 1992.
M. Kojima and S. Shindoh, Extensions of Newton and Quasi-Newton Methodsto Systems of PC 1 Equations, ser. Research reports on informationsciences. Inst. of Technology, Department of Information Sciences, 1986.
L. Mathiesen, "An algorithm based on a sequence of linear complementarityproblems applied to a walrasian equilibrium model: An example," MathematicalProgramming, vol. 37, pp. 1–18, 1987. http://dx.doi.org/10.1007/BF02591680
M. A. Gomes-Ruggiero, J. Martınez, and S. A. Santos, "Solving nonsmoothequations by means of quasi-newton methods with globalization," Recent Advancesin Noonsmooth Optimization, World Scientific Publisher, Singapore,pp. 121–140, 1995.
R. Pérez M., "Algoritmos para complementariedade não lineal e problemasrelacionados," Ph.D. dissertation, IMECC, UNICAM, Campinas, Brazil,Dezembro 1997.
J. M. Martínez, "A quasi-newton method with modification of one columnper iteration," Computing, vol. 33, no. 3-4, pp. 353–362, 1984. http://dx.doi.org/10.1007/BF02242278
J. M. Martínez and M. C. Zambaldi, "An inverse column-updating methodfor solving large scale nonlinear systems of equations," Optimization Methodsand Software, vol. 1, no. 2, pp. 129–140, 1992. http://dx.doi.org/10.1080/10556789208805512
M. Kostreva, "Elasto-hydrodynamic lubrication: A non-linear complementarityproblem," International Journal for Numerical Methods in Fluids, vol. 4,no. 4, pp. 377–397, 1984 http://dx.doi.org/10.1002/fld.1650040407
A. Chen, J.-S. Oh, D. Park, and W. Recker, "Solving the bicriteria trafficequilibrium problem with variable demand and nonlinear path costs," AppliedMathematics and Computation, vol. 217, no. 7, pp. 3020–3031, 2010 http://dx.doi.org/10.1016/j.amc.2010.08.035
M. C. Ferris and J.-S. Pang, "Engineering and economic applications of complementarityproblems," SIAM Review, vol. 39, pp. 669–713, 1997
http://dx.doi.org/10.1137/S0036144595285963
L. Yong, "Nonlinear complementarity problem and solution methods," inProceedings of the 2010 international conference on Artificial intelligenceand computational intelligence: Part I. Springer-Verlag, 2010, pp. 461–469
L. Qi, "Convergence analysis of some algorithms for solving nonsmooth equations,"Math. Oper. Res., vol. 18, no. 1, pp. 227–244, 1993 http://dx.doi.org/10.1287/moor.18.1.227
V. L. R. Lopes, J. M. Martínez, and R. Pérez, "On the local convergenceof quasi-newton methods for nonlinear complementary problems," AppliedNumerical Mathematics, vol. 30, pp. 3–22, 1999 http://dx.doi.org/10.1016/S0168-9274(98)00080-4
C. G. Broyden, J. E. Dennis, and J. J. Moré, On the Local and SuperlinearConvergence of Quasi-Newton Methods, ser. PB 211 923. Department ofComputer Science, Cornell University, 1972.
D.-H. Li and M. Fukushima, "Globally convergent broyden-like methods forsemismooth equations and applications to vip, ncp and mcp," Annals ofOperations Research, vol. 103, no. 1-4, pp. 71–97, 2001.
J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimizationand Nonlinear Equations. Society for Industrial and AppliedMathematics, 1996. http://dx.doi.org/10.1137/1.9781611971200
R. Pérez and V. L. R. Lopes, "Recent applications and numerical implementationof quasi-newton methods for solving nonlinear systems of equations,"Numerical Algorithms, vol. 35, pp. 261–285, 2004. http://dx.doi.org/10.1023/B:NUMA.0000021762.83420.40
C. Ma, "A new smoothing quasi-newton method for nonlinear complementarityproblems," Applied Mathematics and Computation, vol. 171, no. 2, pp.807–823, 2005. http://dx.doi.org/10.1016/j.amc.2005.01.088
S. Buhmiler and N. Krejic, "A new smoothing quasi-newton method for nonlinearcomplementarity problems," Journal of Computational and AppliedMathematics, vol. 211, no. 2, pp. 141 – 155, 2008. http://dx.doi.org/10.1016/j.cam.2006.11.007
J.-S. Pang and L. Qi, "Nonsmooth equations: Motivation and algorithms,"SIAM Journal on Optimization, vol. 3, no. 3, pp. 443–465, 1993. http://dx.doi.org/10.1137/0803021
C. Kanzow and H. Kleinmichel, "A new class of semismooth newton-typemethods for nonlinear complementarity problems," Comput. Optim. Appl.,vol. 11, no. 3, pp. 227–251, 1998. http://dx.doi.org/10.1023/A:1026424918464
F. E. Arenas A., "Métodos secantes de cambio mínimo," Master's thesis,Universidad del Cauca, 2013.
J. M. Martínez, "Practical quasi-newton methods for solving nonlinear systems,"Journal of Computational and Applied Mathematics, vol. 124, no. 1,pp. 97 – 121, 2000. http://dx.doi.org/10.1016/S0377-0427(00)00434-9
L. Lukšan, "Inexact trust region method for large sparse systems of nonlinearequations," Journal of Optimization Theory and Applications, vol. 81, pp. 569–590, 1994. http://dx.doi.org/10.1007/BF02193101
F. H. Clarke, Optimization and Nonsmooth Analysis. Society for Industrialand Applied Mathematics, 1990. http://dx.doi.org/10.1137/1.9781611971309
T. De Luca, F. Facchinei, and C. Kanzow, "A semismooth equation approachto the solution of nonlinear complementarity problems," Mathematical Programming,vol. 75, pp. 407–439, 1996. http://dx.doi.org/10.1016/S0025-5610(96)00028-7 http://dx.doi.org/10.1007/BF02592192
J. E. Dennis, Jr. and J. J. More, "A characterization of superlinear convergenceand its application to quasi-newton methods," Mathematics of Computation,vol. 28, no. 126, pp. 549–560, 1974. http://dx.doi.org/10.1090/S0025-5718-1974-0343581-1
C. G. Broyden, "A Class of Methods for Solving Nonlinear SimultaneousEquations," Mathematics of Computation, vol. 19, no. 92, pp. 577–593, 1965. http://dx.doi.org/10.1090/S0025-5718-1965-0198670-6
T. F. Coleman, B. S. Garbow, and J. J. More, "Software for estimating sparsejacobian matrices," ACM Trans. Math. Softw., vol. 10, no. 3, pp. 329–345,Aug. 1984. http://dx.doi.org/10.1145/1271.1610
J. M. Martínez, "On the relation between two local convergence theories ofleast change secant update methods," Mathematics of Computation, vol. 59,no. 200, pp. pp. 457–481, 1992.
M. Kojima and S. Shindoh, Extensions of Newton and Quasi-Newton Methodsto Systems of PC 1 Equations, ser. Research reports on informationsciences. Inst. of Technology, Department of Information Sciences, 1986.
L. Mathiesen, "An algorithm based on a sequence of linear complementarityproblems applied to a walrasian equilibrium model: An example," MathematicalProgramming, vol. 37, pp. 1–18, 1987. http://dx.doi.org/10.1007/BF02591680
M. A. Gomes-Ruggiero, J. Martınez, and S. A. Santos, "Solving nonsmoothequations by means of quasi-newton methods with globalization," Recent Advancesin Noonsmooth Optimization, World Scientific Publisher, Singapore,pp. 121–140, 1995.
R. Pérez M., "Algoritmos para complementariedade não lineal e problemasrelacionados," Ph.D. dissertation, IMECC, UNICAM, Campinas, Brazil,Dezembro 1997.
J. M. Martínez, "A quasi-newton method with modification of one columnper iteration," Computing, vol. 33, no. 3-4, pp. 353–362, 1984. http://dx.doi.org/10.1007/BF02242278
J. M. Martínez and M. C. Zambaldi, "An inverse column-updating methodfor solving large scale nonlinear systems of equations," Optimization Methodsand Software, vol. 1, no. 2, pp. 129–140, 1992. http://dx.doi.org/10.1080/10556789208805512