General fixed-point method for solving the linear complementarity problem

Xi-Ming Fang; Xi-Ming Fang

doi:10.3934/math.2021691

AIMS Mathematics

2021, Volume 6, Issue 11: 11904-11920. doi: 10.3934/math.2021691

Previous Article Next Article

Research article

General fixed-point method for solving the linear complementarity problem

Xi-Ming Fang ^,

Department of Mathematics and Statistics, Zhaoqing University, Zhaoqing 526000, P. R. China

Received: 07 November 2020 Accepted: 25 May 2021 Published: 16 August 2021
MSC : 65F10, 65F50

In this paper, we consider numerical methods for the linear complementarity problem (LCP). By introducing a positive diagonal parameter matrix, the LCP is transformed into an equivalent fixed-point equation and the equivalence is proved. Based on such equation, the general fixed-point (GFP) method with two cases are proposed and analyzed when the system matrix is a $ P $-matrix. In addition, we provide several concrete sufficient conditions for the proposed method when the system matrix is a symmetric positive definite matrix or an $ H_{+} $-matrix. Meanwhile, we discuss the optimal case for the proposed method. The numerical experiments show that the GFP method is effective and practical.
- linear complementarity problem,
- solution,
- iterative method,
- algorithm,
- convergence
Citation: Xi-Ming Fang. General fixed-point method for solving the linear complementarity problem[J]. AIMS Mathematics, 2021, 6(11): 11904-11920. doi: 10.3934/math.2021691

Related Papers:

Abstract

In this paper, we consider numerical methods for the linear complementarity problem (LCP). By introducing a positive diagonal parameter matrix, the LCP is transformed into an equivalent fixed-point equation and the equivalence is proved. Based on such equation, the general fixed-point (GFP) method with two cases are proposed and analyzed when the system matrix is a $ P $-matrix. In addition, we provide several concrete sufficient conditions for the proposed method when the system matrix is a symmetric positive definite matrix or an $ H_{+} $-matrix. Meanwhile, we discuss the optimal case for the proposed method. The numerical experiments show that the GFP method is effective and practical.

References

[1]	S. R. Sacher, On the solution of large, structured linear complementarity problems: The block partitioned case, Appl. Math. Optim., 4 (1977), 347–363. doi: 10.1007/BF01442149
[2]	Z. Z. Bai, Modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 17 (2010), 917–933. doi: 10.1002/nla.680
[3]	C. W. Cryer, The solution of a quadratic programming problem using systematic over-relaxation, SIAM J. Control Optim., 9 (1971), 385–392. doi: 10.1137/0309028
[4]	X. J. Shi, L. Yang, Z. H. Huang, A fixed-point method for the linear complementarity problem arising from American option pricing, Acta Math. Appl. Sinica(Eglish Ser.), 32 (2016), 921–932. doi: 10.1007/s10255-016-0613-6
[5]	W. Li, A general modulus-based matrix splitting method for linear complementarity problems of $H$-matrices, Appl. Math. Lett., 26 (2013), 1159–1164. doi: 10.1016/j.aml.2013.06.015
[6]	C. Zhang, X. J. Chen, Smoothing projected gradient method and its application to stochastic linear complementarity problems, SIAM J. Optim., 20 (2009), 627–649. doi: 10.1137/070702187
[7]	P. H. Calamai, J. J. Mor, Projected gradient methods for linearly constrained problems, Math. Program., 39 (1987), 93–116. doi: 10.1007/BF02592073
[8]	H. Liu, Y. Huang, X. Li, Partial projected Newton method for a class of stochastic linear complementarity problems, Numer. Algorithms, 58 (2011), 593–618. doi: 10.1007/s11075-011-9472-7
[9]	M. D. Koulisianis, T. S. Papatheodorou, Improving projected successive overrelaxation method for linear complementarity problems, Appl. Numer. Math., 45 (2003), 29–40. doi: 10.1016/S0168-9274(02)00233-7
[10]	Y. C. Cheng, On the gradient-projection method for solving the nonsymmetric linear complementarity problem, J. Optimiz. Theory App., 43 (1984), 527–541. doi: 10.1007/BF00935004
[11]	H. Liu, Y. Huang, X. Li, New reformulation and feasible semismooth Newton method for a class of stochastic linear complementarity problems, Appl. Math. Comput., 217 (2011), 9723–9740.
[12]	B. S. He, A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming, Appl. Math. Optim., 25 (1992), 247–262. doi: 10.1007/BF01182323
[13]	I. M. Sharaf, A projection algorithm for positive definite linear complementarity problems with applications, Int. J. Manag. Sci. Eng., 12 (2017), 141–147.
[14]	A. Hadjidimos, M. Tzoumas, Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem, Linear Algebra Appl., 43 (2009), 197–210.
[15]	S. L. Wu, C. X. Li, Two-sweep modulus-based matrix splitting iteration methods for linear complementarity problems, J. Comput. Appl. Math., 302 (2016), 327–339. doi: 10.1016/j.cam.2016.02.011
[16]	L. L. Zhang, Two-step modulus-based matrix splitting iteration method for linear complementarity problems, Numer. Algorithms, 57 (2011), 83–99. doi: 10.1007/s11075-010-9416-7
[17]	N. Zheng, J. F. Yin, Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem, Numer. Algorithms, 64 (2013), 245–262. doi: 10.1007/s11075-012-9664-9
[18]	S. M. Liu, H. Zheng, W. Li, A general accelerated modulus-based matrix splitting iteration method for solving linear complementarity problems, Calcolo, 53 (2016), 189–199. doi: 10.1007/s10092-015-0143-2
[19]	B. L. Wen, H. Zheng, W. Li, X. F. Peng, The relaxation modulus-based matrix splitting iteration method for solving linear complementarity problems of positive definite matrices, Appl. Math. Comput., 321 (2018), 349–357.
[20]	A. Hadjidimos, M. Lapidakis, M. Tzoumas, On iterative solution for linear complementarity problem with an $H_+$-matrix, SIAM J. Matrix Anal. Appl., 33 (2012), 97–110. doi: 10.1137/100811222
[21]	H. Zheng, S. Vong, On convergence of the modulus-based matrix splitting iteration method for horizontal linear complementarity problems of $H_+$-matrices, Appl. Math. Comput., 369 (2020), 124–890.
[22]	H. Zheng, W. Li, S. W. Vong, A relaxation modulus-based matrix splitting iteration method for solving linear complementarity problems, Numer. Algorithms, 74 (2017), 137–152. doi: 10.1007/s11075-016-0142-7
[23]	H. Zheng, W. Li, W. Qu, A non-modulus linear method for solving the linear complementarity problem, Linear Algebra Appl., 495 (2016), 38–50. doi: 10.1016/j.laa.2016.01.032
[24]	H. Zheng, S. Vong, A two-step modulus-based matrix splitting iteration method for horizontal linear complementarity problems, Numer. Algorithms, 86 (2021), 1791–1810. doi: 10.1007/s11075-020-00954-1
[25]	A. Berman, R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Philadelphia: SIAM Publisher, 1994.
[26]	Z. Z. Bai, On the convergence of the multisplitting methods for the linear complementarity problem, SIAM J. Matrix Anal. Appl., 21 (2006), 67–78.
[27]	G. Csordas, R. S. Varga, Comparisons of regular splittings of matrices, Numer. Math., 44 (1984), 23–35. doi: 10.1007/BF01389752
[28]	A. Frommer, D. B. Szyld, $H$-splittings and two-stage iterative methods, Numer. Math., 63 (1992), 345–356. doi: 10.1007/BF01385865
[29]	K. G. Murty, On the number of solutions to the complementarity problem and spanning properties of complementary cones, Linear Algebra Appl., 5 (1972), 65–108. doi: 10.1016/0024-3795(72)90019-5

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)