On the Convergence of the Newton/Log-Barrier Method
Stephen J. Wright
In the Newton/log-barrier method, Newton steps are taken for the log
barrier function for a fixed value of the barrier parameter until a
certain convergence criterion is satisfied. The barrier parameter is
then decreased and the Newton process is repeated. A naive analysis
indicates that Newton's method does not exhibit superlinear
convergence to the minimizer of each instance of the log-barrier
function until it reaches a very small neighborhood of the minimizer.
By partitioning according to the subspace of active constraint
gradients, however, we show that this neighborhood is actually quite
large, thus explaining why reasonably fast local convergence can be
attained in practice. Finally, we show that the overall convergence
rate of the Newton/log-barrier algorithm
% to the solution of the nonlinear programming problem
is superlinear in the number of function/derivative evaluations,
provided that the nonlinear program is formulated with a linear
objective and the schedule for decreasing the barrier parameter is
related in a certain way to the convergence criterion for each Newton
Preprint ANL/MCS-P681-0897, Mathematics and Computer
Science Division, Argonne National Laboratory, August, 1997.
Revised: January, 1999.