A non-modulus linear method for solving the linear complementarity problem. (English) Zbl 1333.65062
Summary: In this paper, a non-modulus linear method for solving the linear complementarity problem is established by using the sign patterns of the solution of the equivalent modulus equation. In the proposed method the efficient numerical algorithms for solving the linear equations can be applied to the large sparse problems. Numerical examples show that the new method is valid.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C06 | Large-scale problems in mathematical programming |
Keywords:
linear complementarity problem; modulus-based method; sign pattern; algorithm; large sparse problems; numerical examplesReferences:
| [1] | Ahn, B. H., Iterative methods for linear complementarity problems with upper-bounds on primary variables, Math. Program., 26, 295-315 (1983) · Zbl 0506.90081 |
| [2] | Bai, Z.-Z., On the monotone convergence of matrix multisplitting relaxation methods for the linear complementarity problem, IMA J. Numer. Anal., 18, 509-518 (1998) · Zbl 0914.65072 |
| [3] | Bai, Z.-Z., On the convergence of the multisplitting methods for the linear complementarity problem, SIAM J. Matrix Anal. Appl., 21, 67-78 (1999) · Zbl 0942.65059 |
| [4] | Bai, Z.-Z., Modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 17, 917-933 (2010) · Zbl 1240.65181 |
| [5] | Bai, Z.-Z.; Dong, J.-L., A modified damped Newton method for linear complementarity problems, Numer. Algorithms, 42, 207-228 (2006) · Zbl 1106.65052 |
| [6] | Bai, Z.-Z.; Evans, D. J., Matrix multisplitting relaxation methods for linear complementarity problems, Int. J. Comput. Math., 63, 309-326 (1997) · Zbl 0876.90086 |
| [7] | Bai, Z.-Z.; Evans, D. J., Matrix multisplitting methods with applications to linear complementarity problems: parallel synchronous and chaotic methods, reseaux et systemes repartis, Calc. Parallèles, 13, 125-154 (2001) |
| [8] | Bai, Z.-Z.; Evans, D. J., Matrix multisplitting methods with applications to linear complementarity problems: parallel asynchronous methods, Int. J. Comput. Math., 79, 2, 205-232 (2002) · Zbl 1011.65033 |
| [9] | Bai, Z.-Z.; Zhang, L.-L., Modulus-based synchronous multisplitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 20, 425-439 (2013) · Zbl 1313.65131 |
| [10] | Bai, Z.-Z.; Zhang, L.-L., Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems, Numer. Algorithms, 62, 59-77 (2013) · Zbl 1259.65088 |
| [11] | Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences (1994), SIAM Publisher: SIAM Publisher Philadelphia · Zbl 0815.15016 |
| [12] | van Bokhoven, W. M.G., Piecewise-Linear Modelling and Analysis (1981), Proefschrift: Proefschrift Eindhoven |
| [13] | Cottle, R. W.; Pang, J.-S.; Stone, R. E., The Linear Complementarity Problem (2009), SIAM Publisher: SIAM Publisher Philadelphia · Zbl 1192.90001 |
| [14] | Ferris, M. C.; Pang, J.-S., Engineering and economic applications of complementarity problems, SIAM Rev., 39, 669-713 (1997) · Zbl 0891.90158 |
| [15] | Harker, P. T.; Pang, J.-S., A damped-Newton method for the linear complementarity problem, (Allgower, G.; Georg, K., Computational Solution of Nonlinear Systems of Equations. Computational Solution of Nonlinear Systems of Equations, Lectures in Applied Mathematics, vol. 26 (1990), American Mathematical Society: American Mathematical Society Providence, RI), 265-284 · Zbl 0699.65054 |
| [16] | Hestenes, M. R.; Steifel, E., Methods of conjugate gradient for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901 |
| [17] | Kakimura, N., Sign-solvable linear complementarity problems, Linear Algebra Appl., 429, 606-616 (2008) · Zbl 1145.90094 |
| [18] | Li, W., A general modulus-based matrix splitting method for linear complementarity problems of \(H\)-matrices, Appl. Math. Lett., 26, 1159-1164 (2013) · Zbl 1311.65071 |
| [20] | McShane, K., Superlinearly convergent \(O(\sqrt{n} L)\)-iteration interior-point algorithms for LP and the monotone LCP, SIAM J. Optim., 4, 247-261 (1994) · Zbl 0822.90102 |
| [21] | Monteiro, R.; Wright, S., Local convergence of interior-point algorithms for degenerate monotone LCP, Comput. Optim. Appl., 3, 131-155 (1994) · Zbl 0801.90110 |
| [22] | Qi, L.-Q.; Sun, J., A nonsmooth version of Newton’s method, Math. Program., 58, 353-367 (1993) · Zbl 0780.90090 |
| [23] | Saad, Y.; Schultz, M., GMRES a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7, 856-869 (1986) · Zbl 0599.65018 |
| [24] | Wright, S., A path-following interior-point algorithm for linear and quadratic problems, Ann. Oper. Res., 62, 103-130 (1996) · Zbl 0848.90114 |
| [25] | Wright, S.; Zhang, Y., A superquadratic infeasible-interior-point method for linear complementarity problems, Math. Program., 73, 269-289 (1996) · Zbl 0852.90124 |
| [26] | Ye, Y.; Anstreicher, K., On quadratic and \(O(\sqrt{n} L)\) convergence of a predictor-corrector algorithm for LCP, Math. Program., 62, 537-551 (1993) · Zbl 0799.90111 |
| [27] | Zhang, L.-L., Two-step modulus based matrix splitting iteration for linear complementarity problems, Numer. Algorithms, 57, 83-99 (2011) · Zbl 1219.65057 |
| [28] | Zhang, L.-L., Two-stage multisplitting iteration methods using modulus-based matrix splitting as inner iteration for linear complementarity problems, J. Optim. Theory Appl., 160, 189-203 (2014) · Zbl 1334.90181 |
| [29] | Zhang, L.-L., Two-step modulus-based synchronous multisplitting iteration methods for linear complementarity problems, J. Comput. Math., 33, 100-112 (2015) · Zbl 1340.65124 |
| [30] | Zhang, L.-L.; Ren, Z.-R., Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems, Appl. Math. Lett., 26, 638-642 (2013) · Zbl 1266.65097 |
| [31] | Zheng, H.; Li, W., The modulus-based nonsmooth Newton’s method for solving linear complementarity problems, J. Comput. Appl. Math., 288, 116-126 (2015) · Zbl 1320.65096 |
| [33] | Zheng, N.; Yin, J.-F., Accelerated modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Algorithms, 64, 245-262 (2013) · Zbl 1273.65075 |
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.
