Local behavior of the Newton method on two equivalent systems from linear programming.
Newton's method is a fundamental technique underlying many numerical methods for solving systems of nonlinear equations and optimization problems. However, it is often not fully appreciated that Newton's method can produce significantly different behavior when applied to equivalent systems, i.e., problems with the same solution but different mathematical formulations. In this paper, we investigate differences in the local behavior of Newton's method when applied to two different but equivalent systems from linear programming: the optimality conditions of the logarithmic barrier function formulation and the equations in the so-called perturbed optimality conditions. Through theoretical analysis and numerical results, we provide an explanation of why Newton's method performs more effectively on the latter system.
Introduction
Newton's method is generally accepted as an effective tool for solving a system of nonlinear
It is a locally and quadratically convergent method
under reasonable assumptions (see e.g. Dennis and Schnabel (Ref. 1)). It is often not fully
appreciated, however, that Newton's method can exhibit significantly different local and global
behavior on two equivalent systems. By equivalent systems, we refer to two systems of nonlinear
equations that can be derived from one another and essentially share the same set of solutions
(though some auxiliary variables/equations may be present in one but not in another). In this
paper, we compare the behavior of Newton's method applied to two well-known equivalent
systems of nonlinear equations associated with linear programming.
The first of these equivalent systems consists of the first-order optimality conditions of the
log-barrier formulation of the linear program. The second system consists of equations in the
perturbed first-order optimality conditions for the linear program. Though the two nonlinear
systems have essentially the same set of solutions, El-Bakry, Tapia, Tsuchiya, and Zhang (Ref. 2)
show that Newton's method necessarily generates different iterates for the two systems. In
this paper, we show that Newton's method applied to the perturbed optimality conditions for
the linear program has a larger sphere of convergence than Newton's method applied to the
optimality conditions of the log-barrier formulation of the linear program.
Of these two equivalent systems, the perturbed first-order optimality conditions are widely
used in interior-point methods for linear programming. However, the reasons for favoring this
system have not been fully analyzed. In this paper, we provide an explanation on why the
system associated with the perturbed optimality conditions is the system of choice.
The paper is organized as follows. In Section 2, we present the two equivalent nonlinear
systems under consideration. In Section 3, we introduce the notion of the sphere of convergence
of Newton's method and provide theoretical results on the radius of the sphere of convergence
of Newton's method applied to the two equivalent systems. In Section 4 we present numerical
results supporting the theory we developed in the previous section. Finally, we make some
concluding remarks in Section 5.
2. Two Equivalent Formulations
In this section, we introduce the linear programming problem and the two equivalent nonlinear
systems under consideration. We consider the linear programming problem in the standard form
m. The Lagrangian function
associated with problem (1) is
where y
are, respectively, the vectors of Lagrange multipliers associated with
the equality and the inequality constraints. The first-order optimality conditions for problem
(1) are
2.1. Two Equivalent Systems
We derive one of the equivalent systems by formulating problem (1) in the logarithmic barrier
framework. This framework, which was first introduced by Frisch (Ref. 3), consists of solving
a sequence of equality constrained minimization problems with decreasing values of the barrier
parameter - ? 0. For problem (1) and a given value of - ? 0, the log-barrier subproblem has
the following form
log x i
Assume that the feasible set fx : for every value of - ? 0,
there exists a unique solution x
- of the log-barrier subproblem. Under mild assumptions (see
e.g. Fiacco and McCormick (Ref. 4)), as - ! 0 the sequence of iterates fx
converges to a
solution x   of problem (1), i.e. lim -!0 x
The optimality conditions for the log-barrier subproblem are derived by differentiating the
Lagrangian function,
log
where y is the vector of Lagrange multipliers associated with the equality constraints,
and setting the gradient of the Lagrangian equal to zero. Then the optimality conditions are
Observe that the Jacobian of FB is given by
\Gamma-X \Gamma2 A T
If
In applications of Newton's
method near the solution, the Jacobian necessarily becomes ill-conditioned as - approaches zero
(see, (Ref. 5, 6)).
Now we derive a nonlinear system equivalent to system (3). Consider the introduction of an
auxiliary variable, z 2 R n , and define
which is written equivalently as Substituting z into system (3) and adding the
equation that relates x; z and - yields the system
The Jacobian of F P is given by
The Jacobian is nonsingular if solution where x and z contain
zero components, the Jacobian may or may not be nonsingular, depending on the degeneracy
of the solution.
Kojima, Mizuno and Yoshise (Ref. 7) first proposed to use system (5) to solve the linear
program in a primal-dual interior-point method. El-Bakry, Tapia, Tsuchiya, and Zhang (Ref. 2)
show that although systems (3) and (5) are equivalent, Newton's method necessarily generates
different iterates for the two systems.
Two things are worth noting in comparing the two systems (3) and (5). First, while FB and
are undefined for
are defined. Second, while F 0
B is dependent on -, F 0
P is
not. These differences will greatly affect the behavior of Newton's method when applied to the
two systems as - approaches zero.
We remark that although the Jacobian F 0
does not depend on -, we will nevertheless
use the present notation for the Jacobian to stress its association with system (5) for a
given value of - 0.
System (5) can also be obtained by considering the first-order optimality conditions (2) of
the linear program and perturbing the complementarity equation,
2.2. Central Paths
Assume that the strictly feasible set f(x; nonempty.
Let
the solution to system (3) for a particular value of - ? 0, and similarly let
the solution to system (5). Then by the central path for system (3), we mean
the set
The set of points in CB forms a continuous path such that lim -!0 (x
(Ref. 4, 8)).
We remark that systems (3) and (5) are equivalent, in the sense that for - ? 0, and (x
for z
-(X
system (5), we have lim -!0 (x
system (5) the central path is defined as the set
2.3. Assumption and Notation
Throughout the paper, we make use of the following assumption and notation.
Nondegeneracy Assumption. Let the matrix A be of full rank m, and let (x   ; y   ; z   ) be a
primal and dual nondegenerate solution of system (2). Without loss of generality, we assume
that the first m components of x   are positive and the remaining (n \Gamma m) components are zero.
The nondegeneracy assumption guarantees that (x   ; y   ; z   ) is an isolated solution point in the
primal-dual space. It is also well known that the pair (x   ; z   ) satisfies strict complementarity:
x
0g. Then by the nondegeneracy assumption,
ng. The matrix A will be partitioned into
where A B denotes the matrix consisting of the columns of A indexed by B and similarly for
AN . Note that If u is a vector, then its uppercase counterpart U will denote the
diagonal matrix whose diagonal consists of the elements of u. For a vector u 2 R n , u B is the
vector of the first m components of u and uN is the vector of the remaining (n \Gamma m) components
of u. The quantity u 2 represents the vector u whose components are individually squared. All
norms k \Delta k are assumed to be the Euclidean norm unless otherwise noted.
3. Sphere of Convergence: Analysis
Standard local theory of Newton's method applied to a nonlinear system (see e.g. (Ref. 1))
provides the existence of a neighborhood about a solution in which Newton's method is well-
defined. More importantly, starting from any point in the neighborhood, Newton's method
guarantees convergence to the solution. For systems (3) and (5), such a neighborhood also
exists about the solution for any given - ? 0 under our nondegeneracy assumption. In this
section, we introduce the notion of the sphere of convergence for Newton's method. We analyze
the behavior of the radius of the sphere of convergence associated with systems (3) and (5)
by considering Newton's method applied to these equivalent systems as - ! 0. Under the
nondegeneracy assumption, our analysis shows that the radius of the sphere of convergence of
Newton's method on system (3) decreases to zero in the same order as - ! 0. However, we
show the radius of the sphere of convergence of Newton's method applied to system (5) has a
lower-bound estimate independent of -. These results provide a theoretical explanation on why
Newton's method is more efficient on system (5) than on system (3) at least for small values of
3.1. Preliminaries
We introduce the notion of the sphere of convergence for Newton's method. Then, we present
lemmas to be used in our analysis for the radius of the sphere of convergence of Newton's
method on system (3).
We remark that the notion of the sphere of convergence is not new. Several references can
be found in the literature where this notion or similar concept is used, see (Ref. 1, p. 91), for
example. To conduct a rigorous study on the radius of convergence for Newton's method, we
give a formal definition for the sphere of convergence below.
Definition 3.1. We define the closed ball with radius r centered at v   as B(v
rg.
Definition 3.2. For a given nonlinear system, F (v) = 0, and a solution v   , the sphere of
convergence of Newton's method at v   is defined as the largest closed ball centered at v   such
that starting from any interior point in the sphere, excluding v   , Newton's method (with unit
steplength) is well-defined and generates a sequence that converges to v   .
Lemma 3.1. Consider - ? 0 and (x
contained in CB . Then under the nondegeneracy
assumption, there exists -
so that for -
- there is a ball B(x
such that for any
for constants C
Proof. Since x
strictly positive, and x
exist -
constants such that for -
-, we have G 1 - (x
-.
- is an interior point of R n
Such a point must also satisfy
First we show that x i for are bounded away from zero. From (11) for
are bounded above and below and ffi - G 1 =2, from (12) we obtain
Thus
Now, we show the second part of the proof. By the nondegeneracy assumption, strict complementarity
(8) holds at the solution, which, together with the definition (4), implies
lim
Hence, for sufficiently small - and for some constants G 3
Consequently,
By (12) and (13) for i 2 N we obtain
Therefore,
where We note that fi can be chosen so that C 3 ?
Lemma 3.2. Define
where
under the nondegeneracy assumption, there exists ~
-, and for any
is such that Lemma 3.1 holds,
for constants C
Proof. Consider
- is such that Lemma 3.1 holds. Without loss of generality,
consists of the columns A i of A with i 2 B. Similarly, we can define
Substituting in the definition of P we obtain
Now, introduce the m \Theta (n \Gamma m) matrix R where
Then P can be partitioned as follows
Applying the bounds in (9) to (16), we obtain kRk - C 5 - for a constant C 5 ? 0. Since
- such that for
all - ~
-, we obtain kRR T k ! 1. Then using the Neumann series on (I m +RR
from (17) that
for - and constants C
3.2. Sphere of Convergence for System (3)
We provide a tight result showing that the radius of the sphere of convergence of Newton's
method on system (3) decreases to zero in the same order that - ! 0. Our result follows from
showing that a lower-bound and an upper-bound of order - exist for the radius of the sphere
of convergence.
Lemma 3.3. Under the nondegeneracy assumption, there exist ~
such that for any - ~
-, the radius of the sphere of convergence, r B (-), of Newton's method
satisfies
Proof. We will prove the above result by showing that the sequence of Newton iterates
converges to the solution (x
the initial point x 0 satisfies
Consider ~
- given in Lemma 3.2. Assume Newton's method is applied to system (3) for a
particular value of - ~
-. Denote (x; y) as the current Newton iterate where x 2 B(x
and x satisfies the conditions given in (9). Now, consider the next Newton iteration
x
y
Using the fact that FB (x
x
y
-(X
By Taylor's Theorem,
for some -
Substituting (20) into (19) we obtain
where
Making the above substitution for
and multiplying the right-hand-side of (21)
we obtain
Using the definition of P in (14), we rewrite
We now consider first the vector
- ) in (22). If we partition
its basic
and nonbasic components and use the notation for P in (14), then
which leads to
Applying the bounds given in (9) and (15) to the above, we obtain
for some constant C ? 0. Recall that
It follows from (23) that if the initial
iterate satisfies
ae
fi;C
oe
then the x-component of the Newton iteration sequence will converge to x
- .
Now, consider the remaining m components of (22). Taking the norm and partitioning
matrices, we obtain
Applying (9), we have
Then it follows that for some constant -
Thus, the y-component of the Newton iteration sequence converges to y
holds. In view
of (24) and (25), we conclude that the Newton iteration sequence converges to (x
the
initial iterate x 0 satisfies (18) for all - ~
- and for K 1 defined as the constant in the right-hand
side of (24). 2
The above lemma shows that the radius of the sphere of convergence of Newton's method
It establishes only a lower-bound result for the radius of the sphere of
convergence of system (3). To establish that the radius of the sphere of convergence decreases
to zero at exactly the same order as - ! 0, we need an upper-bound of the same order. The
following lemma establishes such an upper-bound.
Lemma 3.4. Consider Newton's method applied to system (3). There exist constants -
and such that for any given -
-, the radius of the sphere of convergence, r B (-),
corresponding to this - satisfies
Proof. It suffices to show the existence of a point x - 0 with
Newton's method does not converge or is not defined. From Lemma 3.1 there exist -
constant such that for -
- and for i 2 N , (x
Consider an i 2 N , and let
where e i is the ith canonical vector. Obviously,
Newton's method is not defined at x. Therefore, r B (- K 2 -. 2
Now we are ready to give the main result for system (3).
Theorem 3.1. There exist constants ~ - ? 0 and K 1 such that for - ~
-, the radius
for the sphere of convergence, r B (-), of Newton's method applied to system (3) satisfies
Proof. Application of Lemma 3.3 and Lemma 3.4 produces the result. 2
Since system (3) is not well-defined in a neighborhood of the solution for it is not
surprising that as - ! 0, the sphere of convergence would decrease to zero. However, it was
previously not known that the radius of the sphere of convergence would decrease to zero at
exactly the same rate as - goes to zero. For the log-barrier formulation of the nonlinear program
with inequality constraints, S. Wright (Ref. lower-bound result for the radius of
the sphere of convergence. In (Ref. 9), it is shown that there exists a -
such that for -
convergence to the solution x
- can be obtained from any point x 0 that satisfies
C- ff (26)
for constant -
In the case of linear programming, our result for system (3)
is tight and shows that the radius of the sphere of convergence decreases in the same order as
our results.
3.3. Sphere of Convergence for System (5)
We now give a lower-bound estimate for the radius of the sphere of convergence of Newton's
method on system (5), which is independent of the value of -. This result shows that the sphere
of convergence is bounded away from zero as - ! 0.
Proposition 3.1. Under the nondegeneracy assumption, there exist constants R ? 0 and
~
such that for any - ~
-, the radius of the sphere of convergence, r P (-), of Newton's
method satisfies
Proof. We will show that Newton's method applied to system (5) generates iterates that
converge to the solution (x
the initial point
which then implies that r P (- R ? 0.
At a given value of -, let (x;
respectively the current iterate and
the solution of Newton's method applied to system (5). Since F 0
by continuity there exist positive constants j and D such that
is independent of -.
choose ~
- such that for all - ~
-,
x
y
z
Now let (x;
-. Then
x
y
z
Hence, for such chosen - and (x; y; z), the Jacobian F 0
is nonsingular and satisfies
in view of (28).
The Newton iterates are of the formB B @
z +C C A =B B @
x
y
Hence,
It follows from (29) that if the initial iterate
for any value of - 2 (0; ~ -), Newton's method converges to the solution (x
a lower bound estimate for the radius of the sphere of convergence of Newton's method is
which is independent of -. 2
Our analysis shows that the radius of the sphere of convergence is independent of - and thus
stays bounded away from zero as - ! 0. This result indicates that the sphere of convergence
associated with system (5) would eventually be larger than the sphere of convergence associated
with system (3); that is, at least for small - values, r B (- r P (-). In the next section, we show
numerically that this is indeed the case.
4. Sphere of Convergence: Numerical Results
In Section 3, we provided bounds on the radii of the spheres of convergence of Newton's method
on systems (3) and (5) under the nondegeneracy assumption. Our analysis shows that at least
for small values of -, the sphere of convergence for system (5) is larger than that for system (3).
In this section, we try to compute numerical upper-bound estimates on the radii of the spheres
of convergence for Newton's method on systems (3) and (5). The purpose of these computations
is not only to confirm our theory for nondegenerate problems for small values of -, but also to
obtain empirical information on degenerate problems and for relatively large values of -.
4.1. Description of the Numerical Experiments
We note that (a) the variables are (x; y) for system (3), and (x;
(z
(c) the variable y appears linearly in both systems (3) and (5). For the sake
of comparison, we will only estimate the radii of the spheres of convergence for both systems
in the x-space, using a fixed initial point for y. More specifically, for any given - ? 0 and any
chosen initial point x 0 , we set y In the rest of the section, the term
"sphere of convergence" is always restricted to the x-space only.
Our upper-bound estimates are based on the following simple idea. Let x ff 2 R n be an
arbitrary unit vector and - ? 0 be a scalar. Consider applying Newton's method to systems (3)
and (5) starting from initial points of the form
and with z (5). If for - ff ? 0, Newton's method does not converge
to
(or to (x
-(X
system (5)), then obviously - ff is an
upper bound for the radius of the sphere of convergence of Newton's method at x
- . This upper
bound is the tightest possible in this particular direction if Newton's method converges to x
- for
any - 2 (0; - ff ). Numerically, this upper bound - ff can be approximated by gradually increasing
- from zero by a small increment until Newton's method fails to converge. We can generate a
tighter upper bound by calculating - ff for a set of random unit vectors fx ff g, and then taking
min ff f- ff g as an upper bound.
Under the nondegeneracy assumption, for system (5) Newton's method is well-defined in a
neighborhood of the solution to the linear program, which includes negative values for x and
z. Therefore, we can choose x ff to be any unit random vector. In our experiments on system
(5), ten unit random vectors x ff are selected using the Matlab function randn followed by a
normalization.
As we mentioned earlier, because of the presence of the term X \Gamma1 , system (3) is not well-defined
nor is Newton's method in any neighborhood of the solution to the linear
program. This fact implies that the sphere of convergence of Newton's method shrinks to zero
However, it is not clear at all that the largest half-sphere inside the positive orthant
where Newton's method is well-defined and convergent should also shrink to zero as - ! 0.
To be fair to system (3), we use only positive unit random vectors x ff . In this way, we
actually estimate an upper bound for the radius of the "half-sphere" of convergence instead of
the sphere of convergence. In our experiments on system (3), ten positive unit random vectors
x ff are selected using the Matlab function rand followed by a normalization.
To observe the behavior of the radii of the half-sphere of convergence for system (3) and of
the sphere of convergence for system (5) as - ! 0, the numerical procedure described above
was performed for a set of values of - ? 0:
We include large values of in order to see the behavior of the radius of the
sphere of convergence of Newton's method when far from the solution at The parameter
- in (30) was given an initial value of 10 \Gamma10 and was incremented when the convergence criteria
was satisfied at some iteration k, where v
Such residual definitions were designed to prevent the stopping
criterion from being in favor of one system or another. Nonconvergence was recorded for a
particular run with a given - value and initial point of the form given in (30) if the maximum
number of iterations, which we set to 50, was reached. The convergence tolerance was set to
. The numerical solution v
was obtained by solving system (5) with a given value of
- in (31) and with a stopping tolerance of 10 \Gamma8 . In particular, system (5) was solved using an
interior-point primal-dual method.
For the given set of - values, the estimates for the radii of the half-sphere or sphere of
convergence were recorded as min ff f- ff g, where by our construction -
- k, and
We emphasize that in these experiments, we always used the pure Newton's
method with the unit step-length.
In our implementation, we used a plain partial-pivoting Gaussian elimination (Matlab back-
slash) to solve all linear equations in computing Newton directions for both systems (3) and
(5). This should minimize the effect of ill-conditioning caused by different elimination schemes
that exploit sparsity.
4.2. Test Problems
Test problems consisted of six randomly generated problems r1-r6 which are all nondegenerate,
the Netlib nondegenerate problems: scagr7, sc50b, share1b and the Netlib degenerate prob-
lems: adlittle, afiro, blend, sc50a, and share2b. For the random problems, the data
were generated from a uniform distribution on the interval (0; 1) using the Matlab function
rand. For a given problem, the same ten unit random vectors x ff were used for all values of - in
(31). The problems were run on a Sun Ultra Sparc workstation using Matlab version 5.1. Test
problem dimensions can be found in Table I, where the first nine problems are nondegenerate
and the last five are degenerate. We mention that some Netlib problems are not in the standard
form and have inequality constraints, and the numbers of variables shown are before the addition
of slack variables.
4.3. Results for Nondegenerate Problems
We present numerical results for only four nondegenerate problems since we obtained similar
results for the remaining problems. Figures 1-2 show the radii of the half-sphere of convergence
associated with system (3) and the sphere of convergence associated with system (5) graphed
against the values of - given in (31). Figure 1 contains the graph for a random problem, and
the remaining graphs show results for the Netlib problems. The results show that the radius of
the sphere of convergence of Newton's method on system (5) is bounded away from zero even
for - sufficiently small, but the radius of the half-sphere of convergence of Newton's method
on system (3) appears to decrease to zero as - ! 0 in a linear fashion. Furthermore, our tests
show a larger radius of the sphere of convergence of Newton's method on system (5) than on
system (3) even before - becomes small. In the case of problem r2, the radius for system (3) is
noticeably larger than that for system (5) only when - is very large.
4.4. Results for Degenerate Problems
For degenerate problems, we do not have a theory for the radius of the sphere of convergence of
Newton's method on either of the two systems. We hope that numerical results would provide
some empirical information on the behavior of Newton's method applied to these problems.
We present numerical results on four of the five degenerate problems, as shown in Figures 3-4,
omitting results for the problem adlittle because they are similar to the presented results.
The results show that the radius of the half-sphere of convergence of Newton's method on
system (3) appears to decrease to zero as - approaches zero, as in the case with the nondegenerate
problems. We observe that unlike the case of nondegenerate problems, the radius of the
sphere of convergence on system (5) also appears to decrease to zero with -.
In these tests, we observe that the radius of the sphere of convergence of system (5) is always
larger than or equal to the radius of the sphere of convergence of system (3) for all the - values
given in (31). In particular, the radius associated with system (5) stays well above that for
system (3), by at least an order of magnitude, as - ! 0.
5. Conclusions
In this paper, we studied the local behavior of Newton's method on two equivalent systems
from linear programming: the optimality system (3) for the log-barrier formulation of the linear
program and the perturbed optimality system (5) for the linear program itself.
For nondegenerate problems, we have shown that the radius of the sphere of convergence of
Newton's method on system (3) decreases to zero at exactly the same order as - ! 0, while
the radius of the sphere of convergence associated with system (5) stays bounded away from
zero as - ! 0. These theoretical results are established for exact arithmetics and hence are
independent of the numerical conditioning of the Jacobian matrices for systems (3) and (5).
The numerical experiments have confirmed our theoretical results. Interestingly, on the majority
of our test problems the estimated radius of the sphere of convergence of Newton's method
was consistently larger on system (5) than on system (3); not only for small values of -, but also
for medium and large values of - for which numerical ill-conditioning does not play a critical
role.
There are multiple reasons why Newton's method performs more favorably on system (5)
than on system (3) (see (Ref. 10) for a recent work on this subject). Contrary to previous belief,
M. Wright (Ref. 11, 12) has shown that numerical ill-conditioning is not a determining factor.
We believe that the results in this paper provide another fundamental reason why system (5)
should be the system of choice to be used in an interior-point path-following framework. Similar
results have been extended to the nonlinear program and will be reported in a subsequent paper.



--R

Numerical Methods for Unconstrained Optimization and Nonlinear Equations

The Logarithmic Potential Method of Convex Programming
Sequential Unconstrained Minimization Techniques
Hessian Matrices of Penalty Functions for Solving Constrained Optimization Problems.
Analytic Expressions for the Eigenvalues and Eigenvectors of Hessian Matrices of Barrier and Penalty Functions.
A Primal-Dual Interior Point Algorithm for Linear Pro- gramming
An Analogue of Moreau's Proximation Theorem
On the Convergence of the Newton/Log-Barrier Method
Why a Pure Primal Newton Barrier Step May be Infeasible.
Some Properties of the Hessian in the Logarithmic Barrier Function

--TR
A primal-dual interior point algorithm for linear programming
Some properties of the Hessian of the logarithmic barrier function
On the formulation and theory of the Newton interior-point method for nonlinear programming
Ill-Conditioning and Computational Error in Interior Methods for Nonlinear Programming

--CTR
D. C. Jamrog , R. A. Tapia , Y. Zhang, Comparison of two sets of first-order conditions as bases of interior-point Newton methods for optimization with simple bounds, Journal of Optimization Theory and Applications, v.113 n.1, p.21-40, April 2002
equivalent systems;linear programming;newton's method;sphere of convergence