Abstract
In most interior point methods for linear programming, a sequence of weighted linear least squares problems are solved, where the only changes from one iteration to the next are the weights and the right hand side. The weighted least squares problems are usually solved as weighted normal equations by the direct method of Cholesky factorization. In this paper, we consider solving the weighted normal equations by a preconditioned conjugate gradient method at every other iteration. We use a class of preconditioners based on a low rank correction to a Cholesky factorization obtained from the previous iteration. Numerical results show that when properly implemented, the approach of combining direct and iterative methods is promising.
Chapter PDF
KeyWords
References
V. Baryamureeba, and T. Steihaug, Computational issues for a new class of preconditioners, To appear in the Proceedings for the 2nd Workshop on Large-Scale Scientific Computations, 1999.
V. Baryamureeba, T. Steihaug and Y. Zhang, A class of preconditioners for weighted least squares problems, Technical Report No. 170, Department of Informatics, University of Bergen, 5020 Bergen, Norway, April 30, 1999.
T.J. Carpenter and D.F. Shanno, An interior point method for quadratic programs based on conjugate projected gradients, Computational Optimization and Applications, Vol. 2, pp. 5–28, 1993.
J.W. Demmel, M.T. Heath, and H.A. Van der Vorst, Parallel numerical linear algebra, Acta Numerica, pp. 111–197, 1993.
D.M. Gay, Electronic mail distribution of linear programming test problems, Mathematical Programming Society COAL Newsletter, No. 13, pp.10–12, 1985.
D. Goldfarb, and S. Liu, An o(n 3L) primal interior-point algorithm for convex quadratic programming, Mathematical Programming, Vol. 49, pp. 325–340, 1991.
G.H. Golub, and Charles H. Van Loan, Matrix computations, Third Edition, 1996.
N.K. Karmarkar and K.G. Ramakrishnan, Computational results of an interior point algorithm for large-scale linear programming, Mathematical Programming, Vol. 52, pp. 555–586, 1991.
S. Mehrotra, Implementations of affine scaling methods: Approximate solutions of systems of linear equations using preconditioned conjugate gradient methods, ORSA J. Comput., 4 (1992), pp. 103–118.
W. Wang, and D.P. O’Leary, Adaptive use of iterative methods in predictor-corrector interior point methods for linear programming Technical Report No. CS-TR-4011, Computer Science Department, University of Maryland, April 1999. (Revised version of TR-3560, November 1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baryamureeba, V., Steihaug, T., Zhang⋆, Y. (1999). Application of a Class of Preconditioners to Large Scale Linear Programming Problems. In: Amestoy, P., et al. Euro-Par’99 Parallel Processing. Euro-Par 1999. Lecture Notes in Computer Science, vol 1685. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48311-X_146
Download citation
DOI: https://doi.org/10.1007/3-540-48311-X_146
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66443-7
Online ISBN: 978-3-540-48311-3
eBook Packages: Springer Book Archive