Superlinear and Quadratic Convergence of Affine-Scaling
Interior-Point Newton Methods for
Problems with Simple Bounds without Strict Complementarity
Assumption
Matthias Heinkenschloss
Department of Computational and Applied Mathematics
Rice University
Michael Ulbrich
Technische Universität München
Institut für Angewandte Mathematik und Statistik
Stefan Ulbrich
Technische Universität München
Institut für Angewandte Mathematik und Statistik
Mathematical Programming, Vol 86 (1999), No. 3, pp. 615-635.
Abstract
A class of affine-scaling interior-point methods
for bound constrained optimization problems
is introduced which are locally q-superlinear or
q-quadratic convergent. It is assumed that the
strong second order sufficient optimality conditions at
the solution are satisfied, but strict complementarity
is not required.
The methods are modifications of the
affine-scaling interior-point Newton methods introduced by
T. F. Coleman and Y. Li
( Math. Programming, 67:189-224, 1994).
There are two modifications. One is a modification
of the scaling matrix, the other one is the use
of a projection of the step to maintain strict feasibility
rather than a simple scaling of the step.
A comprehensive local convergence analysis is given.
A few simple examples are presented
to illustrate the pitfalls of the original approach by Coleman
and Li in the degenerate case and to demonstrate
the performance of the fast converging modifications developed
in this paper.
Keywords
Bound constraints,
affine scaling, interior-point algorithms, superlinear convergence,
nonlinear programming, degeneracy, optimality conditions.
1991 Mathematics Subject Classification
49M15, 65K05, 90C30.
Related papers