Center for Nonlinear AnalysisCNA Home People Seminars Publications Workshops and Conferences CNA Working Groups Summer Schools Summer Undergraduate Institute PIRE Cooperation Graduate Topics Courses Positions Contact
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