Accession Number:

ADA455378

Title:

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

Descriptive Note:

Corporate Author:

RICE UNIV HOUSTON TX DEPT OF MATHEMATICAL SCIENCES

Report Date:

1991-10-01

Pagination or Media Count:

17.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE