CRPC-TR98770-S						September 1998

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

Authors: Maria Cristina Villalobos, Richard A. Tapia, and Yin Zhang

Submitted September 1998; revised July 1999; available as Rice CAAM
TR98-02

Abstract:
Newton-type methods are fundamental techniques for solving systems of
nonlinear equations.  However, it is often 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.

Key words: Newton's method; equivalent systems; interior-point methods;
sphere of convergence; linear programming

------------------------------------------------------------------------------
Maria Cristina Villalobos	Richard A. Tapia	Yin Zhang
cristina@caam.rice.edu		rat@caam.rice.edu	zhang@caam.rice.edu

Department of Computational and Applied Mathematics
Rice University