On quadratic convergence of the O(√(n)L)-iteration homogeneous and self-dual linear programming algorithm

On quadratic convergence of the O(√(n)L)-iteration homogeneous and self-dual linear programming algorithm

0.00 Avg rating0 Votes
Article ID: iaor2000479
Country: Netherlands
Volume: 87
Issue: 1
Start Page Number: 393
End Page Number: 406
Publication Date: Apr 1999
Journal: Annals of Operations Research
Authors: , ,
Keywords: interior point methods
Abstract:

In this paper, we show that Ye–Todd–Mizuno's O(√(n)L)-iteration homogeneous and self-dual linear programming (LP) algorithm possesses quadratic convergence of the duality gap to zero. In the case of infeasibility, this shows that a homogenizing variable quadratically converges to zero (which proves that at least one of the primal and dual LP problems is infeasible) and implies that the iterates of the (original) LP variable quadratically diverge. Thus, we have established a complete asymptotic convergence result for interior-point algorithms without any assumption on the LP problem.

Reviews

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