Why Extrapolation Helps Barrier Methods

By Stephen G. Nash and Ariela Sofer

Abstract

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?

Complete Text (postscript file)

“Why Extrapolation Helps Barrier Methods”, submitted for publication.

Links

• Systems Engineering & Operations Research Dept.
• School of Information Technology and Engineering
• George Mason University

mail to: snash@gmu.edu