CRPC-TR97759						December 1997
							Revised September 1998

Title: Superlinear and Quadratic Convergence of Affine-Scaling 
Interior-Point Newton Methods for Problems with Simple Bounds without 
Strict Complementarity Assumption

Authors: Matthias Heinkenschloss, Michael Ulbrich and Stefan Ulbrich

Submitted August 1998; Available as Rice CAAM TR 97-30 and submitted to
"Mathematical Programming"

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.

------------------------------------------------------------------------------
Matthias Heinkenschloss
Department of Computational and Applied Mathematics
Rice University
heinken@caam.rice.edu

Michael Ulbrich
Technical University of Munich
Institut for Applied Mathematics and Statistics
mulbrich@statistik.tu-muenchen.de

Stefan Ulbrich
Technical University of Munich
Institut for Applied Mathematics and Statistics
sulbrich@statistik.tu-muenchen.de