On the Superlinear Convergence of Interior Point Algorithms for a General Class of Problems

Abstract
This paper extends the Q-superlinear convergence theory recently developed by Zhang, Tapia and Dennis for a class of interior-point linear programming algorithms to similar interior-point algorithms for quadratic programming and for linear complementary problems. Our unified approach consists of viewing all these algorithms as a damped Newton method applied to perturbations of a general problem. We establish a set of sufficient conditions for these algorithms to achieve Q-superlinear convergence. The key ingredients consist of asymptotically taking the step to the boundary of the positive orthant and letting the centering parameter approach zero at a specific rate. The construction of algorithms that have both the global property of polynomiality and the local property of superlinear convergence will be the subject of further research.

This publication has 0 references indexed in Scilit: