Keywords
complementarity function
generalized Newton method
Q-quadratic convergence
How to Cite
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.
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.
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
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
Ferris MC, Pang JS. Engineering and economic applications of complementarity problems, SIAM Review, 39(4): 669-713, 1997.
doi: 10.1137/S0036144595285963
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.
Pang J, Qi L. Nonsmooth equations: Motivation and algorithms. SIAM Journal on Optimization, 3(3): 443-465, 1993.
doi: 10.1137/0803021
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
Qi L. Convergence analysis of some algorithms for solving nonsmooth equations. Mathematics of Operations Research, 18(1): 227-244, 1993.
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
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
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
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
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
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
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
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
Kanzow C, Pieper H. Jacobian smoothing methods for nonlinear complementarity problems. SIAM Journal on Optimization, 9(2): 342-373, 1999. doi: 10.1137/S1052623497328781
Clarke FH. Optimization and nonsmooth analysis. Montreal: Society for Industrial and Applied Mathematics, 1990.
doi: 10.1137/1.9781611971309
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.
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.
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
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.
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.
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
Univ. Sci. is registered under a Creative Commons Attribution 4.0 International Public License. Thus, this work may be reproduced, distributed, and publicly shared in digital format, as long as the names of the authors and Pontificia Universidad Javeriana are acknowledged. Others are allowed to quote, adapt, transform, auto-archive, republish, and create based on this material, for any purpose (even commercial ones), provided the authorship is duly acknowledged, a link to the original work is provided, and it is specified if changes have been made. Pontificia Universidad Javeriana does not hold the rights of published works and the authors are solely responsible for the contents of their works; they keep the moral, intellectual, privacy, and publicity rights. Approving the intervention of the work (review, copy-editing, translation, layout) and the following outreach, are granted through an use license and not through an assignment of rights. This means the journal and Pontificia Universidad Javeriana cannot be held responsible for any ethical malpractice by the authors. As a consequence of the protection granted by the use license, the journal is not required to publish recantations or modify information already published, unless the errata stems from the editorial management process. Publishing contents in this journal does not generate royalties for contributors.