|
Center for
Nonlinear Analysis
CNA Home
People
Seminars
Publications
Workshops and Conferences
CNA Working Groups
Summer Schools
Summer Undergraduate Institute
PIRE
Cooperation
Graduate Topics Courses
Positions
Contact |
Publication 98-CNA-09
Quadratic Convergence of Potential-Reduction Methods for Degenerate Problems Reha H. Tutuncu December 2, 1998
Abstract: 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 (TTY) 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. Key words: linear programming, potential functions, quadratic convergence, degeneracy AMS subject classification: 90C05 Get the paper in its entirety as |
