A STANDARD FORM VARIANT, AND SAFEGUARDED LINESEARCH, FOR THE MODIFIED KARMARKAR ALGORITHM

In his original analysis of the projective algorithm for linear programming, Karmarkar proposed a "modified method" which improved the worst-case arithmetic complexity of the original algorithm by a factor of {Mathematical expression}. Karmarkar's analysis of the {Mathematical expression} improvement is based on a primal-dual formulation, and requires that small steps be taken on each iteration. However, in practice the original algorithm can be easily applied to standard form problems, and is considerably improved by performing a linesearch on each iteration, generally leading to much larger steps. We show here that by incorporating a simple safeguard, a linesearch may be performed in the modified algorithm while retaining the {Mathematical expression} complexity improvement over the original algorithm. We then show that the modified algorithm, with safeguarded linesearch, can be applied directly to a standard form linear program with unknown optimal objective value. The resulting algorithm enjoys a {Mathematical expression} complexity advantage over standard form variants of the original algorithm. © 1990 The Mathematical Programming Society, Inc.