×

A new class of preconditioners for large-scale linear systems from interior point methods for linear programming. (English) Zbl 1071.65088

The authors offer a class of preconditioners for the augmented linear systems arising from the primal-dual interior point methods. It is claimed that the proposed preconditioners are suitable for problems where the Cholesky factorization has a large amount of nonzeros, even the original normal system is sparse.

MSC:

65K05 Numerical mathematical programming methods
90C05 Linear programming
90C51 Interior-point methods
90C06 Large-scale problems in mathematical programming
65F35 Numerical computation of matrix norms, conditioning, scaling

Software:

QAPLIB; PCx; JDQZ; MA57; KORBX
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Adler, I.; Resende, M. G.C.; Veiga, G.; Karmarkar, N., An implementation of Karmarkar’s algorithm for linear programming, Math. Program., 44, 297-335 (1989) · Zbl 0682.90061
[2] Andersen, E. D., Finding all linearly dependent rows in large-scale linear programming, Optim. Methods Softw., 6, 219-227 (1995)
[3] Bergamaschi, L.; Gondzio, J.; Zilli, G., Preconditioning indefinite systems in interior point methods for optimization, Comput. Optim. Appl., 28, 149-171 (2004) · Zbl 1056.90137
[4] Björck, A., Numerical Methods for Least Squares Problems (1996), SIAM Publications, SIAM: SIAM Publications, SIAM Philadelphia, PA, USA · Zbl 0847.65023
[5] Braess, D.; Peisker, P., On the numerical solution of the biharmonic equation and the role of squaring matrices, IMA J. Numer. Anal., 6, 393-404 (1986) · Zbl 0616.65108
[6] Bunch, J. R.; Parlett, B. N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8, 639-655 (1971) · Zbl 0199.49802
[7] Burkard, R. S.; Karisch, S.; Rendl, F., QAPLIB—A quadratic assignment problem library, European J. Oper. Res., 55, 115-119 (1991) · Zbl 0729.90993
[8] Coleman, T. F.; Pothen, A., The null space problem II. Algorithms, SIAM J. Alg. Disc. Meth., 8, 544-563 (1987) · Zbl 0642.65028
[9] Czyzyk, J.; Mehrotra, S.; Wagner, M.; Wright, S. J., PCx an interior point code for linear programming, Optim. Methods Softw., 11, 2, 397-430 (1999) · Zbl 0970.90118
[10] Duff, I. S., On algorithms for obtaining a maximum transversal, ACM Trans. Math. Software, 7, 315-330 (1981)
[11] Duff, I. S., The solution of large-scale least-square problems on supercomputers, Ann. Oper. Res., 22, 241-252 (1990) · Zbl 0705.90064
[12] I.S. Duff, MA57 a new code for the solution of sparse symmetric definite and indefinite systems, Tech. Rep., RAL 2002-024, Rutherford Appleton Laboratory, Oxfordshire, England, 2002; I.S. Duff, MA57 a new code for the solution of sparse symmetric definite and indefinite systems, Tech. Rep., RAL 2002-024, Rutherford Appleton Laboratory, Oxfordshire, England, 2002
[13] Fourer, R.; Mehrotra, S., Performance on an augmented system approach for solving least-squares problems in an interior-point method for linear programming, Math. Program. Soc. COAL Newsletter, 19, 26-31 (1992)
[14] George, A.; Ng, E., An implementation of Gaussian elimination with partial pivoting for sparse systems, SIAM J. Sci. Statist. Comput., 6, 390-409 (1985) · Zbl 0568.65017
[15] Gill, P. E.; Murray, W.; Ponceleón, D. B.; Saunders, M. A., Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl., 13, 292-311 (1992) · Zbl 0749.65037
[16] Golub, G. H.; Wathen, A. J., An iteration for indefinite systems and its application to the Navier-Stokes equations, SIAM J. Sci. Comput., 19, 530-539 (1998) · Zbl 0912.76053
[17] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[18] Lustig, I. J.; Marsten, R. E.; Shanno, D. F., On implementing Mehrotra’s predictor-corrector interior point method for linear programming, SIAM J. Optim., 2, 435-449 (1992) · Zbl 0771.90066
[19] Mehrotra, S., Implementations of affine scaling methods: approximate solutions of systems of linear equations using preconditioned conjugate gradient methods, ORSA J. Comput., 4, 103-118 (1992) · Zbl 0782.90067
[20] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601 (1992) · Zbl 0773.90047
[21] Mészáros, C., The augmented system variant of IPMs in two-stage stochastic linear programming computation, European J. Oper. Res., 101, 317-327 (1997) · Zbl 0929.90066
[22] Monteiro, R. D.C.; Adler, I.; Resende, M. G.C., A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension, Math. Oper. Res., 15, 191-214 (1990) · Zbl 0714.90060
[23] A.R.L. Oliveira, A new class of preconditioners for large-scale linear systems from interior point methods for linear programming, Tech. Rep., PhD Thesis, TR97-11, Department of Computational and Applied Mathematics, Rice University, Houston, TX, 1997; A.R.L. Oliveira, A new class of preconditioners for large-scale linear systems from interior point methods for linear programming, Tech. Rep., PhD Thesis, TR97-11, Department of Computational and Applied Mathematics, Rice University, Houston, TX, 1997
[24] Padberg, M.; Rijal, M. P., Location, Scheduling, Design and Integer Programming (1996), Kluwer Academic: Kluwer Academic Boston · Zbl 0879.68075
[25] Resende, M. G.C.; Veiga, G., An efficient implementation of a network interior point method, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 12, 299-348 (1993) · Zbl 0787.90028
[26] Rusten, T.; Winther, A. J., A preconditioned iterative method for saddlepoint problems, SIAM J. Matrix Anal. Appl., 13, 887-904 (1992) · Zbl 0760.65033
[27] Vanderbei, R. J., Symmetric quasi-definite matrices, SIAM J. Optim., 5, 100-113 (1995) · Zbl 0822.65017
[28] Vanderbei, R. J.; Carpenter, T. J., Indefinite systems for interior point methods, Math. Program., 58, 1-32 (1993) · Zbl 0791.90033
[29] Vavasis, S. A., Stable numerical algorithms for equilibrium systems, SIAM J. Matrix Anal. Appl., 15, 1108-1131 (1994) · Zbl 0806.65020
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.