A local Jacobian smoothing method for solving Nonlinear Complementarity Problems
Published
May 4, 2020
Almetrics
Dimensions
##plugins.themes.bootstrap3.article.details##
Abstract
In this paper, we present a smoothing of a family of nonlinear complementarity functions and use its properties in combination with the smooth Jacobian strategy to present a new generalized Newton-type algorithm to solve a nonsmooth system of equations equivalent to the Nonlinear Complementarity Problem. In addition, we prove that the algorithm converges locally and q-quadratically, and analyze its numerical performance.
Keywords
nonlinear complementarity problem, complementarity function, generalized Newton method, Q-quadratic convergence
References
[1]Anitescu M, Cremer JF, Potra FA. On the existence of solutions to complementarity formulations of contact problems with friction, Complementarity and Variational Problems: State of the art, SIAM Publications, 12-21, 1997.
[2] Kostreva M. Elasto-hydrodynamic lubrication: A non-linear complementarity problem, International Journal for Numerical Methods in Fluids, 4(4): 377-397, 1984.
doi: 10.1002/fld.1650040407
[3] Chen A, Oh J, Park D, Recker W. Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs, Applied Mathematics and Computation, 217(7): 3020-3031, 2010.
doi: 10.1016/j.amc.2010.08.035
[4] Ferris MC, Pang JS. Engineering and economic applications of complementarity problems, SIAM Review, 39(4): 669-713, 1997.
doi: 10.1137/S0036144595285963
[5] Yong L. Nonlinear complementarity problem and solution methods, Proceedings of the 2010 international conference on Artificial intelligence and computational intelligence: Part I. Springer-Verlag, 461-469, 2010.
[6]Pang J, Qi L. Nonsmooth equations: Motivation and algorithms. SIAM Journal on Optimization, 3(3): 443-465, 1993.
doi: 10.1137/0803021
[7] Kanzow C, Kleinmichel H. A new class of semismooth Newton-type methods for nonlinear complementarity problems. Computational Optimization and Applications, 11(3): 227-251, 1998.
doi: 10.1023/A:1026424918464
[8] Qi L. Convergence analysis of some algorithms for solving nonsmooth equations. Mathematics of Operations Research, 18(1): 227-244, 1993.
[9] Broyden CG, Dennis JE, Moré JJ. On the local and superlinear convergence of quasi-Newton methods. IMA Journal of Applied Mathematics, 12: 223-245, 1973.
doi: 10.1093/imamat/12.3.223
[10] Li DH, Fukushima M. Globally convergent Broyden-like methods for semismooth equations and applications to VIP, NCP and MCP. Annals of Operations Research, 103(1): 71-97, 2001.
doi: 10.1023/A:1012996232707
[11]Lopes VLR, Martínez JM, Pérez R. On the local convergence of quasi-Newton methods for nonlinear complementary problems. Applied Numerical Mathematics, 30(1): 3-22, 1999.
doi: 10.1016/S0168-9274(98)00080-4
[12] Pérez R, Lopes VLR. Recent applications and numerical implementation of quasi-newton methods for solving nonlinear systems of equations. Numerical Algorithms, 35(2), 261-285, 2004.
doi: 10.1023/B:NUMA.0000021762.83420.40
[13]Buhmiler S, Kreji´c N. A new smoothing quasi-Newton method for nonlinear complementarity problems. Journal of Computational and Applied Mathematics, 211(2): 141-155, 2008.
doi: 10.1016/j.cam.2006.11.007
[14]Dennis JE, Schnabel RB. Numerical methods for unconstrained optimization and nonlinear equations. Society for Industrial and Applied Mathematics, 1996.
doi: 10.1137/1.9781611971200.fm
[15] Ma C. A new smoothing quasi-Newton method for nonlinear complementarity problems. Applied Mathematics and Computation, 171(2): 807-823, 2005.
doi: 10.1016/j.amc.2005.01.088
[16] Clarke FH,Necessary Conditions for Nonsmooth Problems in Optimal Control and the Calculus of Variations, Ph.D. thesis, University of Washington, 1973.
doi: 10.1007/978-3-7643-8482-1_11
[17] Kanzow C, Pieper H. Jacobian smoothing methods for nonlinear complementarity problems. SIAM Journal on Optimization, 9(2): 342-373, 1999. doi: 10.1137/S1052623497328781
[18] Clarke FH. Optimization and nonsmooth analysis. Montreal: Society for Industrial and Applied Mathematics, 1990.
doi: 10.1137/1.9781611971309
[19] Qi L. C-differentiability, C-differential operators and generalized Newton methods. Technical Report, School of Mathematics, The University of New South Wales, Sydney, Australia, 1996.
[20] Chen X, Qi L, Sun D. Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Mathematics of Computation, 67(222): 519-540, 1998.
[21] Arenas F, Martínez HJ, Pérez R. Least change secant update methods for nonlinear complementarity problem. Ingeniería y Ciencia, 11(21): 11-36, 2015.
doi: 10.17230/ingciencia.11.21.1
[22] Arias CA, Martínez HJ, Pérez R. A global quasi Newton Algorithm for nonlinear complementarity problems. Pacific journal of Optimization, 13 (1): 1-15, 2017.
[23]Arenas F, Martínez HJ, Pérez, R. Redefinición de la función de complementariedad de Kanzow. Revista de Ciencias, 18(2): 111122, 2014.
[24] Xia Y, Leung H,Wang J. A projection neural network and its application to constrained optimization problems. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 49(4): 447-458, 2002.
doi: 10.1109/81.995659
[2] Kostreva M. Elasto-hydrodynamic lubrication: A non-linear complementarity problem, International Journal for Numerical Methods in Fluids, 4(4): 377-397, 1984.
doi: 10.1002/fld.1650040407
[3] Chen A, Oh J, Park D, Recker W. Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs, Applied Mathematics and Computation, 217(7): 3020-3031, 2010.
doi: 10.1016/j.amc.2010.08.035
[4] Ferris MC, Pang JS. Engineering and economic applications of complementarity problems, SIAM Review, 39(4): 669-713, 1997.
doi: 10.1137/S0036144595285963
[5] Yong L. Nonlinear complementarity problem and solution methods, Proceedings of the 2010 international conference on Artificial intelligence and computational intelligence: Part I. Springer-Verlag, 461-469, 2010.
[6]Pang J, Qi L. Nonsmooth equations: Motivation and algorithms. SIAM Journal on Optimization, 3(3): 443-465, 1993.
doi: 10.1137/0803021
[7] Kanzow C, Kleinmichel H. A new class of semismooth Newton-type methods for nonlinear complementarity problems. Computational Optimization and Applications, 11(3): 227-251, 1998.
doi: 10.1023/A:1026424918464
[8] Qi L. Convergence analysis of some algorithms for solving nonsmooth equations. Mathematics of Operations Research, 18(1): 227-244, 1993.
[9] Broyden CG, Dennis JE, Moré JJ. On the local and superlinear convergence of quasi-Newton methods. IMA Journal of Applied Mathematics, 12: 223-245, 1973.
doi: 10.1093/imamat/12.3.223
[10] Li DH, Fukushima M. Globally convergent Broyden-like methods for semismooth equations and applications to VIP, NCP and MCP. Annals of Operations Research, 103(1): 71-97, 2001.
doi: 10.1023/A:1012996232707
[11]Lopes VLR, Martínez JM, Pérez R. On the local convergence of quasi-Newton methods for nonlinear complementary problems. Applied Numerical Mathematics, 30(1): 3-22, 1999.
doi: 10.1016/S0168-9274(98)00080-4
[12] Pérez R, Lopes VLR. Recent applications and numerical implementation of quasi-newton methods for solving nonlinear systems of equations. Numerical Algorithms, 35(2), 261-285, 2004.
doi: 10.1023/B:NUMA.0000021762.83420.40
[13]Buhmiler S, Kreji´c N. A new smoothing quasi-Newton method for nonlinear complementarity problems. Journal of Computational and Applied Mathematics, 211(2): 141-155, 2008.
doi: 10.1016/j.cam.2006.11.007
[14]Dennis JE, Schnabel RB. Numerical methods for unconstrained optimization and nonlinear equations. Society for Industrial and Applied Mathematics, 1996.
doi: 10.1137/1.9781611971200.fm
[15] Ma C. A new smoothing quasi-Newton method for nonlinear complementarity problems. Applied Mathematics and Computation, 171(2): 807-823, 2005.
doi: 10.1016/j.amc.2005.01.088
[16] Clarke FH,Necessary Conditions for Nonsmooth Problems in Optimal Control and the Calculus of Variations, Ph.D. thesis, University of Washington, 1973.
doi: 10.1007/978-3-7643-8482-1_11
[17] Kanzow C, Pieper H. Jacobian smoothing methods for nonlinear complementarity problems. SIAM Journal on Optimization, 9(2): 342-373, 1999. doi: 10.1137/S1052623497328781
[18] Clarke FH. Optimization and nonsmooth analysis. Montreal: Society for Industrial and Applied Mathematics, 1990.
doi: 10.1137/1.9781611971309
[19] Qi L. C-differentiability, C-differential operators and generalized Newton methods. Technical Report, School of Mathematics, The University of New South Wales, Sydney, Australia, 1996.
[20] Chen X, Qi L, Sun D. Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Mathematics of Computation, 67(222): 519-540, 1998.
[21] Arenas F, Martínez HJ, Pérez R. Least change secant update methods for nonlinear complementarity problem. Ingeniería y Ciencia, 11(21): 11-36, 2015.
doi: 10.17230/ingciencia.11.21.1
[22] Arias CA, Martínez HJ, Pérez R. A global quasi Newton Algorithm for nonlinear complementarity problems. Pacific journal of Optimization, 13 (1): 1-15, 2017.
[23]Arenas F, Martínez HJ, Pérez, R. Redefinición de la función de complementariedad de Kanzow. Revista de Ciencias, 18(2): 111122, 2014.
[24] Xia Y, Leung H,Wang J. A projection neural network and its application to constrained optimization problems. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 49(4): 447-458, 2002.
doi: 10.1109/81.995659
How to Cite
Arenas, F. E., Martínez, H. J., & Pérez, R. (2020). A local Jacobian smoothing method for solving Nonlinear Complementarity Problems. Universitas Scientiarum, 25(1), 149–174. https://doi.org/10.11144/Javeriana.SC25-1.aljs
Issue
Section
Mathematics and Statistics