Article ID: | iaor2002952 |
Country: | Germany |
Volume: | 90 |
Issue: | 1 |
Start Page Number: | 169 |
End Page Number: | 203 |
Publication Date: | Jan 2001 |
Journal: | Mathematical Programming |
Authors: | Ttnc R.H. |
Global and local convergence properties of a primal–dual interior-point pure potential-reduction algorithm for linear programming problems is analyzed. This algorithm is a primal–dual variant of the Iri–Imai method and uses modified Newton search directions to minimize the Tanabe–Todd–Ye potential function. A polynomial time complexity for the method is demonstrated. Furthermore, this method is shown to have a unique accumulation point even for degenerate problems and to have Q-quadratic convergence to this point by an appropriate choice of the step-sizes. This is, to the best of our knowledge, the first superlinear convergence result on degenerate linear programs for primal–dual interior-point algorithms that do not follow the central path.