zbMATH — the first resource for mathematics

Extending Mehrotra’s corrector for linear programs. (English) Zbl 1115.90395
Summary: 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.

90C51 Interior-point methods
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX Cite
Full Text: Link