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 . Karmarkar's analysis of the 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. The paper shows here that by incorporating a simple safeguard, a linesearch may be performed in the modified algorithm while retaining the complexity improvement over the original algorithm. It then shows 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 complexity advantage over standard form variants of the original algorithm.