Superlinear convergence of primal-dual interior point
algorithms for nonlinear programming
N.I.M. Gould, D. Orban, A. Sartenaer and Ph.L. Toint
The local convergence properties of a class of primal-dual interior
point methods are analyzed. These methods are designed to minimize a
nonlinear, nonconvex, objective function subject to linear equality
constraints and general 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 specifies both the decrease in the barrier parameter
and the level of accuracy for the inner minimization. It is shown
that, asymptotically, for each value of the barrier parameter, solving
a single primal-dual linear system is enough to produce an iterate
that already matches the barrier subproblem accuracy requirements. The
asymptotic rate of convergence of the resulting algorithm is
Q-superlinear and may be chosen arbitrarily close to quadratic.
Furthermore, this rate applies componentwise. These results hold in
particular for the method described by Conn, Gould, Orban and Toint,
and indicate that the details of its inner minimization are irrelevant
in the asymptotics, except for its accuracy requirements.
Cerfacs technical report TR/PA/00/20, April 2000.
CERFACS - Parallel Algorithms Project
42, Avenue Gaspard Coriolis
31057 Toulouse Cedex 1 - FRANCE.