Extending Mehrotra’s corrector for linear programs.

*(English)*Zbl 1115.90395Summary: In this article a primal-dual interior-point method for solving linear programs is proposed. A new approach for generating higher order search directions, and a new method for an efficient higher order subspace search along several search directions are the basis of the proposed extension. The subspace search is reduced to a linear program in several variables. The method using the simplest (two-dimensional) subprograms is a slight variation of Mehrotra’s predictor-corrector method, and is thus known to be practically very efficient. The higher dimensional subproblems are guaranteed to be at least as effective – with respect to a certain measure – as the two- dimensional ones. Numerical experiments with the PCx package indicate that also in practice the higher order subspace search is very cheap and efficient.