A block principal pivoting algorithm for large-scale strictly monotone linear complementarity problems. (English) Zbl 0802.90106
Summary: A finite block principal pivoting algorithm for the solution of strictly monotone linear complementarity problems is introduced. The algorithm combines a fast block strategy with a single principal pivoting technique that enables finite convergence. Computational experience with large- scale linear complementarity problems illustrates the efficiency of the procedure.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C06 | Large-scale problems in mathematical programming |
References:
| [1] | Harker, P. T.; Pang, J. S., Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Mathl Program., 48, 161-220 (1990) · Zbl 0734.90098 |
| [2] | Murty, K. G., Linear Complementarity, Linear and Nonlinear Programming (1988), Heldermann: Heldermann Berlin · Zbl 0634.90037 |
| [3] | Pang, J. S.; Kaneko, I.; Hallman, W. P., On the solution of some (parametric) linear complementarity problems with applications to portfolio analysis, structural engineering and graduation, Mathl Program., 16, 325-347 (1979) · Zbl 0399.90092 |
| [4] | Pang, J. S.; Lee, S. C., A parametric linear complementarity technique for the computation of equilibrium in a single commodity spatial model, Mathl Program., 20, 81-102 (1981) · Zbl 0441.90106 |
| [5] | Glowinski, R., Finite elements and variational inequalities, (MRC Technical Report 1885 (1978), Mathematics Research Center, University of Wisconsin-Madison) · Zbl 0442.65056 |
| [6] | Gill, P. E.; Murray, W.; Wright, M. H., Practical Optimization (1981), Academic Press: Academic Press New York · Zbl 0503.90062 |
| [7] | Josephy, N. H., Newton’s method for generalized equations, (Technical Report 1966 (1979), Mathematics Research Center, University of Wisconsin-Madison) |
| [8] | Cottle, R. W.; Pang, J. S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press New York · Zbl 0757.90078 |
| [9] | Ahn, B. H., Iterative methods for linear complementarity with upper-bounds on primary variables, Mathl Program., 26, 295-315 (1983) · Zbl 0506.90081 |
| [10] | Graves, R. L., A principal pivoting simplex algorithm for linear and quadratic programming, Ops Res., 15, 482-494 (1967) · Zbl 0154.19604 |
| [11] | Keller, E. L., The general quadratic optimization problem, Mathl Program., 5, 311-337 (1973) · Zbl 0276.90044 |
| [12] | Murty, K. G., Note on a Bard-type scheme for solving the complementarity problem, Opsearch, 11, 123-130 (1974) |
| [13] | Júdice, J. J.; Pires, F. M., Bard-type methods for the linear complementarity problem with symmetric positive matrices, IMA J. maths appl. business Indust., 2, 51-68 (1988/1989) · Zbl 0674.90091 |
| [14] | Kostreva, M., Block pivot methods for solving the complementarity problem, Linear algebra Applic., 21, 207-215 (1978) · Zbl 0395.65032 |
| [15] | Júdice, J. J.; Pires, F. M., A Bard-type method for a generalized linear complementarity problem with a nonsingular M-matrix, Nav. Res. Logist., 37, 279-297 (1990) · Zbl 0699.90089 |
| [16] | Júdice, J. J.; Pires, F. M., A basic-set algorithm for a generalized linear complementarity problem, J. optimiz. theory and Appl., 74, 391-412 (1992) · Zbl 0795.90074 |
| [17] | Júdice, J. J.; Pires, F. M., A polynomial method for a generalized linear complementarity problem with a nonsingular M-matrix, IMA J. maths appl. business Indust., 4, 211-224 (1992) · Zbl 0773.90079 |
| [18] | Júdice, J. J.; Pires, F. M., Direct methods for convex quadratic programs subject to box constraints, Invest. Opl, 9, 23-56 (1989) |
| [19] | Pang, J. S., A new and efficient algorithm for a class of portfolio selection problems, Ops Res., 28, 754-767 (1980) · Zbl 0451.90011 |
| [20] | Pang, J. S., On a class of least-element complementarity problems, Mathl Program., 16, 111-126 (1979) · Zbl 0393.90092 |
| [21] | Coleman, T. F.; Hulbert, L. A., A direct active set algorithm for large sparse quadratic programs with bounds, Mathl Program., 45, 373-406 (1989) · Zbl 0691.90070 |
| [22] | Jùdice, J. J.; Pires, F. M., Solution of large-scale strictly convex linear complementarity problems, Invest. Opl, 11, 31-51 (1991) · Zbl 0674.90091 |
| [23] | Moré, J. J.; Toraldo, G., On the solution of large quadratic programming problems with bound constraints, SIAM J. Optimiz., 1, 93-113 (1991) · Zbl 0752.90053 |
| [24] | Yang, E. K.; Tolle, J. W., A class of methods for solving large convex quadratic programs subject to box constraints (1985), Management Sciences Department, University of Massachusetts at Boston, Working paper |
| [25] | Fletcher, R.; Jackson, M. P., Minimization of a quadratic function subject only to upper and lower bounds, J. Inst. maths and Appl., 14, 159-174 (1974) · Zbl 0301.90032 |
| [26] | O’Leary, D. P., A generalized conjugate-gradient algorithm for solving a class of quadratic programming problems, Linear algebra Applic., 34, 371-399 (1980) · Zbl 0464.65039 |
| [27] | Cryer, C. W., The solution of a quadratic programming problem using systematic overrelaxation, J. SIAM Control, 9, 385-392 (1971) · Zbl 0201.22202 |
| [28] | Harker, P. T.; Pang, J. S., A damped-Newton method for the linear complementarity problem, Lectures appl. Maths, 26, 265-284 (1990) · Zbl 0699.65054 |
| [29] | Kojima, M.; Megiddo, N.; Noma, T.; Yoshise, A., A unified approach to interior point algorithms for linear complenentarity problems: a summary, Ops Res. Lett., 10, 247-254 (1991) · Zbl 0745.90069 |
| [30] | Kojima, M.; Mizuno, S.; Yoshise, A., A polynomal-time algorithm for a class of linear complementarity problems, Mathl Program., 44, 1-26 (1989) · Zbl 0676.90087 |
| [31] | Pardalos, P.; Ye, Y.; Han, C. G., An interior-point algorithm for large-scale quadratic problems subject to box constraints, (Lecture Notes in Control and Information, 144 (1990), Springer: Springer Berlin), 413-422 · Zbl 0725.90073 |
| [32] | Pardalos, P.; Ye, Y.; Han, C. G.; Kalinski, J., Solution of P-matrix linear complementarity problems using a potential reducting algorithm, (Technical report CS-90-32 (1990), Department of Computer Science, The Pennsylvania State University) |
| [33] | Duff, I. S.; Erisman, A. M.; Reid, J. R., Direct Methods for Sparse Matrices (1986), Clarendon Press: Clarendon Press Oxford · Zbl 0604.65011 |
| [34] | Duff, I. S.; Grimes, R. G.; Lewis, J. G., Sparse matrix text problems, ACM Trans. mathl Softw., 15, 1-14 (1989) · Zbl 0667.65040 |
| [35] | Ramarao, B.; Shetty, C. M., Application of disjunctive programming to the linear complementarity problem, Naval Res. Logist. Q., 31, 589-600 (1984) · Zbl 0559.90088 |
| [36] | George, A.; Liu, J. W.H., Computer Solution of Large Positive Definite Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0516.65010 |
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.
