A MODIFIED SCHUR-COMPLEMENT METHOD FOR HANDLING DENSE COLUMNS IN INTERIOR-POINT METHODS FOR LINEAR-PROGRAMMING

The main computational work in interior-point methods for linear progr amming (LP) is to solve a least-squares problem. The normal equations are often used, but if the LP constraint matrix contains a nearly dens e column the normal-equations matrix will be nearly dense, Assuming th at the nondense part of the constraint matrix is of full rank, the Sch ur complement can be used to handle dense columns. In this article we propose a modified Schur-complement method that relaxes this assumptio n. Encouraging numerical results are presented.