Least Change Secant Update Methods for Nonlinear Complementarity Problem
Main Article Content
Keywords
Nonsmooth systems, Nonlinear Complementarity Problems, generalized Jacobians, Quasi-Newton methods, Least Change Secant Update Methods, local convergence, superlinear convergence.
Abstract
In this work, we introduce a family of Least Change Secant Update Methods for solving Nonlinear Complementarity Problems based on its reformulation as a nonsmooth system using the one-parametric class of nonlinear complementarity functions introduced by Kanzow and Kleinmichel. We prove local and superlinear convergence for the algorithms. Some numerical experiments show a good performance of this algorithm.
MSC: 90C30, 90C33, 90C53
Downloads
Download data is not yet available.
References
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