Numerical Comparison of Barrier and Modified-Barrier Methods For Large-Scale Bound-Constrained Optimization

By Stephen G. Nash, R. Polyak, and Ariela Sofer

When a classical barrier method is applied to the solution of a nonlinear  programming problem with inequality constraints, the Hessian of the barrier function becomes increasingly ill-conditioned as the solution is approached. As a result, it may be desirable to consider alternative numerical algorithms. We compare the performance of two methods motivated by barrier functions. The first is a stabilized form of the classical barrier method, where a numerically stable approximation to the Newton direction is used when the barrier parameter is small.  The second is a modified barrier method where a barrier function is applied to a shifted form of the problem, and the resulting barrier terms are scaled by estimates of the optimal Lagrange multipliers.  When implemented appropriately the condition number of the Hessian of the modified barrier function remains bounded as the solution to the  constrained optimization problem is approached. Both of these techniques can be used in the context of a truncated-Newton method, and hence can be applied to large problems, as well as on parallel computers. In this paper, both techniques are applied to problems with bound constraints and we compare their practical behavior.

“Numerical Comparison of Barrier and Modified-Barrier Methods For Large-Scale Bound-Constrained Optimization”, inLarge Scale Optimization: State of the Art, W. W. Hager, D. W. Hearn and P.M. Pardalos (editors), Kluwer Academic Publishers (1994), pages 319-338.

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

(snash@gmu.edu)