Superlinear convergence of primal-dual interior point algorithms for nonlinear programming

The local convergence properties of a class of primal-dual interior point m ethods are analyzed. These methods are designed to minimize a nonlinear, no nconvex, objective function subject to linear equality constraints and gene ral inequalities. They involve an inner iteration in which the log-barrier merit function is approximately minimized subject to satisfying the linear equality constraints, and an outer iteration that species both the decrease in the barrier parameter and the level of accuracy for the inner minimizat ion. Under nondegeneracy assumptions, it is shown that, asymptotically, for each value of the barrier parameter, solving a single primal-dual linear s ystem is enough to produce an iterate that already matches the barrier subp roblem accuracy requirements. The asymptotic rate of convergence of the res ulting algorithm is Q-superlinear and may be chosen arbitrarily close to qu adratic. Furthermore, this rate applies componentwise. These results hold i n particular for the method described in [A. R. Conn, N. I. M. Gould, D. Or ban, and P. L. Toint, Math. Program. Ser. B, 87 ( 2000), pp. 215-249] and i ndicate that the details of its inner minimization are irrelevant in the as ymptotics, except for its accuracy requirements.