On the convergence of the affine-scaling algorithm (Q1196183)

An algorithm is described for linear programming which have polynomial- time complexity (also in the presence of degeneracy). Especially, it is shown that, for special stepsize choices, the algorithm generates iterates that converge at least linearly with a convergence ratio of \(1- \beta/\sqrt n\), where \(n\) is the number of variables and \(\beta\in(0,1]\) is a certain stepsize ratio. Moreover, using an adapted form of Barnes' stepsize choice it is proved that the sequence of iterates converges to a point satisfying a so-called \(\varepsilon\)-complementary slackness condition.