Extending Mehrotra's Corrector for Linear Programs

Florian Jarre, Martin Wechs

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.

Preprint Nr. 219, Mathematische Institute der Universitaet Wuerzburg Dec. 1996, revised Oct. 1997

Contact: jarre@mathematik.uni-wuerzburg.de