Article ID: | iaor1998421 |
Country: | Netherlands |
Volume: | 76 |
Issue: | 2 |
Start Page Number: | 309 |
End Page Number: | 332 |
Publication Date: | Feb 1997 |
Journal: | Mathematical Programming |
Authors: | Gonzaga Clovis C. |
Keywords: | complementarity, interior point methods, duality |
Path-following algorithms take at each iteration a Newton step for approaching a point on the central path, in such a way that all the iterates remain in a given neighborhood of that path. This paper studies the case in which each iteration uses a pure Newton step with the largest possible reduction in complementarity measure (duality gap). This algorithm is known to converge superlinearly in objective values. We show that with the addition of a computationally trivial safeguard it achieves Q-quadratic convergence, and show that this behavior cannot be proved by usual techniques for the original method.