A Superlinearly Convergent Polynomial Primal-Dual Interior-Point Algorithm for Linear Programming
Abstract
The choice of the centering parameter and the step-length parameter are the fundamental issues in primal-dual interior-point algorithms for linear programming. Various choices for these two parameters have been proposed that lead to polynomial algorithms. Recently, Zhang, Tapia and Dennis derived conditions for the choices of the two parameters that were sufficient for superlinear or quadratic convergence. However, prior to this work it had not been shown that these conditions for fast convergence are compatible with the choices that lead to polynomiality; none of the existing polynomial primal-dual interior-point algorithms satisfies these fast convergence requirements. This paper gives an affirmative answer to the question: can a primal-dual algorithm be both polynomial and superlinearly convergent for general problems? We construct and analyze a "large step" algorithm that possesses both polynomiality and, under the assumption of the convergence of the iteration sequence, Q-superlinear convergence. For nondegenerate problems, the convergence is actually Q-quadratic.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1991
- Accession Number
- ADA453104
Entities
People
- Richard A. Tapia
- Yin Zhang
Organizations
- Rice University