The reduced order method for solving the linear complementarity problem with an \(M\)-matrix. (English) Zbl 1497.90202
Summary: In this paper, by seeking the zero and the positive entry positions of the solution, we provide a direct method, called the reduced order method, for solving the linear complementarity problem with an \(M\)-matrix. By this method, the linear complementarity problem is transformed into a low order linear complementarity problem with some low order linear equations and the solution is constructed by the solution of the low order linear complementarity problem and the solutions of these low order linear equations in the transformations. In order to show the accuracy and the effectiveness of the method, the corresponding numerical experiments are performed.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 65K05 | Numerical mathematical programming methods |
| 90C20 | Quadratic programming |
| 65K10 | Numerical optimization and variational techniques |
References:
| [1] | Cottle, RW; Pang, JS; Stone, RE, The linear complementarity problem (1992), New York: Academic Press, New York · Zbl 0757.90078 |
| [2] | Ferris, MC; Pang, JS, Complementarity and variational problems (1997), Pennsylvania: Philadephia, Pennsylvania · Zbl 0891.90158 |
| [3] | Lemke, CE, Bimatrix equilibrium points and mathematical programming, Manag. Sci., 11, 7, 681-689 (1965) · Zbl 0139.13103 · doi:10.1287/mnsc.11.7.681 |
| [4] | Joaquim, JJ; Fernanda, MP, A block principal pivoting algorithm for larger-scale structure linear complementarity problems, Comput. Oper. Res., 5, 21, 581-596 (1994) · Zbl 0802.90106 |
| [5] | Murty, KG, Linear Complement. (1988), Heldermann: Linear and Nonlinear Programming, Heldermann · Zbl 0634.90037 |
| [6] | Shi, XJ; Yang, L.; Huang, ZH, A fixed point method for the linear complementarity problem arising from American option pricing, Acta Math. Appl. Sin., 4, 32, 921-932 (2016) · Zbl 1358.90141 · doi:10.1007/s10255-016-0613-6 |
| [7] | Bai, ZZ, Modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 17, 6, 917-933 (2010) · Zbl 1240.65181 · doi:10.1002/nla.680 |
| [8] | Ahn, BH, Iterative methods for linear complementarity problems with upperbounds on primary variables, Math. Program., 26, 3, 295-315 (1983) · Zbl 0506.90081 · doi:10.1007/BF02591868 |
| [9] | Murty, KG, On the number of sulutions to the complementarity problem and spanning properties of complementary cones, Linear Algebra Appl., 5, 65-108 (1972) · Zbl 0241.90046 · doi:10.1016/0024-3795(72)90019-5 |
| [10] | Li, W., A general modulus-based matrix splitting method for linear complementarity problems of \(H\)-matrices, Appl. Math. Lett., 26, 12, 1159-1164 (2013) · Zbl 1311.65071 · doi:10.1016/j.aml.2013.06.015 |
| [11] | Hadjidimos, A.; Zhang, LL, Comparison of three classes of algorithms for the solution of the linear complementarity problem with an \(H+\)-matrix, J. Comput. Appl. Math., 336, 175-191 (2018) · Zbl 1382.65175 · doi:10.1016/j.cam.2017.12.028 |
| [12] | Cottle, Richard W., The principal pivoting method revisited, Math. Program., 48, 1-3, 369-385 (1990) · Zbl 0716.90095 · doi:10.1007/BF01582264 |
| [13] | Zheng, H.; Li, W.; Qu, W., A non-modulus linear method for solving the linear complementarity problem, Linear Algebra Appl., 495, 38-50 (2016) · Zbl 1333.65062 · doi:10.1016/j.laa.2016.01.032 |
| [14] | Bai, ZZ; Evans, DJ, Chaotic iterative methods for the linear complementarity problems, J. Comput. Appl. Math., 96, 2, 127-138 (1998) · Zbl 0927.65079 · doi:10.1016/S0377-0427(98)00111-3 |
| [15] | Chandrasekarn, R., A special case of the complementary pivot problem, Oper. Res., 7, 263-268 (1970) |
| [16] | Cottle, Richard W.; Sacher, Richard S., On the solution of large, structured linear complementarity problems: the tridiagonal case, Math. Optim., 3, 4, 321-340 (1976) · Zbl 0375.90048 · doi:10.1007/BF01448184 |
| [17] | Dong, JL; Jiang, MQ, A modified modulus method for symmetric positive-definite linear complementarity problems, Numer. Linear Algebra Appl., 16, 2, 129-143 (2010) · Zbl 1224.65152 · doi:10.1002/nla.609 |
| [18] | Bai, ZZ; Dong, JL, A modified damped Newton method for linear complementarity problems, Numer. Algorithms, 42, 3-4, 207-228 (2006) · Zbl 1106.65052 · doi:10.1007/s11075-006-9028-4 |
| [19] | Graves, RL, A principal pivoting simplex algorithm for linear and quadratic programming, Oper. Res., 15, 3, 482-494 (1967) · Zbl 0154.19604 · doi:10.1287/opre.15.3.482 |
| [20] | Hadjidimos, A.; Tzoumas, M., Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem, Linear Algebra Appl., 431, 1, 197-210 (2009) · Zbl 1168.65027 · doi:10.1016/j.laa.2009.02.024 |
| [21] | Hadjidimos, A.; Tzoumas, M., The solution of the linear complementarity problem by the matrix analogue of the accelerated overrelaxation iterative method, Numer. Algorithms., 73, 3, 665-684 (2016) · Zbl 1353.65054 · doi:10.1007/s11075-016-0112-0 |
| [22] | Jiang, YJ; Zeng, JP, Direct algorithm for the solution of two-sided obstacle problems with M-matrix, Numer. Linear Algebra Appl., 18, 167-173 (2011) · Zbl 1249.65136 · doi:10.1002/nla.726 |
| [23] | Wu, SL; Li, CX, Two-sweep modulus-based matrix splitting iteration methods for linear complementarity problems, J. Comput. Appl. Math., 302, 327-339 (2016) · Zbl 1334.90179 · doi:10.1016/j.cam.2016.02.011 |
| [24] | Zhou, SZ, A direct method for the linear complementarity problem, J. Comput. Math., 8, 2, 178-182 (1990) · Zbl 0725.65065 |
| [25] | Zhang, L.; Hu, XY, On the direct method for linear complementarity problem, Math. Numer. Sin., 16, 1, 59-64 (1994) · Zbl 0925.65111 |
| [26] | Zeng, JP; Jiang, YJ, Direct algorithms to solve the two-sided obstacle problem for an \(M\)-matrix, Numer. Linear Algebra Appl., 13, 7, 543-551 (2006) · Zbl 1174.65434 · doi:10.1002/nla.487 |
| [27] | Chen, XJ; Xiang, SH, Computation of error bounds for \(P\)-matrix linear complementarity problems, Math. Program., 106, 3, 513-525 (2006) · Zbl 1134.90043 · doi:10.1007/s10107-005-0645-9 |
| [28] | Mathis, Roy; J. S., Pang, Error bounds for the linear complementarity problem with a \(P\)-matrix, Linear Algebra Appl., 132, 123-136 (1990) · Zbl 0711.90077 · doi:10.1016/0024-3795(90)90058-K |
| [29] | Chen, X.; Xiang, S., Perturbation bounds of \(P\)-matrix linear complementarity problems, SIAM J. Optim., 18, 4, 1250-1265 (2007) · Zbl 1172.90018 · doi:10.1137/060653019 |
| [30] | Garcia-Esnaola, M.; Pena, JM, A comparison of error bounds for linear complementarity problems of \(H\)-matrices, Linear Algebra Appl., 433, 5, 956-964 (2010) · Zbl 1195.65077 · doi:10.1016/j.laa.2010.04.024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
