The largest step path following algorithm for monotone linear complementarity problems

The largest step path following algorithm for monotone linear complementarity problems

0.00 Avg rating0 Votes
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:
Keywords: complementarity, interior point methods, duality
Abstract:

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.

Reviews

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