Superlinear Convergence of Interior Point Algorithms for a General Class of Problems.

摘要

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.