The Behavior of Newton-type Methods on Two Equivalent Systems from Linear Programming

M.C. Villalobos, R.A. Tapia, Y. Zhang

Newton-type methods are fundamental techniques for solving systems of nonlinear equations. However, it is not fully appreciated that these methods can produce significantly different behavior when applied to equivalent systems. In this paper, we investigate differences in local and global behavior of Newton-type methods when applied to two different but equivalent systems from linear programming: the optimality conditions of the logarithmic barrier formulation and the perturbed optimality conditions. Through theoretical analysis and numerical results, we show Newton-type methods perform more effectively on the latter system.

TR9802 (also report CRPC-TR98770-S) Rice University, Computational and Applied Mathematics, Houston, TX September 1998