A Potential Reduction Newton Method for Constrained Equations.
Extending our previous work [T. Wang, R. D. C. Monteiro, and J.-S. Pang, Math. Programming, 74 (1996), pp. 159--195], this paper presents a general potential reduction Newton method for solving a constrained system of nonlinear equations. A major convergence result for the method is established. Specializations of the method to a convex semidefinite program and a monotone complementarity problem in symmetric matrices are discussed. Strengthened convergence results are established in the context of these specializations.
Introduction
In the paper [11], we have introduced the problem of solving a system of nonlinear equations
subject to additional constraints on the variables, i.e., a constrained system of equations. We
have demonstrated that constrained equations (CEs) provide a unifying framework for the study
of complementarity problems of various types, including the standard nonlinear complementarity
problem and the Karush-Kuhn-Tucker system of a variational inequality. Postulating a partitioning
property of the CE, we have introduced an interior point potential reduction algorithm for solving
the CE and applied this method to convex programs of different kinds. The goal of this paper is
to present a potential reduction Newton method for solving a CE, without assuming the existence
of the partitioning property that is key to the previous work.
The central problem studied in this paper is stated as follows. Let be a given
mapping from the real Euclidean space ! n into itself and
let\Omega be a given closed subset of ! n . The
constrained equation defined by the
find a vector x
We refer the reader to [11] for the initial motivation to study the CE. Later in this paper, we will
consider applications of our results to a semidefinite convex program and a monotone complementarity
problem on the cone of positive semidefinite matrices. These applications yield new interior
This work was based on research supported by the National Science Foundation under grants INT-9600343 and
CCR-970048 and the Office of Naval Research under grant N00014-94-1-0340.
y This work was based on research supported by the National Science Foundation under grant CCR-9213739 and
by the Office of Naval Research under grant N00014-93-1-0228.
point methods for solving these problems whose convergence can be established under some mild
assumptions.
The method proposed in this paper for solving the
combines ideas from the classical
damped Newton method for solving the unconstrained system of equations
and the family of interior point methods for solving constrained optimization and complementarity
problems. A general convergence theory for the proposed method will be presented and specializations
of the results to the aforementioned applications will be described. Unlike the previous study
[11] where we assume that the function H(x) has a certain partition conformal to the
set\Omega\Gamma we
make no such assumption herein. Instead, the present work is based on a set of broad hypotheses
on the
We explain some terminology and fix the notation used throughout the paper. For a given subset
S of ! n , we let int S, cl S, and bd S denote, respectively, the interior, closure, and boundary of S.
If the mapping H is (Fr'echet) differentiable at a point x in its domain, the Jacobian matrix of H
at x is denoted H 0 (x); thus the (i; j)-entry of H 0 (x) is equal to @H i (x)=@x j , for
is the Fr'echet derivative of H at x
along the direction v. If H(x; y) is a function of two arguments (x;
x denote the
partial Jacobian matrix of H with respect to the variable x. For a real-valued function
we write rOE(x) for the gradient vector of OE at the vector x . The p-norm of a vector x is
denoted by kxk p ; in particular, its 2-norm or Euclidean norm is denoted by kxk. For a nonnegative
vector a 2 ! n , we let [0; a] denote the line segment joining the origin and a.
The set of real matrices of order n is denoted M n ; the subset of symmetric matrices in M n
is denoted S n . The set M n forms a finite-dimensional inner-product vector space with the inner
product given by
where "tr" denotes the trace of a matrix. This inner product induces the Frobenius norm for
matrices given by
The subsets of S n consisting of the positive semidefinite and positive definite matrices are denoted
by S n
++ respectively. For two matrices A and B in S n , we write A
similarly, A OE B means
++ . For any matrix A 2 S n
denotes the square root of A;
i.e., A 1=2 is the unique matrix in S n
such that A.
Description and Analysis of the Algorithm
In this section, we describe the potential reduction Newton algorithm for solving the
where\Omega is a closed subset of ! n and H is a continuous mapping
This section is
divided into four subsections as follows: in the first subsection, we lay down the basic assumptions
satisfied by the
in the second subsection, we give some results which guarantee the
existence of a solution for the
in the third subsection, we present the detailed statement
of the algorithm; in the fourth subsection, we establish a convergence theorem for the algorithm.
2.1 Basic assumptions
We introduce several key assumptions on the
Subsequently, these assumptions will be
verified in the context of several applications of the CE.
(A1) The closed
set\Omega has a nonempty interior.
There exists a closed convex set S ' ! n such that
(a)
(b) the (open)
int\Omega is nonempty;
(c) the set H \Gamma1 (int
bd\Omega is empty.
H is continuously differentiable
on\Omega I , and H 0 (x) is nonsingular for all x
2\Omega I .
Assumption (A1) is needed for the applicability of an interior point method. The sets S and
\Omega I in assumption (A2) contain the key elements of the proposed algorithm. Notice that S pertains
to the range of H
and\Omega I to the domain. Initiated at a vector x 0
in\Omega I , the algorithm generates
a sequence of iterates fx k g
ae\Omega I so that the sequence fH(x k )g ae int S will eventually converge
to zero, thus accomplishing the goal of solving the
at least approximately. Assumption
facilitates the application of a Newton scheme for the generation of fx k g; this scheme relies
on a potential function for the
set\Omega I that is induced by such a function for int S. Specifically, we
postulate the existence of a potential function satisfying the following properties:
(A4) for every sequence fu k g ae int S such that
either lim
we have
lim
continuously differentiable on its domain and u T rp(u) ? 0 for all nonzero u 2 int S.
A condition equivalent to (A4) is stated in the following straightforward result.
Condition (A4) holds if and only if for all 0, the set
is compact.
The notion of the central path has played a fundamental role in all interior-point methods for
solving optimization and complementarity problems [2, 4, 5]. Inspired by this notion, we introduce
an important assumption on the potential function p that postulates the existence of a vector
satisfying a certain property; this vector will be used to define a modified Newton direction
that is key to the generation of the iterates for solving the
Although the vector a is
inspired by the central vector of all ones in the case where S is the nonnegative orthant, since our
present setting is very broad, the vector a should not be thought of as just a "central vector" for
int instead, a is closely linked with the potential function p which itself is fairly loosely restricted.
There exists a nonzero vector a 2 ! n and a scalar
oe
(a T u) (a T rp(u))
The basic role of the potential function p is to keep the sequence fH(x k )g away from the set
bd S n f0g while forcing it towards the zero vector. Hence, its role is slightly different from that of
a standard barrier function used in nonlinear programming, which in contrast penalizes an iterate
when it gets close to any boundary point of S. Later, we will identify this function for various sets
S in the applications to semidefinite problems. For now, we will consider the simple case where S
is the nonnegative orthant ! n
and establish the validity of conditions (A4)-(A6) for the function
log
is an arbitrary scalar. (Note: the ' 1 norm of u, instead of u T u, could also be used in
the first logarithmic term. The analysis remains the same with the constant i properly adjusted.)
Clearly, p is norm-coercive on ! n
lim
because for u ? 0,
log
log n
log
where the first and second inequalities follow from the fact that kuk 1  p nkuk and n log(
log u i  n log n, respectively. Moreover, for any positive sequence fu k g converging to a
nonzero nonnegative vector with at least one zero component, the limit (1) clearly holds. Thus
holds. Moreover, with a taken to be the vector of all ones, (A6) also holds. Indeed, we have
for
a
thus
(a T rp(u)) (a T u)
where the last inequality follows from the fact that kuk 1  p n kuk and the arithmetic-geometric
mean inequality.
Other choices for the function p exist for
. The above choice will be generalized to the
case where S involves the cone of symmetric positive semidefinite matrices.
2.2 Existence of solutions
In this subsection, we study conditions that guarantee the existence of solutions of the
We start by giving a few definitions. Assume that M and N are two metric spaces and that
N is a map between these two spaces. For
Eg. The map G is said to be proper with respect to a set
is compact for every compact set K ' E. If G is proper with respect to N ,
we will simply say that G is proper. For D ' M , and E ' N such that G(D) ' E, the restricted
defined by ~
denoted by Gj (D;E) ; if
we write this ~
G simply as GjD . We will also refer to Gj (D;E) as "G restricted to the pair (D; E)",
and to GjD as "G restricted to D". We say that partition of the set V if
space M is said to be connected if there exists no
partition which both O 1 and O 2 are non-empty and open. A metric space M is said
to be path-connected if for any two points there exists a continuous
that
The following result and its proof can be found in Monteiro and Pang [7] (see Corollary 1 of
this reference).
Proposition 1 Let M and N be two metric spaces and N be a continuous map. Let M 0 '
M and N 0 ' N be given sets satisfying the following conditions:
is a local homeomorphism,
Assume that F is proper with respect to some set
E such that N 0 ' E ' N . Then F restricted to the pair (M local
homeomorphism. If, in addition, N 0 is connected, then F cl N 0 .
Using Proposition 1, we now derive two existence results for the
Theorem 1 Assume that conditions (A1)-(A3) hold and that there exists a convex set E ae S such
that
I ) is nonempty and H
proper with respect to E. Then,
.
In particular,
solution.
Proof. To apply Proposition 1, let
j\Omega I , N Using
(A2), we easily see that F (M by (A3) and the
inverse function theorem, it follows that F j M 0 is a local homeomorphism. Since
with respect to E by assumption, it follows from Proposition 1 that
cl cl
where the last equality follows from the fact that cl E) " cl (int
by elementary properties of convex sets (see subsection 2.1 in Chapter 3 of [1]). Moreover, it also
follows from Proposition 1 that restricted to the
int S) is a proper
local homeomorphism.
Theorem 2 Assume that conditions (A1)-(A3) hold and that F is proper with respect to S. Then
restricted
to\Omega I maps each path connected component
of\Omega I homeomorphically
onto int S. In particular,
solution.
Proof. Conclusion (i) follows immediately from Theorem 1 with S. Using the last conclusion
obtained in the proof of Theorem 1 and setting we conclude that F restricted to the pair
(\Omega I ; int S) is a proper local homeomorphism. If T
'\Omega I is a path connected component
of\Omega I
then F restricted to the pair (T ; int S) is a proper local homeomorphism since T is both open and
closed with respect
to\Omega I . Since every proper local homeomorphism from a path connected set into
a convex set is a homeomorphism (see for example Theorem 1 of [7]), (ii) follows.
2.3 The algorithm
The algorithm for solving the
damped Newton method applied to the
Referring the reader to [8] for the basic family of Newton methods for
solving this unconstrained equation, we highlight the modifications to deal with the presence of
the constraint
In essence, there are two major modifications. One, the Newton equation to
compute the search directions is modified using the (central) vector a in assumption (A6). Two,
the merit function for the line searches is based on the merit function:
This is different from the norm functions of H that are the common merit functions used in a
classical damped Newton method. Note that by (A3) and (A5) the function / is continuously
differentiable
on\Omega I .
With the above explanation, we now give the full details of the promised Newton method for
solving the
under the setting given in the last subsection.
Step 0. (Initialization) Let a vector x 0
2\Omega I and scalars ae 2 (0; 1) and ff 2 (0; 1) be given. Let a
sequence of scalars foe k g ae [0;  oe) be also given. (The scalar
oe is as given in assumption (A6).) Set
the iteration counter
Step 1. (Computing the modified Newton direction) Solve the system of linear equations
a
a (3)
to obtain the search direction d k .
Step 2. (Armijo line search) Let m k be the smallest nonnegative integer m such that x k +ae m d k
2\Omega I
and
Step 3. (Termination test) If
prescribed tolerance;
stop; accept x k+1 as an approximate solution of the
Otherwise, return to Step 1 with
k replaced by k + 1.
By (A3) and the fact that x k
2\Omega I , the Newton equation (3) has a unique solution which
we have denoted by d k . The following lemma guarantees that d k is a descent direction for the
function / at x k . This property, along with the openness
of\Omega I , ensures that the integer m k can
be determined in a finite number of trials (starting with increasing it by one at each
thus guaranteeing the well-definedness of the next iterate x k+1 .
Lemma 2 Suppose that conditions (A5) and (A6) hold. Assume also that x
2\Omega I , d
are such that
a T H(x)
where a
are as in condition (A6). Then, r/(x) T d ! 0.
Proof. Let due to (4) and the assumption that x
2\Omega I . This
together with (2), (5), (4), (A5) and (A6) imply
a T u
a
oe
as claimed.
2.4 A convergence result
In what follows, we state and prove a limiting property of an infinite sequence of iterates fx k g
produced by the algorithm. Before stating the theorem, we observe that such a sequence necessarily
belongs to the
set\Omega I ; thus fH(x k )g ae int S. Since the sequence fx k g is infinite, we have
for all k.
Theorem 3 Assume conditions (A1)-(A6) hold and that lim sup k oe k !  oe. Let fx k g be any infinite
sequence produced by the potential reduction Newton algorithm. Then, the following statements
hold:
(a) the sequence fH(x k )g is bounded;
(b) any accumulation point of fx k g, if it exists, solves the
in particular, if fx k g is
bounded then the
solution.
Moreover, for any closed subset E of S containing the sequence fH(x k )g,
(c) if H is proper with respect to
(d) if H is proper with respect to E, then fx k g is bounded.
Proof. Let
all k. Hence, for any " ? 0 we have fu k g ae  "g. Since by Lemma 1 the
set  ("; fl) is compact, and hence bounded, we conclude that fu k g is bounded. Hence, (a) follows.
To show (b), let x 1 be an accumulation point of fx k g. Clearly x 1
2\Omega because\Omega is a closed
set. Assume for contradiction that be a subsequence converging
to x 1 and assume without loss of generality that foe converges to some scalar oe 1 . Since
oe k  0 for all k and lim sup k oe k !  oe, we must have oe 1 2 [0;  oe). Since p(u k )
and
lim
there exists " ? 0 such that the subsequence fu ae  ("; fl). Since by Lemma 1 the
set  ("; fl) is compact, we conclude that u int S, and hence that x 1 2
assumption (A2), it follows that x 1
2\Omega I . Hence, by assumption (A3), H 0
exists. This implies that the sequence fd converges to a vector d 1 satisfying
a
a:
Hence, it follows from Lemma 2 that r/(x 1
converges to x 1
2\Omega I where / is continuous, it follows that f/(x k
converges. This implies that the whole sequence f/(x k )g converges due to the fact that it is
monotonically decreasing. Using the relation
for all k, we conclude that
lim
and hence that
lim
because
lim
Thus
lim
which implies that m k  2 for all k 2  sufficiently large. Consequently, by the definition of m k ,
we deduce that
for all k 2  sufficiently large. Letting k 2  tend to infinity in the above expression, we obtain
which contradicts the fact that ff ! 1 and r/(x 1 Consequently, we must have
0, and hence (b) follows.
Assume now that E is a closed subset of S containing the sequence fH(x k )g. To prove (c),
assume for contradiction that for an infinite subset  ae f0;
lim inf
By an argument similar to that employed above, we conclude that for some " ? 0 we have
and the fact that E is closed, we conclude that  (";
a compact subset of int S " E. Since H is proper with respect to int S " E, the inverse image of
is compact, and hence bounded. This implies that fx is bounded.
By (b), every accumulation point of the latter subsequence is a zero of H . This contradiction
establishes (c).
Finally, using (a) and the fact that E is closed, we conclude that fu k g is contained in a compact
subset E 1 of E. Since H is proper with respect to E, it follows that the set H is
bounded. Hence, (d) follows.
Statements (a), (b) and (c) of Theorem 3 do not claim the boundedness of the sequence fx k g.
In particular, existence of a solution to the
established only under the properness
condition of statement (d). A consequence of statement (c) is
consequently,
in the sense that for any such ", there
exists a vector x "
can be computed by the potential
reduction Newton method starting at the given vector x 0 .
The framework of the
that we have set forth so far is very broad. In addition to
not assuming any sign restriction on the components of H (like we did in [11]; see Assumption 1
therein), part of the generality of the present framework stems from the freedom in the choice of
the set S and the associated potential function p. Indeed, as we shall see in the special cases below,
the set S and the function p can often be constructed under very mild assumptions.
3 Monotone Complementarity Problems in Symmetric Matrices
We consider a mixed complementarity problem defined on the cone of symmetric positive semidefinite
matrices. The linear version of this problem was introduced by Kojima, Shindoh, and Hara
[3] and has received a great deal of research attention recently. In what follows, we consider a non-linear
version of this problem defined in [6]. This reference contains a fairly extensive bibliography
on interior point methods for solving optimization and complementarity problems defined on the
cone of semidefinite matrices; it will be the source for several results that will be used freely in the
subsequent development.
3.1 Implicit mixed complementarity problems
We recall the framework considered in [6]. Let F : S n
be a given mapping. The
mixed complementarity problem in symmetric matrices is to find a triple (X; Y; z) 2 S n \Theta S n \Theta ! m
satisfying
F (X; Y;
\Theta S n
As explained in [6] and the references therein, there are several equivalent ways of stating the
complementarity condition each leading to a different interior point method for solving
the above problem. In what follows, we consider the equivalent formulation of this problem as the
CE defined by the
where the
set\Omega and the
\Theta S n
are defined by
F (X; Y; z)
Similar treatment can be applied to other equivalent formulations and to generalizations of the
basic problem (6). Throughout the following discussion, F is assumed to be continuous on its
domain and continuously differentiable on S n
++ \Theta S n
Associated with the above mapping H , define the set
\Theta S n
g:
It has been shown in Lemma 1 of [6] that
\Theta S n
g:
The fundamental role of the set U in the study of the problem (6) is well explained in this reference.
This set continues to have an important role in the present algorithmic setting for solving the cone
complementarity problem.
We introduce an important assumption on the mapping F that will be used to verify the
nonsingularity of the Jacobian matrix H 0 (X; Y; z).
(B1) The mapping F is (X; Y )-differentiably-monotone at every triple (X; Y; z) 2 U \Theta ! m ; i.e., for
any such triple,
(B2) The mapping F is z-differentiably-injective at every triple (X; Y; z) 2 U \Theta ! m ; i.e., for any
such triple,
The following lemma asserts that the basic assumptions (A1)-(A3) in Subsection 2.1 are valid
under the above hypotheses.
Lemma 3 Consider the
with\Omega and H defined by (7) and (8), and let S j S n
If conditions (B1) and (B2) hold, then
\Omega I j
moreover, the
and the set S satisfy conditions (A1), (A2) and (A3).
Proof. Only the second assertion requires a proof. Conditions (A1) and (A2)(a) obviously hold.
Clearly U is an open set; since (I ; I) 2 U , (A2)(b) holds. Moreover, it is easy to see that the
alternative representation (10) implies (A2)(c). Next we establish that (A3) holds under (B1) and
(B2). This amounts to showing that for every (X; Y; z)
the following implication
holds:
Assume the left-hand condition holds. Then,
Condition (B1) and (14) imply that dX ffl dY  0. This together with (13) and the fact that
(see the proof of Theorem 3.1(iii) of [10]). In turn, this together
with imply
which yields due to (B2).
Next we deal with conditions (A4)-(A6). For this purpose, consider the potential function
++ \Theta S n \Theta defined by
++ \Theta S n
is an arbitrary constant.
Lemma 4 The potential function (15), the vector a j and the scalar
conditions (A4), (A5) and (A6).
Proof. Since for a matrix Z 2 S n , kZk 2
F is equal to the sum of the squares of the n eigenvalues of
Z, and det Z is equal to the product of these eigenvalues, the verification of (A4) for the function
p(M; N; v) is the same as in the previous case of a nonnegatively constrained equation (discussed
at the end of Subsection 2.1). Noting that
we have
and thus (A5) holds. We now show that (A6) is satisfied with the given a and  oe. Indeed we have
which implies
Noting that (i) tr(M) equals the sum of the eigenvalues of M , (ii) tr(M the sum of the
inverses of the same eigenvalues, and (iii) kMk 2
the sum of these eigenvalues
squared, it follows from the same derivation as in the end of Subsection 2.1 that condition (A6)
holds.
According to (2), the potential function (15) induces the following merit function on the set
log
det
for any triple (X; Y; z) 2 U \Theta ! m . Here, k \Delta k F;2 denotes the norm on S n \Theta ! m defined by
We now give a detailed description of a specialized algorithm for solving the mixed complementarity
problem in symmetric matrices (6), based on the potential reduction Newton method for
solving the
oe defined as in (7), (8), Lemma 3, (15)
and Lemma 4, respectively.
Step 0. (Initialization) Let a pair of matrices (X
and ff 2 (0; 1) be given. Let a sequence of scalars foe k g be also given, where oe k 2 [0; 1) for all k.
Set the iteration counter
Step 1. (Computing the modified Newton direction) Solve the system of linear
A
to obtain the search triple (dX
Step 2. (Armijo line search) Let m k be the smallest nonnegative integer m such
and
Step 3. (Termination test) If
prescribed tolerance;
stop; accept the triple (X as an approximate solution of the problem (6). Otherwise,
return to Step 1 with k replaced by k + 1.
As an immediate consequence of Lemma 3, Lemma 4 and Theorem 3, we have the following
convergence result for the above algorithm.
Theorem 4 Assume that conditions (B1) and (B2) hold and lim sup k oe k ! 1. Let f(X
be any infinite sequence produced by the above algorithm for solving problem (6). Then, the following
statements hold:
(a) the sequence fH(X
(b) any accumulation point of exists, solves the problem (6); in particular, if
bounded then problem (6) has a solution.
We now make a few remarks. The above theorem guarantees neither that f(X k
bounded nor that it has an accumulation point. The conclusion that f(X k ; Y k ; z k )g is bounded
would follow from Theorem 3(d) with could prove that the map H is proper with respect
to the set S j S n
. Unfortunately, this requirement is rather strong. For monotone mixed
complementarity problems, we state in Proposition 2 below a result (from Monteiro and Pang [6,
Lemma 2]) asserting that the map H is proper with respect to S n \Theta F (U \Theta ! m ). Hence, if the latter
set contains the set
equivalently if the equality F (U \Theta ! m
then the sequence generated by the above algorithm f(X k ; Y k ; z k )g is bounded. Intuitively, the
equality F (U \Theta ! m hold for maps F satisfying some kind of strong monotonicity
condition. But since this type of condition is fairly restrictive, we do not pursue this issue any
further.
Another possible approach which would guarantee the boundedness of f(X is to
reduce the set S so as to have S ' S n \Theta F (U \Theta ! m ). This approach requires some knowledge of the
set F (U \Theta ! m ). We will see that for the complementarity problems studied in Subsection 3.2 and
Section 4, enough information about the set F (U \Theta ! m ) is available which allows us to choose a set
S together with a potential function satisfying the inclusion S ' S n \Theta F (U \Theta ! m )
and the conditions (A1)-(A6) of Subsection 2.1.
Before stating the properness result mentioned above, we give a few basic definitions.
mapping J(X; Y; z) defined on a subset dom(J) of M n \Theta M n \Theta ! m is said to be
Y )-equilevel-monotone on a subset V ' dom(J) if for any (X; Y; z) 2 V and (X
such that F (X; Y;
will simply say that J is (X; Y )-equilevel-monotone.
In the following two definitions, we assume that W , Z and N are three normed spaces and that
OE(w; z) is a function defined on a subset of W \Theta Z with values in N .
2 The function OE(w; z) is said to be z-bounded on a subset V ' dom(OE) if for every
sequence f(w k ; z k )g ae V such that fw k g and fOE(w k ; z k )g are bounded, the sequence fz k g is also
bounded. When dom(OE), we will simply say that OE is z-bounded.
Definition 3 The function OE(w; z) is said to be z-injective on a subset V ' dom(OE) if the following
implication holds: (w;
we will simply say that OE is z-injective.
The following is the promised result from Lemma 2 of Monteiro and Pang [6].
m be a continuous map and let H
m be the map defined by (8). Assume that the map F is (X; Y )-equilevel-monotone and
z-bounded on its domain. If the map H restricted to U \Theta ! m is a local homeomorphism, then H is
proper with respect to S n \Theta F (U \Theta ! m ).
3.2 Standard complementarity problem
In this section, we consider the standard nonlinear complementarity problem (NCP) in symmetric
matrices:
is a given continuous mapping which is continuously differentiable on S n
++ .
This problem is a special case of the implicit mixed complementarity problem of Subsection 3.1
z is not present) and F : S n
\Theta S n
\Theta S n
We make the following assumption on the mapping f .
is monotone on S n
Lemma 5 If condition (C1) holds then the
\Theta S n
defined by (17) satisfies
condition (B1) of Subsection 3.1.
Proof. By (C1), it follows that for every X 2 S n
, the linear map f 0 (X) is monotone in the sense
that
To verify (B1), assume that (dX; dY equivalently
by (18), we have
This shows that implication (11) holds for since implication (12) holds vacuously for
It is possible to solve the NCP (16) with the use of the potential reduction algorithm described
in Subsection 3.1. However, the sequence of iterates generated by this algorithm might
not be bounded. We now develop a different potential reduction algorithm in which the set S is
reduced so as to have S ' S n
\Theta F (U ), thus ensuring the boundedness of the sequence f(X
(see the discussion at the end of the previous subsection).
To describe the alternative algorithm, it is sufficient to identify the
the set S,
the potential function and the vector a and scalar  oe in condition (A6). We let
\Theta S n
\Theta S n
where F is given by (17). Moreover, we let S j S n
\Theta S n
be defined by
F
\Theta S n
is an arbitrary constant. Finally, we let a j (I ; I) and  oe j 1. Clearly, the
set\Omega I and
the merit function /
and
log
det
Lemma 6 The
the set S, the potential function !, the vector a and the
scalar  oe defined above satisfy conditions (A1)-(A6) of Subsection 2.1.
Proof. Condition (A2)(b) follows from the fact that
2\Omega I for all sufficiently large. The
other conditions are either straightforward or are shown using Lemma 5 and the same arguments
used in the proofs of Lemma 3 and Lemma 4.
Before giving the convergence result for the potential reduction Newton method in the above
framework, we state the following result which will be used to establish boundedness of the iterates
generated by this method.
Lemma 7 Suppose that f : S n
is a continuous map which is continuously differentiable
on S n
++ and satisfies condition (C1). Then, for the maps F and H defined by (17) and (19)
respectively, we have:
(a) F
\Theta S n
proper with respect to S n \Theta S n
(c) if 0 2 F (S n
\Theta S n
proper with respect to S n \Theta S n
Proof. By Proposition 4(a) and Corollary 3 of [6] with
\Theta S n
\Theta S n
). Using this inclusion, we easily see that statement (a) holds.
We next show (b). By Lemma 6, H 0 (X; Y ) is invertible for all (X; Y restricted
to U is a local homeomorphism. Thus it follows from Lemma 2 that H is proper with respect to
once we prove that S n
++ \Theta S n
++ be
arbitrary.
\Theta S n
\Theta S n
such that ~
X). For ffl ? 0,
let
X). Clearly, X ffl  0 for every ffl ? 0. By
the continuity of f and the fact that U
Y  0, we have Y ffl  0 for ffl ? 0 sufficiently small. Since
that U belongs to F (S n
\Theta S n
We omit the proof of (c) which is similar to that of (b).
We will skip the straightforward formulation of the potential reduction Newton method specialized
to the above choices of the
potential function
and scalar  oe; instead we directly give the convergence properties of the method.
Theorem 5
be a continuous function which is continuously differentiable on
++ and satisfies condition (C1). Suppose that f(X k ; Y k )g is a sequence generated by the potential
reduction Newton method with the
potential function
and scalar
oe as specified above. Then, the following statements hold:
(a) every accumulation point of f(X k ; Y k )g is a solution of the NCP (16);
(b) if there exists ~
such that f( ~
(c) if there exists "
++ such that f( "
, then the sequence f(X k ; Y k )g is bounded.
Proof. Statement (a) follows from Theorem 3(b). To prove statement (b), note first that the
assumption implies that 0 2 F (S n
\Theta S n
Hence, by Lemma 7(b), we conclude that H is proper
with respect to S n \Theta S n
++ . It follows from Theorem 3(c) with
to zero. The proof of (c) follows similarly from Lemma 7(c) and Theorem 3(d) with
Statement (a) is within expectation; statement (b) is interesting because its assumption is
the feasibility of the NCP in symmetric matrices (16). A consequence of of statement (b) is that
feasibility of this problem (which is also monotone by assumption (C1)) is sufficient for the sequence
to converge to zero although no boundedness of the sequence f(X k ; Y k )g is asserted.
The latter assertion is established under the strict feasibility of the problem (16); this is statement
(c).
4 Convex Semidefinite Programs
In this section we consider the convex semidefinite program studied in [6, 9], namely:
minimize '(x)
subject to G(x)  0
are given smooth mappings. Under a suitable
constraint qualification, if x   is a locally optimal solution of the semidefinite program, then there
must exist (j   ; U
such that
is the Lagrangian function defined by
Clearly, the first-order optimality condition (21) and the feasibility of x   is equivalent to the implicitly
mixed complementarity problem (6) in which the map F : S n
\Theta S n
is defined by
\Theta S n
and the following correspondence of variables are made: (U; V ) Hence, as
in Subsection 3.1, the feasibility of x   and the first-order optimality condition (21) can be formulated
as the
set\Omega and the
\Theta S n
are defined by
\Theta S n
\Theta S n
Our goal is to solve the
by the potential reduction Newton method. For this purpose,
we make the following blanket assumptions on problem (20):
(D1) the objective function continuously differentiable and convex;
(D2) the map G continuously differentiable and positive semidefinite convex
(psd-convex), that is
(D3) the map affine, and the (constant) gradients frh j (x)g p
are linearly
independent;
(D4) for every (x; U;
the following implication holds:
(D5) the feasible set
is nonempty and bounded.
We propose below a new interior point method for solving the convex semidefinite program
(20) based on the potential reduction Newton algorithm of Subsection 2.3. This method not
only generalizes the algorithm developed in Section 4.2 of [11] to the context of the nonlinear
semidefinite programming problem but it also allows for more general choice of starting points.
The new algorithm uses a novel potential function / which depends on the starting point. A
key advantage of the new algorithm is that strong convergence properties can be established for
arbitrary starting points. This differs from the results in [11] which either require the starting point
to satisfy the linear equality constraint (Theorem 5 in the reference) or do not guarantee
the boundedness of the sequence of multipliers (Theorem 4 in the reference).
p+m denote an arbitrary starting point and let c 0 j h(x 0 ) and
any matrix such that
\Theta S n
Note that S depends on the starting point when
The following technical lemma is a partial restatement of Lemma 6 of [6] and is used in the
subsequent Lemma 9 to establish that the
and the set S defined above satisfy conditions
(A1)-(A3) of Subsection 2.1.
Lemma 8 Assume that G is an affine function. Then
the following statements hold:
(a) for every U 2 S n
, the function x
(b) if condition (D5) holds then, for every
!, the set
is bounded.
Lemma 9 Assume that problem (20) satisfies conditions (D1)-(D4). The following three statements
hold:
(a) the map F defined by (23) satisfies (B1) and (B2) of Subsection 3.1;
(b) the
with\Omega and H defined by (25) and (24), respectively, and the set S defined by
(26), satisfy conditions (A1), (A2) and (A3) of Subsection 2.1; and
(c) the map H restricted to the set U \Theta ! p+m is a local homeomorphism.
Proof. Since the case where c is easy to deal with, the proof below focuses on the case where
Conditions (A1) and (A2)(a) are obvious. Clearly, we have
which is nonempty because it contains the tuple (U using (10) we easily see
that the set H \Gamma1 (int
bd\Omega is empty. We have thus proved that condition (A2) holds. Using
the same arguments as in the proof of Lemma 3, we can show that if statement (a) holds, then
is nonsingular for every (U; V; j; x) 2 U \Theta ! p+m ; in particular, we can conclude that
holds due to (27), and that H restricted to the set U \Theta ! p+m is a local homeomorphism by
the inverse function theorem. Thus the remaining proof is to show that F satisfies (B1) and (B2).
For this purpose, assume that (U; V; x;
for some (dU; dV; dx; dj) 2 S n \Theta S n \Theta ! p+m , or equivalently
Lemma 8(a) together with conditions (D1), (D2) and (D3) and the fact that U  0 imply that
L(x; U; j) is a convex function of x. Hence, we have that dx T L 00
xx (x; U; j)dx  0. Multiplying (29)
on the left by dx T and using this last observation together with (28) and (30), we obtain
xx (x; U; j)dx  0: (31)
Thus F satisfies (B1). Assume now that
Then all the relations above hold with (dU; dV In particular, (28), (30) and (31) imply
that h 0 (x;
Hence, we conclude that
to (D4). Using this and the fact that relation (29) hold with
which in turn implies that due to (D3). We have thus shown that F satisfies (B2).
Associated with the set S, we now introduce the following potential function
defined for any tuple (A; B; c; d) 2 int S by
det
where i is a suitable constant.
We establish in the next result that if i  3n=2, then the above potential function satisfies
conditions (A4), (A5) and (A6) of Subsection 2.1.
then the potential function (32), the tuple a
and the constant
conditions (A4), (A5) and (A6) of Subsection 2.1.
Proof. The verification of (A4) is similar to the one of Lemma 4. Define
~
It is easy to see that
~
~
~
The definition of  and ~
together with a simple algebraic manipulation reveals that
and hence that (A5) holds. Moreover, using the fact that
F and (trP
for every P 2 S n and i  3n=2, we obtain for every (A; B; c; d) 2 int S,
2i
F
Hence (A6) holds with
The next two results will be used in Theorem 3 to establish the boundedness of the sequence of
iterates generated by the potential reduction Newton method under the framework of this section.
Lemma 11 Assume that problem (20) satisfies conditions (D1)-(D5). Then the
\Theta
defined in (25) is proper with respect to the set S n \Theta F (U \Theta ! p+m ).
Proof. Using Proposition 4(a) and Lemma 7 of [6], we conclude that the map F defined in (23) is
)-equilevel monotone on S n
\Theta S n
\Theta ! p+m . Moreover, by Proposition 4(c) and Lemma 9 of [6],
it follows that F is (j; x)-bounded on S n
p+m . Since by Lemma 9 the map H restricted
to U \Theta ! m+p is a local homeomorphism, we conclude from Proposition 2 that H is proper with
respect to S n \Theta F (U \Theta ! p+m ).
In the next result we describe in more detail the set F (U \Theta ! p+m ) for the map F given by (23).
Lemma 12 Assume that problem (20) satisfies conditions (D1)-(D5). Then F (U \Theta ! p+m
is the map given by (23) and
Moreover, F is a convex set.
Proof. The inclusion F (U \Theta ! p+m straightforwardly from the definition of the
map F and the set U . Assume now that (B; c; d) 2 F \Theta ! m . We have proved in Lemma 10 of [6]
that if conditions (D1)-(D5) holds and (0; Consider now the
problem
minimize ~
subject to ~
where ~
. It is easy to
see that the functions ~
G and ~
h also satisfies conditions (D1)-(D5). Hence, applying Lemma
of [6] to this new problem, we conclude that (0; 0;
F is defined like the
function F in (23) with ', G and h replaced by ~
G and ~ h, respectively. A simple verification
shows that (0; 0;
F (U \Theta ! p+m ) is equivalent to (B; c; d) 2 F (U \Theta ! p+m ). We have thus shown
that F (U \Theta ! p+m Using conditions (D2) and (D3), and some standard arguments, we
can easily show that F is a convex set.
We establish one technical lemma which will be used to prove an important conclusion of the
main result of this section, Theorem 6.
Lemma 13 Let fU k g and fV k g be two sequences in S n
++ such that
lim
Then
lim
Proof. Since its eigenvalues are all real. Since
it follows that all the eigenvalues of U k V k are real too. This implies that the eigenvalues of (U k
are all positive. Therefore,
Since the right-hand norm converges to zero as k ! 1, the same holds for the left-hand norm.
Thus the spectrum of U k V k converges to the single element f0g. Since this spectrum is the same
as that of (U k the desired limit (33) follows.
The following is the main convergence result of the potential reduction Newton method specialized
to the convex semidefinite program (20).
Theorem 6 Suppose that problem (20) satisfies conditions (D1)-(D5), and that f(U
is a sequence generated by the potential reduction Newton method of Subsection 2.3 initialized at
an arbitrary tuple (U
(25), (26) and (32), respectively, a j Assume also that
1=2. Then, the following statements hold:
(a) every accumulation point of f(U is a solution of the
(b) the sequence f(V k ; x k )g is bounded; thus fx k g has at least one accumulation point;
(c) lim k!1 H(U
(d) every accumulation point of the sequence fx k g is an optimal solution of problem (20);
(e) if there exists
that is problem (20) has a Slater
point, then the whole sequence f(U
Proof. By Lemmas 9 and 10, the assumptions of the theorem guarantee
conditions (A1)-(A6) of Subsection 2.1. Hence,
by Theorem 3, we conclude that statement (a) holds and that the sequence fH(U
bounded. By the definition of H , this implies that fV k are bounded, and
hence fx k g ae fx
8(b) the latter set is bounded, we conclude that fx k g is bounded. Clearly, this and the fact that
bounded imply that fV k g is also bounded. Hence, statement (b) follows.
The proofs of statements (c) and (e) are based on statements (c) and (d) of Theorem 3. For
simplicity, we assume in the remaining proof that c 0 j h(x 0 ) 6= 0; the proof when c
analogous. Define
\Theta
Note that E is a closed subset of S. Moreover, using (D3) and the fact that the third component
of a is zero, we easily see that fh(x k )g ae [0; c 0 ]. Clearly, this implies that fH(U
In view of (c) and (d) Theorem 3, statement (c) and (e) follow once we establish that the map H
is proper with respect to
\Theta
and also proper with respect to E under the assumption that (0; We prove first the
properness assertion with respect to int S " E. By Lemmas 11 and 12, we know that H is proper
with respect to S n \Theta F (U \Theta ! p+m Hence, it suffices to show that int S " E is
contained in S n \Theta F \Theta ! m , or equivalently that
Using the definition of F and Lemma 8(b), it is easy to see that
cl
Moreover, it follows immediately from the definition of F and (35) that
cl F
Let (B; c) be an arbitrary element of the left-hand set in (34). Since c 2 [0; c 0 ], we have
some t 2 [0; 1]. Hence,
Since (0; cl F by (D5), by (26), and cl F is a convex set due to Lemma 12 and
Proposition III.1.2.7 of [1], we conclude that (tG cl F . Hence, by
(37) and (38), we have (B; c) = (B; holds.
Assume now that (0; To prove the properness assertion with respect to E, it suffices to
show that E ' S n \Theta F \Theta ! m , or equivalently
If (B; c) is in the left-hand set then we have
by (26) and F is convex by Lemma 12, we conclude that
Hence, by (36) and the fact that B  tG 0 , we have (B; c) = (B;
holds.
Finally, we prove statement (d). For each k, let
It follows that x k is an optimal solution of the convex program
due to the fact that x k together with the multiplier pair (U the optimality condition
for this problem. Now let x 1 be an arbitrary accumulation point of fx k g. Clearly, x 1 is a feasible
solution of (20) due to Theorem 6(c). To show the global optimality of x 1 , assume that ~
x is
an arbitrary feasible solution of (20). Let t k 2 [0; 1] be such that h(x k
~
is feasible to (40). Since ft k g converges to zero, it follows that
converges to ~ x. Moreover, since H(U by the definition of S (26), we have
for each k (cf. (38)),
Hence, it follows that
log det
for all k. Rearranging this inequality, we obtain
log det
log det
I
log det
log det
where the last inequality follows from the fact that
Hence, as k goes to 1, we may invoke Lemma 13 to conclude that We have
thus proved that x 1 is an optimal solution of (20).
Remark. The significance of part (d) of Theorem 6 is that it does not require the sequence of
multipliers to be unbounded.
Assuming that G 0  0, it is possible to show that the potential function (32), a j
and
the inequality in condition (A6) for every (A; B; c; d) in the set
E is defined in the proof of Theorem 6. Using this fact, it is possible to establish a convergence
result similar to Theorem 6 for a j 1. The crucial point to note is that Theorem
3 still holds if we assume the inequality in condition (A6) to be valid only for points in the sequence
)g. Details are omitted.



--R

Convex Analysis and Minimization Algorithms I
A unified approach to interior point algorithms for linear complementarity problems

The complementarity problem for maximal monotone multifunctions
Pathways to the optimal set in linear programming
On two interior-point mappings for nonlinear semidefinite complementarity problems

Iterative Solution of Nonlinear Equations in Several Variables
First and second order analysis of nonlinear semidefinite programs
Existence of search directions in interior-point algorithms for the SDP and monotone SDLCP programs
An interior point potential reduction method for constrained equations
--TR

--CTR
Samuel Burer , Renato D. C. Monteiro , Yin Zhang, Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation, Computational Optimization and Applications, v.22 n.1, p.49-79, April 2002
Tong , Liqun Qi , Yu-Fei Yang, The Lagrangian Globalization Method for Nonsmooth Constrained Equations, Computational Optimization and Applications, v.33 n.1, p.89-109, January   2006
Christian Kanzow , Nobuo Yamashita , Masao Fukushima, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, Journal of Computational and Applied Mathematics, v.172 n.2, p.375-397, 1 December 2004
Christian Kanzow , Nobuo Yamashita , Masao Fukushima, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, Journal of Computational and Applied Mathematics, v.173 n.2, p.321-343, 15 January 2005
Stefania Bellavia , Maria Macconi , Benedetta Morini, STRSCNE: A Scaled Trust-Region Solver for Constrained Nonlinear Equations, Computational Optimization and Applications, v.28 n.1, p.31-50, April 2004
Jong-Shi Pang , Defeng Sun , Jie Sun, Semismooth homeomorphisms and strong stability of semidefinite and Lorentz complementarity problems, Mathematics of Operations Research, v.28 n.1, p.39-63, February
potential function;global convergence;interior point methods;primal-dual methods;complementarity problems;semidefinite programming;potential reduction algorithm;newton method;constrained equation;variational inequality