An Interval Matrix Based Generalized Newton Method for Linear Complementarity Problems
Affiliation(s)
College of Mathematics, Inner Mongolia University for the Nationalities, Tongliao, China.
College of Mathematics, Inner Mongolia University for the Nationalities, Tongliao, China.
ABSTRACT
The penalty equation of LCP is transformed into the absolute value equation, and then the existence of solutions for the penalty equation is proved by the regularity of the interval matrix. We propose a generalized Newton method for solving the linear complementarity problem with the regular interval matrix based on the nonlinear penalized equation. Further, we prove that this method is convergent. Numerical experiments are presented to show that the generalized Newton method is effective.
The penalty equation of LCP is transformed into the absolute value equation, and then the existence of solutions for the penalty equation is proved by the regularity of the interval matrix. We propose a generalized Newton method for solving the linear complementarity problem with the regular interval matrix based on the nonlinear penalized equation. Further, we prove that this method is convergent. Numerical experiments are presented to show that the generalized Newton method is effective.
KEYWORDS
Linear Complementarity Problem, Nonlinear Penalized Equation, Interval Matrix, Generalized Newton Method
Linear Complementarity Problem, Nonlinear Penalized Equation, Interval Matrix, Generalized Newton Method
Cite this paper
Han, H. and , L. (2015) An Interval Matrix Based Generalized Newton Method for Linear Complementarity Problems. Open Journal of Applied Sciences, 5, 443-449. doi: 10.4236/ojapps.2015.58044.
Han, H. and , L. (2015) An Interval Matrix Based Generalized Newton Method for Linear Complementarity Problems. Open Journal of Applied Sciences, 5, 443-449. doi: 10.4236/ojapps.2015.58044.
References
[1] Cottle, R.W., Pang, J.-S. and Stone, R.E. (1992) The Linear Complementarity Problem. Academic Press, San Diego [2] Glowinski, R. (1984) Numerical Methods for Nonlinear Variational Problems. Springer-Verlag, New York. http://dx.doi.org/10.1007/978-3-662-12613-4 [3] Kanzow, C. (1996) Some Non-Interior Continuation Methods for Linear Complementarity Problem. SIAM Journal on Matrix Analysis and Applications, 17, 851-868.
http://dx.doi.org/10.1137/S0895479894273134 [4] Facchinei, F. and Pang, J.S. (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York. [5] Han, J.Y., Xiu, N.H. and Qi, H.D. (2006) Nonlinear Complementarity Theory and Algorithms. Shanghai Science and Technology Publishing House, Shanghai. (In Chinese) [6] Murty, K.G. (1988) Linear Complementarity, Linear and Nonlinear Programming. Heldermann, Berlin. [7] 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 [8] 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 [9] 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 [10] 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. [11] 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) [12] Rohn, J. (1989) Systems of Linear Interval Equation. Linear Algebra and its Application, 126, 39-78. [13] Bensoussan, A. and Lions, J.L. (1978) Applications of Variational Inequalities in Stochastic Control. North-Holland, Amsterdam, New York, Oxford. [14] Mangasarian, O.L. and Meyer, R.R. (2006) Absolute Value Equations. Linear Algebra and Its Applications, 419, 359-367. http://dx.doi.org/10.1016/j.laa.2006.05.004 [15] 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 [16] Jiang, H.Y. and Qi, L.Q. (1997) A New Nonsmooth Equations Approach to Nonlinear Complementarity Problems. SIAM Journal on Control and Optimization, 45, 178-193.
http://dx.doi.org/10.1137/S0363012994276494 [17] Yong, L.Q., Deng, F.A. and Chen, T. (2009) An Interior Point Method for Solving Monotone Linear Complementarity Problem. Journal of Mathematics, 29, 681-686. (In Chinese)
[1] Cottle, R.W., Pang, J.-S. and Stone, R.E. (1992) The Linear Complementarity Problem. Academic Press, San Diego [2] Glowinski, R. (1984) Numerical Methods for Nonlinear Variational Problems. Springer-Verlag, New York. http://dx.doi.org/10.1007/978-3-662-12613-4 [3] Kanzow, C. (1996) Some Non-Interior Continuation Methods for Linear Complementarity Problem. SIAM Journal on Matrix Analysis and Applications, 17, 851-868.
http://dx.doi.org/10.1137/S0895479894273134 [4] Facchinei, F. and Pang, J.S. (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York. [5] Han, J.Y., Xiu, N.H. and Qi, H.D. (2006) Nonlinear Complementarity Theory and Algorithms. Shanghai Science and Technology Publishing House, Shanghai. (In Chinese) [6] Murty, K.G. (1988) Linear Complementarity, Linear and Nonlinear Programming. Heldermann, Berlin. [7] 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 [8] 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 [9] 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 [10] 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. [11] 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) [12] Rohn, J. (1989) Systems of Linear Interval Equation. Linear Algebra and its Application, 126, 39-78. [13] Bensoussan, A. and Lions, J.L. (1978) Applications of Variational Inequalities in Stochastic Control. North-Holland, Amsterdam, New York, Oxford. [14] Mangasarian, O.L. and Meyer, R.R. (2006) Absolute Value Equations. Linear Algebra and Its Applications, 419, 359-367. http://dx.doi.org/10.1016/j.laa.2006.05.004 [15] 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 [16] Jiang, H.Y. and Qi, L.Q. (1997) A New Nonsmooth Equations Approach to Nonlinear Complementarity Problems. SIAM Journal on Control and Optimization, 45, 178-193.
http://dx.doi.org/10.1137/S0363012994276494 [17] Yong, L.Q., Deng, F.A. and Chen, T. (2009) An Interior Point Method for Solving Monotone Linear Complementarity Problem. Journal of Mathematics, 29, 681-686. (In Chinese)