On the improvement per iteration in Karmarkar's algorithm for linear programming (Q918862): Difference between revisions

Let \(\delta_ n(\alpha)\) be the greatest possible guaranteed potential drop at an iteration of Karmarkar's projective method for linear programming problems in dimension n, when the method uses step length parameter \(\alpha\). The paper shows that \(\delta_ n(\alpha)\) equals \(\ln (1+\alpha)-\ln (1-\frac{\alpha}{(n-1)})\) for n sufficiently large.