Article ID: | iaor1993767 |
Country: | Netherlands |
Volume: | 56 |
Issue: | 3 |
Start Page Number: | 301 |
End Page Number: | 319 |
Publication Date: | Oct 1992 |
Journal: | Mathematical Programming (Series A) |
Authors: | Tseng Paul, Luo Zhi-Quan |
The affine-scaling algorithm, first proposed by Dikin, is presently enjoying great popularity as a potentially effective means of solving linear programs. An outstanding question about this algorithm concerns its convergence in the presence of degeneracy. In this paper, the authors give new convergence results for this algorithm that do not require any non-degeneracy assumption on the problem. In particular, they show that if the stepsize choice of either Dikin or Barnes or Vanderbei, et al. is used, then the algorithm generates iterates that converge at least linearly with a convergence ratio of