Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem. (English) Zbl 1168.65027
Authors’ abstract: The linear complementarity problem (LCP) has many applications as, e.g., in the solution of linear and convex quadratic programming, in free boundary value problems of fluid mechanics, etc. In the present work we assume that the coefficient matrix \(M\in \mathbb R^{n\times n}\) of the LCP is symmetric positive definite and we introduce the (optimal) nonstationary extrapolation to improve the convergence rates of the well-known modulus algorithm and block modulus algorithm for its solution. Two illustrative numerical examples show that the (optimal) nonstationary extrapolated block modulus algorithm is far better than all the previous similar algorithms.
Reviewer: Yves Cherruault (Paris)
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
Keywords:
\(P\)-matrices; real symmetric positive definite matrices; iterative schemes; extrapolation; (Block) modulus algorithm; nonlinear conjugate gradient method; linear complementarity problem; convergence; numerical examplesReferences:
| [1] | Ahn, B. H., Solution of nonsymmetric linear complementarity problems by iterative methods, J. Optim. Theory Appl., 33, 175-185 (1981) · Zbl 0422.90079 |
| [2] | Bai, Z.-Z., On the monotone convergence of the matrix multisplitting relaxation methods for 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 linear complementarity problem, SIAM J. Matrix Anal. Appl., 21, 67-78 (1999) · Zbl 0942.65059 |
| [4] | 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 |
| [5] | Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences. Nonnegative Matrices in the Mathematical Sciences, Classics in Applied Mathematics (1994), SIAM: SIAM Philadelphia · Zbl 0815.15016 |
| [6] | Cottle, R. W.; Dantzig, G. B., Complementarity pivot theory of mathematical programming, Linear Algebra Appl., 1, 103-125 (1968) · Zbl 0155.28403 |
| [7] | Cottle, R. W.; Pang, J.-S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press New York · Zbl 0757.90078 |
| [8] | Cryer, C. W., The solution of a quadratic programming problem using systematic over-relaxation, SIAM J. Control, 9, 385-392 (1971) · Zbl 0201.22202 |
| [9] | Cvetković, Ll.; Rapajić, S., How to improve MAOR method convergence area for the linear complementarity problems, Appl. Math. Comput., 162, 577-584 (2005) · Zbl 1132.65052 |
| [10] | Fallatt, S. M.; Tsatsomeros, M. J., On the Cayley transform of positivity classes of matrices, Electron. J. Linear Algebra, 9, 190-196 (2002) · Zbl 1023.15009 |
| [11] | Hadjidimos, A.; Tzoumas, M., On the principle of extrapolation and the Cayley transform, Linear Algebra Appl., 428, 2761-2777 (2008) · Zbl 1153.65031 |
| [12] | Kappel, N. W.; Watson, L. T., Iterative algorithms for the linear complementarity problems, Int. J. Comput. Math., 19, 273-297 (1986) · Zbl 0654.65047 |
| [13] | Koulisianis, M. D.; Papatheodorou, T. S., Improving projected successive overrelaxation method for linear complementarity problems, Appl. Numer. Math., 45, 29-40 (2003) · Zbl 1018.65117 |
| [14] | Lemke, C. E., Bimatrix equilibrium points and mathematical programming, Management Sci., 11, 681-689 (1965) · Zbl 0139.13103 |
| [15] | Mangasarian, O. L., Solution of symmetric linear complementarity problems by iterative methods, J. Optim. Theory Appl., 22, 465-485 (1977) · Zbl 0341.65049 |
| [16] | O.L. Mangasarian, Nonlinear Programming, McGraw Hill, New York, 1969 (Reprint: SIAM Classics in Applied Mathematics 10, Philadelphia, 1994).; O.L. Mangasarian, Nonlinear Programming, McGraw Hill, New York, 1969 (Reprint: SIAM Classics in Applied Mathematics 10, Philadelphia, 1994). |
| [17] | K.G. Murty, Linear Complementarity, Linear and Nolinear Programming. Internet ed., 1997.; K.G. Murty, Linear Complementarity, Linear and Nolinear Programming. Internet ed., 1997. |
| [18] | Pang, J. S., Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem, J. Optim. Theory Appl., 42, 1-17 (1984) · Zbl 0506.90082 |
| [19] | K. Pantazopoulos, Numerical Methods and Software for the Pricing of American Financial Derivatives, Ph.D. Thesis, Department of Computer Sciences, Purdue University, West Lafayette, IN, 1998.; K. Pantazopoulos, Numerical Methods and Software for the Pricing of American Financial Derivatives, Ph.D. Thesis, Department of Computer Sciences, Purdue University, West Lafayette, IN, 1998. |
| [20] | Samelson, H.; Thrall, R. M.; Wesler, O., A partitioning theorem for Euclidean \(n\)-space, Proc. Amer. Math. Soc., 9, 805-807 (1958) · Zbl 0117.37901 |
| [21] | Schäfer, U., A linear complementarity problem with a \(P\)-matrix, SIAM Rev., 46, 189-201 (2004) · Zbl 1133.90402 |
| [22] | Schäfer, U., On the modulus algorithm for the linear complementarity problem, Oper. Res. Lett., 32, 350-354 (2004) · Zbl 1148.90343 |
| [23] | W.M.G. van Bokhoven, Piecewise-linear Modelling and Analysis, Proeschrift, Eindhoven, 1981.; W.M.G. van Bokhoven, Piecewise-linear Modelling and Analysis, Proeschrift, Eindhoven, 1981. |
| [24] | R.S. Varga, Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1962 (also: second ed., Revised and Expanded, Springer, Berlin, 2000).; R.S. Varga, Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1962 (also: second ed., Revised and Expanded, Springer, Berlin, 2000). · Zbl 0133.08602 |
| [25] | Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic Press: Academic Press New York · Zbl 0204.48102 |
| [26] | Yuan, D.; Song, Y., Modified AOR methods for linear complementarity problem, Appl. Math. Comput., 140, 53-67 (2003) · Zbl 1030.65065 |
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.
