Quadratic convergence of potential-reduction methods for degenerate problems

Quadratic convergence of potential-reduction methods for degenerate problems

0.00 Avg rating0 Votes
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:
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 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.

Reviews

Required fields are marked *. Your email address will not be published.