Largest Step Path Following Algorithm for Monotone Linear ComplementarityProblems

摘要

Path-following algorithms take at each iteration a Newton step for approaching apoint on the central path, in such a way that all the iterates remain in a given neighborhood of that path. The 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. The authors 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.