Local behavior of the Newton method on two equivalent systems from linear programming (Q5959909)

The local behavior of Newton's method for two equivalent systems of nonlinear equations related to the solution of linear programming problems by interior-point methods is investigated. The first system originates from the first order optimality conditions for the logarithmic barrier function formulation of a linear program, the second one, which is the starting point especially of primal-dual path-following methods, can be interpreted as a perturbation of the optimality conditions for the problem and may be derived from the first system by introduction of auxiliary variables. For nondegenerate problems it is proved that, if Newton's method is applied to the first system, the radius of its sphere of convergence shrinks to zero in the same order as the barrier parameter is decreased, whereas, in case of the second system, it is bounded away from zero for all sufficiently small nonnegative perturbation parameters. This result, which is accompanied by interesting numerical experiments, supports use of the perturbed system and thereby contributes to completion of the numerical analysis of some very successful linear programming methods. Moreover, some additional numerical experiments seem to indicate that, for degenerate problems, the convergence radii of Newton's method tend to zero for both systems when the respective parameters are diminished monotonically, but that employment of the perturbed optimality conditions is more favourable also for such problems since the convergence radii of Newton's method normally seem to be considerably larger for them.