A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm (Q920840)

The modified Karmarkar algorithm improved the worst-case arithmetic complexity of the original Karmarkar algorithm by a factor of \(\sqrt{n}\), but with the restrictions of taking small steps on each iteration and using the primal-dual formulation of the LP problems. The author of this paper shows that by incorporating a simple safeguard strategy which in fact is a sufficient decrease criterion of Goldstein-Armijo type in nonlinear programming, a line search may be performed in the modified Karmarkar's algorithm while retaining the \(\sqrt{n}\) complexity improvement and the new modified algorithm can be applied directly to a standard form linear program with unknown optimal objective value.