Superlinear Convergence of an Interior-Point Method Despite Dependent Constraints.
We show that an interior-point method for monotone variational inequalities exhibits superlinear convergence provided that all the standard assumptions hold except for the well-known assumption that the Jacobian of the active constraints has full rank at the solution. We show that superlinear convergence occurs even when the constant-rank condition on the Jacobian assumed in an earlier work does not hold.
Introduction
. We consider the following monotone variational inequality
over a closed convex set C ae
Find z 2 C such that (z
(1)
and the set C is defined by the following algebraic inequality:
. The mapping \Phi is assumed to be C 1 (continuously differentiable)
and monotone; that is,
while each component function g i (\Delta) of g(\Delta) is convex and twice continuously differentiable

By introducing g(\Delta) explicitly into the problem (1), we obtain the following mixed
nonlinear complementarity (NCP) problem: Find the vector triple (z; -; y) 2 IR n+2m
such that
y
\Gammag(z)
(2)
is the C 1 function defined by
It is well known [3] that, under suitable conditions on g such as the Slater constraint
qualification, z solves (1) if and only if there exists a multiplier - such that (z; -)
solves (2).
To show superlinear (local) convergence in methods for nonlinear programs, on
eusually makes several assumptions with regard to the solution point. Until recently,
these assumptions included (local) uniqueness of the solution (z; -; y). This uniqueness
condition was relaxed somewhat in [6] to allow for several multipliers - corresponding
Department of Mathematics, The University of Melbourne, Parkville, Victoria 3052, Australia.
The work of this author was supported by the Australian Research Council.
y Mathematics and Computer Science Division, Argonne National Laboratory, 9700 South Cass
Avenue, Argonne, Illinois 60439, U.S.A. This work was supported by the Mathematical, Information,
and Computational Sciences Division subprogram of the Office of Computational and Technology
Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.
to a locally unique solution z   of (1), by introducing a constant rank condition on the
gradients of the constraints g i that are active at z   . The point of this article is to show
that superlinear convergence holds in the previous setting [6] even when the constant
rank condition does not hold. This result lends theoretical support to our numerical
observations [6, Section 7]. Moreover, we believe that the superlinear convergence
result can be shown for other interior-point methods whose search directions are
asymptotically the same as the pure Newton (affine-scaling) direction defined below
(6).
Briefly stated, the assumptions we make to obtain the superlinear results are as
follows: monotonicity and differentiability of the mapping from (z; -) to (f(z; -); \Gammag(z)),
such that the partial derivative with respect to z is Lipschitz near z   ; a positive definiteness
condition to ensure invertibility of the linear system that is solved at each iteration
of the interior-point method; the Slater constraint qualification on g; existence
of a strictly complementary solution; and a second-order condition that guarantees
local uniqueness of the solution z   of (1). A formal statement of these assumptions
and further details are given in Section 2.2. Superlinear convergence has been proved
for other methods for nonlinear programming without the strict complementarity as-
sumption, but these results typically require the Jacobian of active constraints to have
full rank (see Pang [5], Bonnans [1], and Facchinei, Fischer, and Kanzow [2]).
Possibly the best known application of (1) is the convex programming problem
defined by
min
z
OE(z) subject to z 2 C;
DOE. It is easy to show that the
formulation (2),(3) is equivalent to the standard Karush-Kuhn-Tucker (KKT)
conditions for (4). If a constraint qualification holds, then solutions of (4) correspond,
via Lagrange multipliers, to solutions of (2)-(3) and, in addition, solutions of (1) and
coincide.
We consider the solution of (1) by the interior-point algorithm of Ralph and
Wright [6], which is in turn a natural extension of the safe-step/fast-step algorithm
of Wright [7] for monotone linear complementarity problems. The algorithm is based
on a restatement of the problem (2) as a set of constrained nonlinear equations, as
\Gamma\LambdaY e5 =4 r f (z; -)
r g (z; y)
where the residuals r f and r g are defined in an obvious way. All iterates (z
satisfy the positivity conditions strictly; that is, (-
The interior-point algorithm can be viewed as a modified Newton's method applied to
the equality conditions in (5), in which search directions and step lengths are chosen
to maintain the positivity condition on (-; y). Near a solution, the algorithm takes
steps along the pure Newton direction defined by4 D z f Dg T 0
\Delta-
r g (z; y)
The solution (\Deltaz; \Delta-; \Deltay) of this system is also known as the affine-scaling direction.
The duality measure defined by
is used frequently in our analysis as a measure of nonoptimality and infeasibility.
To extend the superlinear convergence result of [6] without a constant rank condition
on the active constraint Jacobian, we show that the affine-scaling step defined
by (6) has size O(-). Hence, the superlinearity result can be extended to most algorithms
that take near-unit steps along directions that are asymptotically the same as
the affine-scaling direction.
Since we are extending our work in [6], much of the analysis in that earlier paper,
much of the analysis in the earlier work carries over without modification to the present
case, and we omit many of the details here. We focus instead on the main technical
result needed to prove fast local convergence-the estimate (\Deltaz; \Delta-;
the affine-scaling step-and restate just enough of the earlier material to make the
current note self-contained.
2. The Algorithm. In this section, we review the notation, assumptions, and
the statement of the algorithm from Ralph and Wright [6]. We also state the main
global and superlinear convergence results, which differ from the corresponding theorems
in [6] only in the absence of the constant rank assumption.
2.1. Notation and Terminology. We use S to denote the solution set for (2),
and S z;- to denote its projection onto its first
For a particular z   to be defined in Assumption 4, we define
We can partition f1; into basic and nonbasic index sets B and N such
that for all solutions (z
The solution (z strictly complementary if -
for all
We use -N and -B to denote the subvectors of - that correspond to the index sets
N and B, respectively. Similarly, we use DgB (z) to denote the jBj \Theta n row submatrix
of Dg(z) corresponding to B.
Finally, if we do not specify the arguments for functions g, Dg, f , and so on, they
are understood to be the appropriate components of the current point (z; -; y). The
notation Dg   refers to Dg(z   ).
2.2. Assumptions. Here we give a formal statement of the assumptions needed
for global and superlinear convergence. Some motivation is given here, but we refer
the reader to the earlier paper [6] for further details.
The first assumption ensures that the mapping f defined by (3) is monotone with
respect to z and therefore that the mapping (z; -) ! (f(z; -); \Gammag(z)) is monotone.
Assumption 1. \Phi : and each component function
The second assumption requires positive definiteness of a certain matrix projec-
tion, to ensure that the coefficient matrix of the Newton-like system to be solved for
each step in the interior-point algorithm is nonsingular (see (11)).
Assumption 2. The two-sided projection of the matrix
D z f(z;
onto ker Dg(z) is positive definite for all z 2 IR n and -
that is, for any basis
Z of ker Dg(z), the matrix Z T D z f(z; -)Z is invertible.
Note that this assumption is trivially satisfied when the nonnegativity condition
z - 0 is incorporated in the constraint function g(\Delta).
We assume, too, that the Slater condition holds for the constraint function g.
Assumption 3. There is a vector -
z 2 C such that g(-z) ! 0.
Next, we assume the existence (but not uniqueness) of a strictly complementary
solution.
Assumption 4. There is a strictly complementary solution (z
The strict complementarity condition is essential for superlinear convergence in a
number of contexts besides NCP and nonlinear programming. See, for example Wright
[8, Chapter 7] for an analysis of linear programming and Monteiro and Wright [4] for
asymptotic properties of interior-point methods for monotone linear complementarity
problems.
Next, we make a smoothness assumption on \Phi and g in the neighborhood of the
first component z   of the strictly complementary solution from Assumption 4. (We
show in [6, Lemma 4.2] that, under this assumption, z   is the first component of all
solutions.)
Assumption 5. The matrix-valued functions D\Phi and D 2 g i , are
Lipschitz continuous in a neighborhood of z   .
Finally, we make an invertibility assumption on the projection of the Hessian
onto the kernel of the active constraint Jacobian. This assumption is essentially a
second-order sufficient condition for optimality.
Assumption 6. Let z   be defined as in Assumption 4, and let B, S z;- and S
- be
defined as in Section 2. Then for each - 2 S
- , the two-sided projection of D z f(z   ; -)
onto ker(Dg
In the statements of our results, we refer to a set of "standing assumptions,"
which we define as follows:
Standing Assumptions: Assumptions 1-6, together with an assumption
that the algorithm of Ralph and Wright [6] applied to the problem
(2) generates an infinite sequence f(z with a limit
point.
Along with Assumptions 1-6, the superlinear convergence result in Ralph and Wright
[6] requires a constant rank constraint qualification to hold. To be specific, the analysis
of that paper requires the existence of an open neighborhood U of z   such that for
all matrix sequences fH k g ae fDgB (z) T
index sets J ae we have that
However, in the analysis of [6], this assumption is not invoked until Section 5.4, so we
are justified in reusing many results from earlier sections of that paper here. Indeed,
we also reuse results from later sections of [6] by applying them to constant matrices
(which certainly satisfy the constant rank condition).
The algorithm makes use of a family of
defined for positive parameters
and fi as follows:
In particular, the kth iterate (z belongs to \Omega\Gamma
chooses the sequences ffl k g and ffi k g to satisfy
Given the notation
it is easy to see that
Since all iterates (z belong to \Omega\Gamma and since the residual norms kr f k and kr g k
are bounded in terms of - for vectors in this set, we are justified in using - alone as
an indicator of progress, rather than a merit function that also takes account of the
residual norms.
We assume that the sequence of iterates has a limit point, which we denote by
By [6, Theorem 3.2], we have that (z   ; -; y   S. We are particularly interested in
points
in\Omega that lie close to this limit point, so we define the near-solution neighborhood
S(ffi) by
2.3. The Algorithm. The major computational operation in the algorithm is
the repeated solution of 2m-dimensional linear systems of the form4 D z f Dg T 0
\Delta-
r g (z; y)
where the centering parameter ~ oe lies in the range [0; 1
2 ]. These equations are simply
the Newton equations for the nonlinear system of equality conditions from (2), except
for the ~ oe term. The algorithm searches along the direction (\Deltaz; \Delta-; \Deltay) obtained
from (11).
At each iteration, the algorithm performs a fast step along a direction obtained by
solving (6) (or, equivalently, (11) with ~
We choose the
neighborhood\Omega k+1 to
be strictly larger
than\Omega k (by appropriate choice of fl k+1 and fi k+1 ), thereby allowing
a nontrivial step ff k to be taken along this direction without
leaving\Omega k+1 . If the fast
step achieves at least a certain fixed decrease in -, it is accepted as the new iterate.
Otherwise, we
reset\Omega k+1
/\Omega k and defne a safe step by solving (11) with ~
oe chosen in
the range [-oe; 1) for some constant -
We perform a backtracking line search
along this direction, stopping when we identify a value of ff k that achieves a "sufficient
decrease" in - without leaving the
set\Omega k+1 .
The algorithm is parametrized by the following quantities whose roles are explained
more fully in [6].
where exp(\Delta) is the exponential function. The constants fi min and fl max are related to
the starting point (z
The main algorithm is as follows.
terminate with solution (z
else
Although we may calculate both a fast step and a safe step in the same iteration,
the coefficient matrix in (11) is the same for both steps, so the coefficient matrix is
factored only once.
The safe-step procedure is defined as follows.
choose ~ oe 2 [-oe; 1], ff
solve (11) to find (\Deltaz; \Delta-; \Deltay);
choose ff to be the first element in the sequence ff
such that the following conditions are satisfied:
return (z(ff); -(ff); y(ff)).
The fast step routine is described next.
solve (11) with ~
to find (\Deltaz; \Delta-; \Deltay);
set ~
define
choose ff to be the first element in the sequence ff
such that the following conditions are satisfied:
return (z(ff); -(ff); y(ff)).
2.4. Convergence of the Algorithm. The algorithm converges globally according
to the following theorem.
Theorem 2.1. (Ralph and Wright [6, Theorem 3.2]) Suppose that Assumptions 1
and 2 hold. Then either
limit points of f(z belong to S.
Here, however, our focus is on the following local superlinear convergence theorem.
It is simply a restatement of [6, Theorem 3.3] without the constant rank condition on
the active constraint Jacobian matrix [6, Assumption 7].
Theorem 2.2. Suppose that Assumptions 1, 2, 3, 4, 5, and 6 are satisfied and
that the sequence f(z is infinite, with a limit point (z   ; -; y   S. Then the
algorithm eventually always takes fast steps, and
(i) the sequence f- k g converges superlinearly to zero with Q-order at least 1
and
(ii) the sequence f(z converges superlinearly to (z   ; -; y   ) with R-order
at least 1
- .
The proof of this result follows that of the earlier paper in all respects except for
the estimate
for the affine-scaling step calculated from (6). The remainder of this section is devoted
to proving that this estimate holds under the given assumptions.
3. An O(-) Estimate for the Affine-Scaling Step. Our strategy for proving
the estimate (12) for the step (6) is based on a partitioning of the right-hand side in
(6). The following vectors are useful in defining the partition.
(13a)
(13c)
(13d)
where z   is defined in Assumption 4 and (z   ; -) is the projection of the current point
(z; -) onto the set S z;- of (z; -) solution components. The right-hand side of (6) can
be partitioned as4 r f
r g
\Gamma\LambdaY e5 =4 j f
\Gamma\LambdaY e5 +4 ffl f
We define a corresponding splitting of the affine-scaling step:
the following linear systems:4 D z f (Dg) T 0
We define a third variant on (6) as follows:4 D z f (Dg
\Gamma(Dg
c
\Deltaz
c
\Delta-
\Deltay7 5 =4 -
and split the step ( c
\Deltaz; c
\Delta-; c
\Deltay) as
\Deltaz; c
\Delta-; c
t; ~ u; ~ v)
v) and ( ~ t
\Gamma(Dg
~ u
\Gamma(Dg
~
Because of Assumption 2, the matrices in (15), (16), (17), (19), and (20) are all
invertible, so all these systems have unique solutions.
Our basic strategy for proving the estimate (12) is as follows. From [6, Section 5.3],
we have without assuming the constant rank condition that
positive constant. The constant rank assumption
is, however, needed in [6] to prove that the other step component (t; u; v) is also O(-).
In this article, we obtain the same estimate without the constant rank assumption, by
proving that
\Deltaz; c
\Delta-; c
\Deltay
for all (z; -; y) 2 S(ffi).
Our first result, proved in the earlier paper [6], collects some bounds that are
useful throughout this section.
Lemma 3.1. [6, Lemma 5.1] Suppose that the standing assumptions hold. Then
there is a constant C 1 such that the following bounds hold for all (z; -; y) 2 S(1):
(22a)
(22c)
Lemma 3.1 implies that the limit point (z   ; -
defined in (9) has
The second result is as follows.
Lemma 3.2. (cf. [6, Lemma 5.2]) Suppose that the standing assumptions are
satisfied. Then there are constants - such that for all (z; -; y) 2
\Deltaz; c
\Delta-; c
\Deltay) of (17) and ( ~ t; ~ u; ~ v) of (19) satisfy
and
respectively.
Proof. We claim first that the right-hand-side components of (17) and (19) are
O(-). From [6, Equation (78)], we have that
for some positive constants C 2;1 and 1). By Lipschitz continuity (Assump-
tion 5), the definitions (8) and (10), and the fact that f(z   ; -
-) is
defined in (13), there are constants
where L denotes the Lipschitz constant of Assumption 5. (The radius ffi 3 is chosen so
that lies inside the neighborhood of Assumption 5.) For the second right-hand
side component, we have simply that
after a possible adjustment of C 2;2 . For the remaining right-hand-side component in
(17), we have trivially that
Consider now the system (17). As in the proof of [6, Lemma 5.2], we have that
eliminating the c
\Deltay component we obtain
\Deltaz
c
\Delta-
We reduce the system further by eliminating the vector c
\Delta- N to obtain
(D z f)
(Dg
\Gamma(Dg
\Deltaz
c
One can easily see that the right-hand-side vector in this expression is O(-), because
of (27), (28) and the bounds (22), which imply that y B , -N , and
N are all O(-)
for (z; -; y) 2
By using the estimate   \Gamma1
3.1 again) and recalling the
notation for the limit point of the sequence, we have for (z; -; y) 2 S(ffi 3 ) that
D z f(z   ; -) (Dg
\Gamma(Dg
\Deltaz
c
f
O(-k c
O(-k c
denotes the right-hand-side vector in (29). By partitioning c
\Deltaz into
its components in ker Dg
B and ran (Dg
we have from Assumption 6 that c
\Deltaz is
bounded in norm by the size of the right-hand side in (30). Hence, there is a constant
C 2;3 such that
for all (z; -; y) 2 S(ffi 3 ). By choosing -
enough that C 2;3 - :5 for
the result (24) follows from some simple manipulation of the inequality
above.
The proof of (25) is similar.
The next result and others following make use of the positive diagonal matrix D
defined by
From Lemma 3.1, there is a constant C 3 such that
for all (z; -; y) 2 S(1).
Lemma 3.3. (cf. [6, Lemma 5.3]) Suppose that the standing assumptions are
satisfied. Then for -
defined in Lemma 3.2, there is C 4 ? 0 such that
for all (z; -; y) 2 S( -
Proof. First, let -
ffi be defined in Lemma 3.2, but adjusted if necessary to ensure
that
The proof closely follows that of [6, Lemma 5.3], but we spell out the details here
because the analytical techniques are also needed in a later result (Theorem 3.8).
Recall the splitting (18) of the step ( c
\Deltaz; c
\Delta-; c
\Deltay) into components ( ~ t; ~
defined by (19) and (20), respectively. By multiplying the last block row in
(20) by   \Gamma1=2 Y \Gamma1=2 and using (31), we find that
e:
Using (20) again, we obtain
(D z f) ~
since D z f is positive semidefinite by Assumption 1. Hence, by taking inner products
of both sides in (35), we obtain
and therefore
For ( ~ t; ~ u; ~ v), the third block row in (19) implies that Therefore,
we have
\Gamma(Dg   ) ~
(D z f) ~
where again we have used monotonicity of D z f . Define the constant C 4;1 as
From (25), (27), (32), and (34), we have for (z; -; y) 2 S( - ffi ) that
From (28) and (32), we have
By substituting the last two bounds into (37), we obtain
It follows from this inequality by a standard argument that
for some constant C 4;2 depending only on C 4;1 , and -
. By combining this bound with
(18) and (36), we obtain
\Delta-k
and the first part of (33) follows if we define C
the second part of (33) follows likewise.
Bounds on some of the components of c
\Delta- and c
\Deltay follow easily from Lemma 3.3.
Theorem 3.4. (cf. [6, Theorem 5.4]) Suppose that the standing assumptions are
satisfied. Then there are positive constants - ffi and C 5 such that
\Delta-
\Deltay
Proof. Let - ffi be as defined in Lemma 3.3. From the definition (31) and the bounds
(33), we have
c
for any i 2 N . Hence, by using (22), we obtain
min
which proves that k c
\Delta- for an obvious choice of C 5 . The bound on c
\Deltay B is
derived similarly.
Lemma 3.5. (cf. [6, Lemma 5.10]) Let ; 6= J ae B and ; 6= K ae N . If the
two-sided projection of D z f(z; -) onto ker Dg
B is positive definite, then for t 2 IR n
and -J 2 IR jJ j , we have that
(D z f) (Dg
\GammaDg
if and only if
In addition, we have that
dimker
(D z f) (Dg
\GammaDg   0 \GammaI \DeltaK
Proof. This result differs from [6, Lemma 5.10] only in that z   replaces z as the
argument of Dg(\Delta). The proof is essentially unchanged.
By Assumptions 5 and 6, the two-sided projection of D z f(z; -) onto the kernel of
(Dg
positive definite for all (z; -; y) sufficiently close to the limit point (z   ; -; y   )
defined in (9). It follows from Lemma 3.5 and (23) that the set
ae- D z f(z; -) (Dg
\Gamma(Dg
oe
has constant column rank for some -
Theorem 3.6. Suppose that the standing assumptions hold. Then there is a
positive constant ~
ffi such that for all (z; -; y) 2 S( ~ ffi ), we have that ( c
\Deltaz; c
\Deltay N ) is
the solution of the following convex quadratic program:
min
subject to
\Gamma(Dg
uB
\Delta- N
I \DeltaB
c
\Deltay B
Moreover, there is a constant C 6 such that
\Deltay
\Deltay B )k:
Proof. The value ~
ffi from (39) and -
ffi from Theorem 3.4, suffices
to prove this result. The technique of proof is by now familiar (it follows the proof of
[6, Theorem 5.12] closely), and we omit the details.
At this point, we have proved the first estimate in (21), as we summarize in the
following theorem.
Theorem 3.7. Suppose that the standing assumptions hold. Then there are
constants ~
7 such that for any (z; -; y) 2 S( ~ ffi ) we have
\Deltaz; c
\Delta-; c
Proof. Let ~
ffi be as defined in Theorem 3.6. From Theorem 3.4, (27), and (28), we
have for (z; -; y) 2 S( ~
\Deltay
Hence, from (41) we have also that
\Deltay
and it follows from (24) that k c
Our last result is concerned with the second estimate in (21) involving the relationship
between (t; u; v) and ( c
\Deltaz; c
\Delta-; c
\Deltay).
Theorem 3.8. Suppose that the standing assumptions hold. Then there are
positive constants ffi ? 0 and C 8 such that
\Deltay
for all (z; -; y) 2 S(ffi).
Proof. By taking differences of (15) and (17), we obtain4 D z f (Dg) T 0
c
c
c
\Deltay
\Delta-
\Deltaz
We have from (26), Lipschitz continuity of Dg(\Delta) (Assumption 5), and Theorem 3.7
that there is a radius ffi 4 2 (0; ~
\Delta-
\Deltaz3
The remainder of the proof follows that of [6, Lemma 5.7]. By applying the
technique used in Lemma 3.2 to the system (42), and using the estimate (43), we
have that there are constants
Next, we note that the technique used in the second half of the proof of Lemma 3.3
can be used to prove that there is
\Deltay
where D is the diagonal scaling matrix defined in (31). Modifications are needed only
to account for the different right-hand side estimate (43) and the different estimate
(44) of k c
we omit the details. From (32) and (45), it follows immediately that
\Deltay
The final estimate for ( c
obtained by substituting these expressions into (44).
Corollary 3.9. Suppose that the standing assumptions hold. Then there are
constants 9 such that the affine-scaling step defined by (6) satisfies
Proof. We have from Theorems 3.7 and 3.8 that (t; u; defined as in
Theorem 3.8. Moreover, it follows directly from [6, Section 5.3] that
possibly after some adjustment of ffi . Hence, the result follows from (14).
4. Conclusions. The result proved here explains the numerical experience reported
in Section 7 of Ralph and Wright [6], in which the convergence behavior of
our test problems seemed to be the same regardless of whether the active constraint
Jacobian satisfied the constant rank condition. We speculated in [6] about possible
relaxation of the constant rank condition and have verified in this article that, in fact,
this condition can be dispensed with altogether.
Our results are possibly the first proofs of superlinear convergence in nonlinear
programming without multiplier nondegeneracy or uniqueness.



--R

Local study of Newton type algorithms for constrained problems
On the accurate identification of active constraints
A survey of theory
Local convergence of interior-point algorithms for degenerate monotone LCP
Convergence of splitting and Newton methods for complementarity problems: An application of some sensitivity results
Superlinear convergence of an interior-point method for monotone variational inequalities


--TR

--CTR
Hiroshi Yamashita , Hiroshi Yabe, Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems, Computational Optimization and Applications, v.31 n.2, p.123-143, June      2005
Lus N. Vicente , Stephen J. Wright, Local Convergence of a Primal-Dual Method for Degenerate Nonlinear Programming, Computational Optimization and Applications, v.22 n.3, p.311-328, September 2002
Huang , Defeng Sun , Gongyun Zhao, A Smoothing Newton-Type Algorithm of Stronger Convergence for the Quadratically Constrained Convex Quadratic Programming, Computational Optimization and Applications, v.35 n.2, p.199-237, October   2006
interior-point method;superlinear convergence;monotone variational inequalities