# zbMATH — the first resource for mathematics

On the convergence of the affine-scaling algorithm. (English) Zbl 0762.90052
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.
Reviewer: R.Nehse (Ilmenau)

##### MSC:
 90C05 Linear programming 90C35 Programming involving graphs or networks 90C60 Abstract computational complexity for mathematical programming problems 90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: