Advanced Modeling and Optimization

Abstract for Paper 4 of Volume 1, Number 2, 1999, pp. 38-60


Extending Mehrotra's Corrector for Linear Programs


Florian Jarre and Martin Wechs
Institut für Angewandte Mathematik und Statistik,
Universität Würzburg, Am Hubland,
D-97074 Würzburg, Federal Republic of Germany.

Abstract

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.