A quadratically convergent -iteration algorithm for linear programming

A quadratically convergent -iteration algorithm for linear programming

0.00 Avg rating0 Votes
Article ID: iaor19941935
Country: Netherlands
Volume: 59
Issue: 2
Start Page Number: 151
End Page Number: 162
Publication Date: Apr 1993
Journal: Mathematical Programming (Series A)
Authors: , , ,
Keywords: interior point methods
Abstract:

Recently, Ye, Tapia and Zhang demonstrated that Mizuno-Todd-Ye's predictor-corrector interior-point algorithm for linear programming maintains the equ2-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper the authors establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to the present knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or non-degeneracy.

Reviews

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