##
Why Extrapolation Helps Barrier Methods

###
Stephen G. Nash and Ariela Sofer

Barrier methods for nonlinear programming went out of fashion in the
late 1960s, because of ill-conditioning in the Hessian of the barrier
function. It is now known, however, that this ill-conditioning is
benign if the barrier method is implemented appropriately using
Newton's method. More recently, it has been shown that, if the
solution of one barrier subproblem is used as the initial guess for
the next subproblem, then the Newton step at the initial guess is
likely to be infeasible. In this paper, we show that if
extrapolation is used to obtain the initial guess, however,
this doesn't happen. In fact, such a barrier method has many good
properties; for example, the initial guess will be close to the
solution of the barrier subproblem, and the gradient of the
barrier function will be small. This leads us to ask: What,
if anything, is wrong with barrier methods, and why did they
go out of fashion?

Contact: asofer@gmu.edu