On the improvement per iteration in Karmarkar’s algorithm for linear programming

We investigate the decrease in potential at an iteration of Karmarkar’s projective method for linear programming. For a fixed step length parameter α (so that we must have 0<α•1) the best possible guarantee δn(α) in n dimensional space is essentially ln2⋍0.69; and to achieve this we must take α about 1. Indeed we show the precise result that δn(α) equals ln(1+α)-ln(1-α/(n-1)) for n sufficiently large. If we choose an optimal step length at each iteration then this guarantee increases only to about δ*⋍0.72. We also shed some light on the remarkable empirical observation that the number of iterations required seems scarcely to grow with the size of the problem.