ANOTHER DERIVATION OF THE KARMARKAR DIRECTION FOR LINEAR PROGRAMMING

Abstract

This paper provides another derivation of the Karmarkar direction for linear programming. It is strongly motivated by derivations of Gonzaga, but we show how the direction can be viewed as a steepest descent direction in the original feasible region corresponding to a metric different fromthe Euclidean one. We show that a fixed decrease in the potential function can be obtained by taking a step in this direction, as long as a certain assumption holds. We give an example showing that such a restriction is necessary, and discuss two ways to remove it.