A modified Schur-complement method for handling dense columns in interior-point methods for linear programming
Author:
Open Access
- 1 September 1996
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 22 (3) , 348-356
Abstract
The main computational work in interior-point methods for linear programming (LP) is to solve a least-squares problem. The normal equations are often used, but if the LP constraint matrix contains a nearly dense column the normal-equations matrix will be nearly dense. Assuming that the nondense part of the constraint matrix is of full rank, the Schur complement can be used to handle dense columns. In this article we propose a modified Schur-complement method that relaxes this assumption. Encouraging numerical results are presented.Keywords
This publication has 12 references indexed in Scilit:
- An Efficient Newton Barrier Method for Minimizing a Sum of Euclidean NormsSIAM Journal on Optimization, 1996
- Presolving in linear programmingMathematical Programming, 1995
- Commentary—Major Cholesky Would Feel ProudINFORMS Journal on Computing, 1994
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear ProgrammingSIAM Journal on Optimization, 1992
- Computational experience with a primal-dual interior point method for linear programmingLinear Algebra and its Applications, 1991
- Further Development of a Primal-Dual Interior Point MethodINFORMS Journal on Computing, 1990
- Primal barrier methods for linear programmming: Technical report1989
- An implementation of Karmarkar's algorithm for linear programmingMathematical Programming, 1989
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective methodMathematical Programming, 1986
- Some Extensions of an Algorithm for Sparse Linear Least Squares ProblemsSIAM Journal on Scientific and Statistical Computing, 1982