A Singular Values Based Newton Method for Linear Complementarity Problems

Haishan Han, Yuan Li

College of Mathematics, Inner Mongolia University for the Nationalities, Tongliao, China.

DOI: 10.4236/am.2015.614207                

Abstract

The existence condition of the solution of special nonlinear penalized equation of the linear complementarity problems is obtained by the relationship between penalized equations and an absolute value equation. Newton method is used to solve penalized equation, and then the solution of the linear complementarity problems is obtained. We show that the proposed method is globally and superlinearly convergent when the matrix of complementarity problems of its singular values exceeds 0; numerical results show that our proposed method is very effective and efficient.

Keywords

Linear Complementarity Problem, Nonlinear Penalized Equation, Newton Method, Singular Values

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Cottle, R.W., Pang, J.-S. and Stone, R.E. (1992) The Linear Complementarity Problem. Academic, Boston.
[2]	Han, J.Y., Xiu, N.H. and Qi, H.D. (2006) Nonlinear Complementarity Theory and Algorithms (in Chinese). Shanghai Science and Technology Publishing House, Shanghai.
[3]	Outrata, J., Kocvara, M. and Zowe, J. (1998) Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results. Kluwer Academic Publishers, Boston. http://dx.doi.org/10.1007/978-1-4757-2825-5
[4]	Kojima, M., Megiddo, N., Noma, T. and Yoshise, A. (1991) A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Lecture Notes in Computer Science, Springer-Verlag, New York, Berlin. http://dx.doi.org/10.1007/3-540-54509-3
[5]	Friedman, A. (1982) Variational Principles and Free-Boundary Problems. Wiley, New York.
[6]	Elliott, C.M. and Ockendon, J.R. (1982) Weak and Variational Methods for Moving Boun-dary Problems. Pitman Publishing, London.
[7]	Glowinski, R. (1984) Numerical Methods for Nonlinear Variational Problems. Springer-Verlag, New York, Berlin, Heideberg, Tokyo.
[8]	Bensoussan, A. and Lions, J.L. (1982) Applications of Variational Inequalities in Stochastic Control. North-Holland, Amsterdam.
[9]	Wang, S., Yang, X.Q. and Teo, K.L. (2006) Power Penalty Method for a Linear Complementarity Problems Arising from American Option Valuation. Journal of Optimization Theory and Applications, 129, 227-254. http://dx.doi.org/10.1007/s10957-006-9062-3
[10]	Wang, S. and Huang, C.S. (2008) A Power Penalty Method for Solving a Nonlinear Parabolic Complementarity Problem. Nonlinear Analysis, 69, 1125-1137. http://dx.doi.org/10.1016/j.na.2007.06.014
[11]	Wang, S. and Yang, X.Q. (2008) Power Penalty Method for Linear Complementarity Problems. Operations Research Letters, 36, 211-214. http://dx.doi.org/10.1016/j.orl.2007.06.006
[12]	Li, Y., Han, H.S., Li, Y.M. and Wu, M.H. (2009) Convergence Analysis of Power Penalty Method for Three Dimensional Linear Complementarity Problem. Intelligent Information Management Systems and Technologies, 5, 191-198.
[13]	Li, Y., Yang, D.D. and Han, H.S. (2012) Analysis to the Convergence of the Penalty Method for Linear Complementarity Problems. Operations Research and Management Science, 21, 129-134. (In Chinese)
[14]	Li, Y., Han, H.S. and Yang, D.D. (2015) A Penalized Equation Based Generalized Newton Method for Solving Linear Complementarity Problems. Numerical Mathematics: A Journal of Chinese Universities, 37, 53-70. (In Chinese)
[15]	Han, H.S. and Lan-Ying (2015) An Interval Matrix Based Generalized Newton Method for Linear Complementarity Problems. Open Journal of Applied Sciences, 5, 443-449. http://dx.doi.org/10.4236/ojapps.2015.58044
[16]	Geiger, C. and Kanzow, C. (1996) On the Resolution of Monotone Complementarity Problems. Computational Optimization and Applications, 5, 155-173. http://dx.doi.org/10.1007/BF00249054
[17]	Jiang, H.Y. and Qi, L.Q. (1997) A New Nonsmooth Equations Approach to Nonlinear Complementarity Problems. SIAM Journal on Control and Optimization, 35, 178-193. http://dx.doi.org/10.1137/S0363012994276494
[18]	Yong, L.Q., Deng, F. and Chen, T. (2009) An Interior Point Method for Solving Monotone Linear Complementarity Problem. Journal of Mathematics, 29, 681-686. (In Chinese)