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