Convergence in Karmarkar's Algorithm for Linear Programming

Abstract

Karmarkar’s algorithm is formulated so as to avoid the possibility of failure because of unbounded solutions. A general inequality gives an easy proof of the convergence of the iterations. It is shown that the parameter value α = 0.5 more than doubles the originally predicted rate of convergence. To go from the last iterate to an exact optimal solution, an O(n^3) termination algorithm is prescribed. If the data have maximum bit length independent of n, the composite algorithm is shown to have complexity 0(n^4.5 log n).