On Two Interior-Point Mappings for Nonlinear Semidefinite Complementarity Problems.
Extending our previous work ( Monteiro and Pang 1996), this paper studies properties of two fundamental mappings associated with the family of interior-point methods for solving monotone nonlinear complementarity problems over the cone of symmetric positive semidefinite matrices. The first of these maps lead to a family of new continuous trajectories which include the central trajectory as a special case. These trajectories completely "fill up" the set of interior feasible points of the problem in the same way as the weighted central paths do the interior of the feasible region of a linear program. Unlike the approach based on the theory of maximal monotone maps taken by Shida and Shindoh (1996) and Shida, Shindoh, and Kojima (1995), our approach is based on the theory of local homeomorphic maps in nonlinear analysis.
Introduction
In a series of recent papers (see Kojima, Shida and Shindoh 1995a, Kojima, Shida and Shindoh
1995b, Kojima, Shida and Shindoh 1996, Kojima, Shindoh and Hara 1997, Shida and Shindoh
1996, Shida, Shindoh and Kojima 1995, Shida, Shindoh and Kojima 1996), Hara, Kojima, Shida
and Shindoh have introduced the monotone complementarity problem in symmetric matrices, studied
its properties, and developed interior-point methods for its solution. A major source where this
problem arises is a convex semidefinite program which has in the last couple years attracted a great
deal of attention in the mathematical programming literature (see Alizadeh 1995, Alizadeh, Hae-
berly and Overton 1994, Alizadeh, Haeberly and Overton 1995, Goldfarb and Scheinberg 1996, Luo,
Sturm and Zhang 1996a, Luo, Sturm and Zhang 1996b, Monteiro 1995, Nesterov and Nemirovskii
1994, Nesterov and Todd 1995, Nesterov and Todd 1997, Potra and Sheng 1995, Ramana, Tun-cel
and Wolkowicz 1997, Shapiro 1997, Vandenberghe and Boyd 1996, Zhang 1995). Our goal in this
paper is to extend our previous work Monteiro and Pang (1996) to the monotone complementarity
problem in symmetric matrices and to apply the results to a convex semidefinite program. Although
the present analysis is significantly more involved (for one thing, a great deal of matrix-theoretic
tools is employed), we obtain a large set of conclusions that extend those in Monteiro and Pang
(1996). Similar to the motivation in this reference (which the reader is advised to consult), we undertook
the present study in order to gain an in-depth understanding of the interior point methods,
in particular the limiting behavior of certain solution trajectories, both new and known, for solving
these important mathematical programs defined on the cone of positive semidefinite matrices.
Let M n denote the vector space of n \Theta n matrices with real entries; let S n denote the subspace
of M n consisting of the symmetric matrices; and let ! m denote the m-dimensional Euclidean space
of real vectors. Let S n
denote the subset of S n consisting of the positive semidefinite matrices.
m be a given mapping which we assume to be continuous on S n
(which is isomorphic to the Euclidean space ! n(n+1)=2 ). The complementarity problem which we
shall study in this paper is to find a triple (X; Y; z) 2 S n \Theta S n \Theta ! m satisfying
F (X; Y;
(1)
It is known (see the cited references) that there are several equivalent ways to represent the complementarity
conditions in this problem; namely,
(2)
where "tr" denotes the trace of a matrix. Associated with these equivalent conditions, we can define
mappings that will help us understand the limiting behavior of certain path-following interior point
methods for solving the problem (1). In this paper, we focus on the first two conditions and the
associated mappings. Specifically, a main objective of this paper is to examine properties of the
mapping
defined by
Associated with this map, we define the set
++ \Theta S n
We will give conditions on the mapping F which guarantee that the system
has the following properties:
(P1) it has a solution for every (A; B) 2 S n
(P2) the solution, denoted (X(A; B); Y (A; B); z(A; B)), is unique when
if a sequence
++ \Theta F (U \Theta ! m ) converges to a limit (A1
++ \Theta
F (U \Theta ! m ), then the sequence converges to the limit
if a sequence
++ \Theta F (U \Theta ! m ) converges to a limit (A1
then the sequence
implies the existence of a solution of (1) when
We also consider the map ~
~
and prove under suitable conditions that for every - 0 and B 2 F (S n
++ \Theta S n
~
has a solution, which is is unique when - ? 0. Clearly, this latter result implies that (1) has a
solution under the weaker assumption that 0 2 F (S n
++ \Theta S n
A major difference between the mappings H and ~
H lies in their ranges. Comparing the systems
(5) and (7) with varying right-hand sides, we see that we are able to obtain results for a broader
class of solution trajectories in the case of H than ~
H , with the right-side matrix A in (5) being an
arbitrary symmetric matrix versus the restriction to a positive multiple of the identity matrix in
(7).
The main tool used to derive the above results is a known theory of local homeomorphic maps
summarized in Monteiro and Pang (1996) that has been applied to a standard mixed complementarity
problem defined on ! n
As judged from the papers on semidefinite programming,
the extension of the previous analysis Monteiro and Pang (1996) to the case of complementarity
problems in symmetric positive semidefinite matrices is nontrivial; this thus necessitates our present
investigation.
The complementarity problem (1) arises as the set of first-order necessary optimality conditions
for the following nonlinear semidefinite program (see Shapiro 1997):
minimize '(x)
subject to G(x) 2 \GammaS n
are given smooth mappings. Indeed, it is
well-known (see for example Shapiro 1997) that, under a suitable constraint qualification, if x   is
a local optimal solution of the semidefinite program, then there must exist j
such that
is the Lagrangian function defined by
where
denotes the scalar product of A; Letting
F (U; V; x;
r x L(x; U;
we see that the first-order necessary optimality conditions for problem (8) are exactly in the form
of the complementarity problem (1). For the mapping F in (11), our principal result is Theorem 4
which shows that under some fairly standard assumptions on the functions ', G, and h, the mapping
H defined by (3) maps U \Theta ! m+p homeomorphically onto the convex set S n
++ \Theta F (U \Theta ! m+p );
moreover, H(S n
Before proceeding further, we should relate the formulation (1) with the formulation in Kojima,
Shida and Shindoh (1995a), Kojima, Shida and Shindoh (1995b), Kojima, Shida and Shindoh
(1996), Kojima, Shindoh and Hara (1997), Shida and Shindoh (1996), Shida, Shindoh and Kojima
(1995), Shida, Shindoh and Kojima (1996). Specifically by defining the set
the problem (1) is of the form
which is exactly the central problem studied in the cited references. So in principle the results in
these references (especially Shida and Shindoh 1996, Shida, Shindoh and Kojima 1995 which deal
with nonlinear problems) could be applied to the problem (1), provided that we can demonstrate
that F is a "maximal monotone" subset of S n \Theta S n . By assuming that a certain monotonicity
condition on F holds everywhere on S n \Theta S n \Theta ! m , the maximal monotonicity of F follows from
Theorem 8 in Monteiro and Pang (1996). In this case, the existence and continuity of the solutions
of system (7) follow from the theory presented in Shida, Shindoh and Kojima (1995). However, the
requirement that the function F satisfy the monotonicity condition everywhere on S n \Theta S n \Theta ! m
is quite restrictive; for example, the function F given by (11) satisfies the monotonicity condition
only on the set S n
Our analysis assumes that the monotonicity condition holds only
on the latter set, and thus is valid for the special map F given by (11). Incidentally, under the
weaker monotonicity condition imposed on F , we are able to establish that the set F defined by
(12) is maximal monotone only in a restricted sense, namely with respect to the set U (see Section
6). Section 7 of this paper establishes the results of Shida, Shindoh and Kojima (1995) about the
existence and continuity of the solutions to the system (7) under the weaker monotonicity condition
on F . As far as the system (5) is concerned, properties (P1)-(P4) are shown to be valid here for
the first time.
The following notation is used throughout this paper. The symbols - and - denote, respectively,
the positive semidefinite and positive definite ordering over the set of symmetric matrices; that is,
for positive semidefinite, and X - Y (or Y OE X)
means positive definite. We let M n
++ denote the set of matrices
that respectively. Given U 2 M n and a differentiable function
denote the m-vector whose i-th entry is (@G(x)=@x i
is the partial derivative of G with respect to x i . Finally we let
Preliminaries
In this section, we introduce some further notation and describe some background concepts and
results needed for the subsequent developments. The section is divided into two subsections. The
first subsection summarizes a theory of local homeomorphic maps defined on metric spaces; the
discussion is very brief. We refer the reader to Section 2 of Monteiro and Pang (1996), Chapter 5
of Ortega and Rheinboldt (1970), and Chapter 3 of Ambrosetti and Prodi (1993) for a thorough
treatment of this theory. The second subsection introduces the key conditions on the mapping F
in (1) and establishes some basic properties of the set U defined in (4).
2.1 Local homeomorphic maps
If M and N are two metric spaces, we denote the set of continuous functions from M to N by
C(M;N) and the set of homeomorphisms from M onto N by Hom(M;N ). For G 2 C(M;N ),
Eg. Given
such that G(D) ' E, the restricted mapping ~
defined by ~
denoted by Gj (D;E) ; if then 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". The closure of a subset E of a metric space will be denoted by cl E. Any
continuous function from a closed interval of the real line ! into a metric space will be called a
path. We say that partition of the set V if
space M is said to be connected if there exists no partition
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 path M such that It
is well-known that any path-connected metric space is connected; the converse however does not
always hold. A metric space M is said to be simply-connected if it is path-connected and for any
there exists a continuous mapping ff : [0; 1] \Theta [0; 1] !M
such that ff(s;
A subset C of a vector space is said be star-shaped if there exists c 0 2 C such that the line segment
connecting c 0 to any other point in C is contained entirely in C. Clearly, every star-shaped set in
a normed vector space is simply-connected.
In the rest of this subsection, we will assume that M and N are two metric spaces and that
1 The mapping G 2 C(M;N) is said to be proper with respect to the set E ' N if
is compact for every compact set K ' E. If G is proper with respect to N , we will
simply say that G is proper.
The proofs of the following three results can be found in Section 2 and the Appendix of Monteiro
and Pang (1996).
Proposition 1 Assume that G : M ! N is a local homeomorphism. If M is path-connected and
N is simply-connected then G is proper if and only if G 2 Hom(M;N).
Proposition be given sets satisfying the following conditions: GjM 0
is a local homeomorphism, G(M Assume that G is proper with
respect to some set E such that N 0 ' E ' N . Then H restricted to the pair (M
a proper local homeomorphism. If, in addition, N 0 is connected, then G(M 0
cl N 0 .
Proposition 3 Let M be a path-connected metric space. Assume that is a local
homeomorphism and that G \Gamma1 ([y is compact for any pair of points y
and G(M) is convex.
2.2 Some key concepts
We introduce the key conditions on the map F that will be assumed throughout the paper.
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 J(X; Y; dom (J), we
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 .
Definition 3 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 4 The function OE(w; z) is said to be z-injective on a subset V ' dom (OE) if the following
implication holds: (w;
dom (OE), we will simply say that OE is z-injective.
In the next result, we collect a few technical facts which will be used later. Parts (a) and (b)
are well-known consequences of the self-dual property of the cone S n
. Their proofs are omitted.
Parts (c), (d), and (e) pertain to properties of the set U .
Lemma 1 The following statements hold:
(a) U - 0 if and only if U ffl V - 0 for every V - 0;
(b) if U - 0,
(c)
(d) if (X; Y
then
(e) the set U is star-shaped, thus simply-connected.
Proof. We give a simple proof of (c). Let X; Y 2 S n
be such that XY +Y X - 0. Then XY must
be a P-matrix, and thus it has positive determinant. Hence X and Y are both nonsingular, and
thus positive definite.
By applying the proof of Theorem 3.1(iii) in Shida, Shindoh and Kojima (1996), we can establish
part (d). The details are omitted.
For part (e), observe that (I ; I) 2 U . Now let (X; Y ) be an arbitrary element in U . We will
show that the line segment connecting (I ; I) to (X; Y ) is contained in U , from which part (e)
follows. Indeed, any point on this segment is of the form (X
It is easy to see
++ is a convex cone, it follows that (X t We have thus shown that
U is star-shaped.
The next lemma gives a consequence of the concepts introduced in the previous definitions.
m be a continuous map and let H
m be the map defined by (3). Assume that the map F is (X; Y )-equilevel-monotone and
z-bounded. 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 ).
Proof. Let K be a compact subset of S n \Theta F (U \Theta ! m ). We will show that H \Gamma1 (K) is compact,
from which the result follows. The continuity of H implies that H \Gamma1 (K) is a closed set. Hence, it
remains to show that H \Gamma1 (K) is bounded. Indeed, suppose for contradiction that there exists a
sequence is compact and
we may assume without loss of generality that there exists F 1 2 F (U \Theta ! m )
such that
Clearly, we have F
such that the set
contains is an open set and every local homeomorphism maps open sets
onto open sets, it follows from Lemma 4 that H(N1 ), and hence F (N1 ), is an open set. Thus, by
(13), we conclude that for all k sufficiently large, say k
hence that F (X
monotone, we have (X
This inequality together with fact
that ( ~
imply
for every k - k 0 . Using the fact that fH(X k ; Y k ; z k )g ae K and K is bounded, we conclude that
g, is bounded. This fact together with the above inequality
implies that the sequences fX k g and fY k g are bounded. Since lim k!1 k(X
must have lim k!1 kz k is z-bounded, we conclude that lim k!1
1, thereby contradicting (13).
3 The Affine Case
Beginning in this section, we develop our main theory for the complementarity problem (1) and
the associated mapping H defined in (3). This section pertains to the case where F is affine; the
treatment of the general case of a nonlinear map F is given in the next section. Apart from the
fact that an affine map F considerably simplifies the analysis, through this case, we will be able to
obtain a technical result (Lemma 5) that will play an important role in the analysis of a nonlinear
F , which is the subject of the next section. The derivation of this technical lemma is definitely
the main reason for us to consider the case of an affine map separately.
We begin with a lemma that contains some elementary properties of affine maps.
Lemma 3 Assume that F is an affine map and let F
its linear part. Then the following statements hold:
(a) F is (X; Y )-equilevel-monotone if and only if
(b) F is z-injective if and only if
(c) F is z-injective if and only if F is z-bounded.
Proof. The proofs of (a) and (b) are straightforward. We next prove (c). Assume first that F is
z-injective. To show that F is z-bounded assume for contradiction that f(X k ; Y k ; z k )g is a sequence
in S n \Theta S n \Theta ! m such that f(X k are bounded and lim k!1 kz k
By passing to a subsequence if necessary, we may assume that lim k!1 z k =kz k
1. Hence, we obtain
z k
Since \Deltaz 6= 0, this contradicts the fact that F is z-injective. Hence, the "only if " part of (c) follows.
Assume now that F is not z-injective. Then there exists \Deltaz
and \Deltaz 6= 0. The sequence f(X defined by X
has the property that F 0 (X are
bounded and lim k!1 kz k showing that F is not z-bounded. The 'if ' part of c) follows.
The next lemma is an important step toward the main result in the affine case.
Lemma 4 Assume that F is an affine map which is (X; Y )-equilevel-
monotone and z-injective. Then the map H restricted to U \Theta ! m is a local homeomorphism.
Proof. Since U \Theta ! m is an open set, it is sufficient to show that the derivative map H 0 (X;
m is a isomorphism for every (X; Y; z) 2 U \Theta ! m . For this purpose,
fix any (X; Y; z) 2 U \Theta ! m . Since H 0 (X; Y; z) is linear and is a map between identical spaces, it is
enough to show that
Indeed, assume that the left-hand side of the above implication holds. By the definition H , we have
By (17) and Lemma 3(a), we have \DeltaX ffl \DeltaY - 0. In view of Lemma 1(d), this relation together
with (18) imply that This conclusion together with (17) and Lemma 3(b) imply
that We have thus shown that the implication (16) holds and the result follows.
We are now ready to present the main result of this section.
Theorem 1 Assume that F is an affine map which is (X; Y )-equilevel-
monotone and z-injective. Then, the following statements hold:
(a) H maps U \Theta ! m homeomorphically onto S n
(b) H(S n
Proof. The proof of the theorem follows from Proposition 2 as follows. Let M j S n
show
that these sets together with the map G j H j M satisfy the assumptions of Proposition 2. Indeed,
first observe that GjM 0
is a local homeomorphism due to Lemma 4. The assumption that
F is (X; Y )-equilevel-monotone and z-injective together with Lemma 3(c) and Lemma 4 imply
that the assumptions of Lemma 2 are satisfied. Hence, the conclusion of this lemma implies that
is proper with respect to E. Also the set H(M due to the fact that
To show that H(MnM 0 assume for contradiction that there
exists (X; Y; z) 2 MnM 0 such that H(X; Y; z) 2 N 0 . Then, by definition of H and the sets M , M 0
and N 0 , it follows that (XY +Y X)=2 2 S n
++ and (X; Y
. But this contradicts Lemma
1(c), and hence we must have Lemma 1, the set U , and hence
U star-shaped. Since the image of a star-shaped set under an affine map is star-shaped,
it follows that F (U \Theta ! m ), and hence N 0 , is star-shaped. Since every star-shaped set is simply-
connected, we conclude that N 0 is simply-connected. Hence, by Proposition 2 and the fact that
restricted to the pair (M 0
is a proper local homeomorphism and that H(cl U \Theta ! m
The theorem now follows from the two last conclusions, the fact that M 0 is path-connected, N 0 is
simply-connected, and Proposition 1.
We use the above result to prove the following very important technical lemma.
be elements of U such that
Proof. Let \DeltaX assume for contradiction that either \DeltaX 6= 0
or \DeltaY 6= 0. Without loss of generality, we may assume that \DeltaX 6= 0. We claim that there exists a
linear \DeltaY and is monotone, that is W ffl M(W
every W 2 S n . Indeed, if then the zero map satisfies the conditions of the claim. Assume
then that \DeltaY 6= 0. We consider two cases depending on whether \DeltaX ffl \DeltaY ? 0 or \DeltaX ffl
Consider first the case in which \DeltaX ffl \DeltaY ? 0. In this case, the subspace generated by \DeltaX and
the subspace L orthogonal to \DeltaY span S n . Clearly, there exists a unique linear
such that M (\DeltaX can be uniquely written
as
for every W 2 S n . Hence, M is a monotone map. Consider now the case in which \DeltaX ffl
Let L 1 denote the subspace orthogonal to both \DeltaX and \DeltaY . Clearly, there exists a unique map
\DeltaX; and M(V
Any W 2 S n can be uniquely written as
Then, we obtain
\DeltaX
for every W 2 S n . Hence, M is a monotone map. We have thus shown that the claim holds.
Consider now the defined by F (X; Y
. Using the fact that M is a monotone map and that M (\DeltaX
see that F satisfies the assumptions of Theorem 1 (with
By Theorem 1(a), it follows that the associated map H (with restricted to U is one-to-one.
Moreover, (19) and the relation F (X imply that H(X
last two conclusions together with the fact that (X imply that (X
4 The Nonlinear Case
In this section we establish results for nonlinear maps F which are similar to Theorem 2. We
also consider the case of a nonlinear map that arises from the mixed nonlinear complementarity
problems in symmetric matrices.
Theorem 2 Assume that F : S n
m is a continuous map which is (X; Y )-
equilevel-monotone, z-bounded (on S n
z-injective on S n
++ \Theta S n
Then, the
following statements hold for the mapping H given by (3):
(a) H is proper with respect to S n \Theta F (U \Theta ! m );
homeomorphically onto S n
(c) H(S n
Proof. The proof is close to the one given for Theorem 1. It consists of showing that the sets
together with the map G j H j M satisfy the assumptions of Proposition 2. But
instead of using Lemma 4 to show that GjM 0
is a local homeomorphism, we use Lemma
5 to prove that H j M 0
maps M 0 homeomorphically onto H(M 0 ). Since
is a continuous map
from an open subset of the vector space S n \Theta S n \Theta ! m into the same space, by the domain
invariance theorem it suffices to show that H j M 0
is one-to-one. For this purpose, assume that
z) for some ( -
Then, by the
definition of H , we have F ( -
z) and -
Y ~
X. Since F is
(X; Y )-equilevel-monotone, we conclude that ( -
Hence, by Lemma 5, we
have
Y ). This implies that F ( -
and by the z-injectiveness
of F on S n
++ \Theta S n
++ \Theta S n
We have thus
proved that H j M 0 maps M 0 homeomorphically onto H(M 0 ). To prove (b), it suffices to show that
. As in Theorem 1, we can verify that H(M 0
Using the assumption that F is (X; Y )-equilevel-monotone and z-bounded and the fact that H j M 0
is a homeomorphism onto H(M 0 ), it follows from Lemma 2 that H is proper with respect to
holds. Using the fact that U 0 is star-shaped and thus path-
connected, we easily see that N 0 is path-connected, and hence connected. Hence, by Proposition 2
and the fact that H(M 0
and H(cl U 0 \Theta ! m
Remark. The z-injectiveness of F is assumed only on S n
++ \Theta S n
(and not on S n
In the application to convex semidefinite programming to be discussed in the next section, we show
that under appropriate convexity assumptions, the mapping F defined by (11) satisfies the former
z-injectiveness property; thus Theorem 2 is applicable. Nevertheless, we do not know
if this special map F is z-injective on the larger set.
Theorem 2 establishes the claimed properties (P1)-(P4) of the map H stated in the Introduction.
Indeed, (P1) follows from conclusion (c); (P2) and (P3) follow from (b); and (P4) follows from
(a). In what follows, we give two important consequences of the above theorem, assuming that
first one, Corollary 1, has to do with the central path for the semidefinite
complementarity problem (1); the second one, Corollary 2, is a solution existence result for the
same problem.
Corollary 1 Assume that F : S n
m is a continuous map which is (X; Y )-
equilevel-monotone, z-bounded (on S n
z-injective on S n
++ \Theta S n
further that
that
++ for every t 2 (0; 1]. Then there exist (unique) paths
++ and z : (0;
Moreover, every accumulation point of (X(t); Y (t); z(t)) as t tends to 0 is a solution of the complementarity
problem (1).
Corollary 2 Assume that F : S n
m is a continuous map which is (X; Y )-
equilevel-monotone, z-bounded (on S n
z-injective on S n
++ \Theta S n
. If there
exists m such that F (X
, the system2 (XY
has a solution, which is unique when A 2 S n
++ .
Next, we introduce a strengthening of the equilevel-monotonicity concept and show that under
this strengthened monotonicity property, the image F (U \Theta ! m ) is a convex set in S n \Theta ! m .
Definition 5 The
)-everywhere-monotone if there
exist continuous functions OE
that c(R;
(R
where
Obviously, if F is (X; Y )-everywhere-monotone then F is (X; Y )-equilevel-monotone.
Theorem 3 Suppose that F : S n
m is a continuous map which is (X; Y )-
everywhere monotone, z-bounded (on S n
z-injective on S n
++ \Theta S n
in addition to statements (a), (b) and (c) of Theorem 2, it holds that the set F (U \Theta ! m ) is convex.
Proof. It suffices to establish the convexity of F (U \Theta ! m ). The proof is based on Proposition 3.
Consider the set M j U \Theta ! m and the map G j H j U \Theta! m . With M and G defined this way, the
convexity of F (U \Theta ! m ) follows from Proposition 3, provided that M and G satisfy the hypotheses of
the corollary. The rest of proof is devoted to the verification of these hypotheses. First observe that
G is a local homeomorphism due to Lemma 4. It remains to show that for any two triples ( ~
, the set G \Gamma1 (E) is compact, where E is the line segment connecting the
points H( ~
z). It is enough to show that any sequence f(X
has an accumulation point in G \Gamma1 (E). Indeed, let f(X
every k - 0 we have
Y ~
for some sequence f- k g ae [0; 1], where ~
z) and F k j F (X
By the (X; Y )-everywhere monotonicity of F and (21), it follows that
Hence,
Similarly, we can show that
Multiplying (22) by - k and (23) by and adding, we obtain
By (20) and (21) and the fact that f- k g is bounded, we see that the sequences fX k ffl Y k g and
are bounded. This observation, the fact that f- k g is bounded and the function c(\Delta; \Delta) is
continuous imply that the right hand side of (24), and hence its left hand side, is bounded. A
simple argument now shows that fX k g and fY k g are also bounded. This conclusion, the fact that
is bounded and the map F is z-bounded imply that fz k g is bounded. Hence, the sequence
is bounded and must have an accumulation point ( -
z). It remains to show that
closed since
H is continuous and both the domain of H and the set E are closed. The closeness of H
and the fact that f(X k imply that ( -
Using (20) and the
fact that ( ~
Y ) are in U , we easily see that ( -
++ . Morever, since
we see that ( -
. By Lemma 1(c), we conclude
that ( -
We have thus shown that ( -
Consider now the special case in which the mapping F : S n
has the
following structure:
F (X; Y; z) jB @
for some continuous mapping /
. The following result gives
conditions on / for the mapping F to satisfy all the assumptions of Theorem 3. This result will be
used in the next section for the map F given by (11).
Proposition 4 The following statements hold:
(a) F is (X; Y )-everywhere-monotone on S n
is a monotone mapping, that
is
\Theta

for every (X; z); (X
(b) F is z-injective on S n
++ \Theta S n
is z-injective on S n
(c) F is z-bounded on S n
is z-bounded on S n
Proof. We first prove (a). To prove that the mapping H is (X; Y )-everywhere-monotone, define
OE(X; Y; z) j (X; \Gammaz); and c j 0:
Using these
two equalities and the fact that / is a monotone mapping, we obtain

\Theta

which implies
(R
The proofs of (b) and (c) are straightforward and therefore we omit the details.
5 Convex Semidefinite Programming
In this section, we discuss the application of Theorem 3 to the mapping F given by (11). We wish
to specify some conditions on the functions ', G, and h in order for the resulting function F to
satisfy the assumptions of this theorem, and thus for the conclusions of the theorem to hold. The
following correspondence of variables should be used to cast the mapping F defined by (11) into
the form of the general mapping F considered in Section 4: (U; V )
Our first goal is to give a sufficient condition for the mapping F to be (X; Y )-monotone on
As in Shapiro (1997), we say that the mapping G positive semidefinite
convex (psd-convex) if
The following technical result is useful for the analysis of this section.
Lemma 6 Assume that G is an affine function. Then
the following statements hold:
(a) for every W 2 S n
, the function x
(b) the function x
(c) if the set X j fx nonempty and bounded then, for every
A 2 S n and fi 2 !, the set fx
Proof. (a) Using (25) and Lemma 1(b), we obtain
(b) Using (25), the fact that - max (\Delta) is a homogeneous convex function over the set of symmetric
matrices and the implication U
(c) Consider the function defined by v(x) j maxf- max (G(x)); kh(x)kg for x
Using (b), we see that v is a convex function. Moreover, the level set v \Gamma1 (\Gamma1; 0] is nonempty and
bounded since it coincides with the set X . By a well-known property of convex functions (Corollary
8.7.1 of Rockafellar 1970), it follows that every level set of v is bounded. Since fx
In the next three lemmas we study properties of the mapping /
defined by
\GammaG(x)
r x L(x; U;
where the map L is defined in (10).
Lemma 7 Suppose that continuously differentiable and convex, G
continuously differentiable and psd-convex and is an affine function. Then, the map
defined by (26) is monotone in the sense of Proposition 4(a).
Proof. We have to show that for any (U; x; j); (U
m+p , there holds
0: (27)
The assumption of the proposition implies that the functions L(\Delta; U; are convex
Hence, we have
Adding these two inequalities, using the definition of L and simplifying, we obtain (27).
Lemma 8 Suppose that continuous differentiable and convex, G
continuously differentiable and psd-convex and is an affine function such that the
gradient matrix rh(x) has full column rank. Then, / defined by (26) is (x; j)-injective
on S n
any one of the conditions below is satisfied:
(a) ' is strictly convex;
(b) for every U 2 S n
++ , the map x strictly convex;
(c) the feasible set X j fx bounded and each G ij (x) is an analytic
function.
Proof. Let U 2 S n
++ and (x; j); m+p be such that /(U; x;
We have to show that (x;
since rh(x) has full column rank, we have
Hence, it suffices to show that Note that by (28) and the definition of L, we have
The assumption of the lemma implies that the functions L(\Delta; U; are convex on ! m .
Hence, the two bracketed expressions in the right hand side of (29) are nonnegative and, since their
sum is zero, both of them must be equal to zero. In particular, we have
If (a) or (b) holds then the function L(\Delta; U; j) is strictly convex and, by (30), we must have
Consider case (c). Since h is affine, we have h(x
together with (30) and the definition of L imply
0:
Since '(\Delta) and U ffl G(\Delta) are convex functions on that the two bracketed expressions
in the above relation are nonnegative. Hence, we conclude that U ffl G(x
It is now easy to see that this relation together with the convexity of U ffl G(x)
and the fact that imply that U ffl using
the fact that G is psd-convex and
Thus, we have
we must have is an analytic function, this implies
that every y in the set L j f-x !g. Clearly, since
and h is affine, we also have that Hence, L is contained in the set
fy which is bounded in view of Lemma 6. This implies that
Lemma 9 Suppose that the function '
is continuously differentiable and psd-convex and is an affine function such that
the (constant) gradient matrix rh(x) has full column rank. Suppose also that the set X defined
in Lemma 8(c) is nonempty and bounded. Then the map / defined by (26) is (x; j)-bounded on
Proof. Assume that f(U k is a sequence in S n
m+p such that fU k g and f/(U k
are bounded. By the definition of /, it follows that fG(x k )g, fr x are
bounded. Hence, there exists ff ? 0 such that
or equivalently, fx k g ae fx ffg. By Lemma 6(c), we conclude that
is bounded. This fact together with the fact that fU k g and fr x are bounded
imply that frh(x k )j k g is bounded. Since rh(x) is constant and has full column rank, we conclude
that is bounded. We have thus shown that f(x k ; j k )g is bounded, and hence that / is (x; j)-
bounded on S n
Combining the above lemmas with Theorem 3, we obtain the following theorem which is the
main result of this section.
Theorem 4 Suppose that the function ' continuously differentiable and convex,
continuously differentiable and psd-convex, is an affine function such
that the (constant) gradient matrix rh(x) has full column rank and the feasible set X defined in
Lemma 8(c) is bounded. If any one of the following conditions holds:
(a) ' is strictly convex;
(b) for every U 2 S n
++ , the map x strictly convex;
(c) each G ij is an analytic function,
then the following statements hold for the maps F and H given by (11) and (3), respectively:
(i) H is proper with respect to S n \Theta F (U \Theta ! m+p );
homeomorphically onto S n
++ \Theta F (U \Theta ! m+p );
(iii) the set F (U \Theta ! m+p ) is convex;
(iv) H(S n
Proof. In view of Lemmas 7, 8 and 9, the map / given by (26) is monotone on S n
(x; j)-injective on S n
j)-bounded on S n
By Proposition 4, it follows that
the map F given by (11) is (U; V )-everywhere-monotone on S n
j)-injective on
++ \Theta S n
j)-bounded on S n
. The result now follows immediately
from Theorem 3.
By Theorem 4, if 0 2 F (U \Theta ! m+p ) then the system
has a solution for every A 2 S n
this solution is unique when A 2 S n
++ . Clearly, a solution
of this system when yields a feasible solution of (8) satisfying the stationary condition (9).
We henceforth give conditions on problem (8) for 0 to be an element of F (U \Theta ! m+p ). It turns out
that the existence of a Slater point for (8) is one of the conditions required by the next result.
Suppose that the function '
is continuously differentiable and psd-convex, is an affine function. Suppose also
that the feasible set X defined in Lemma 8(c) is bounded and there exists a vector ~ x 2 X such that
is given by (11).
Proof. consider the problem
subject to G(x) - \Gamma"I
By Lemma 6(c) and the assumption that X is bounded, it follows that the set of feasible solutions
of (32) is compact. Since its objective function is defined and continuous over the whole feasible
region, we conclude that (32) has an optimal solution x   . Observe that (32) satisfies the Slater
constraint qualification since G(~x) OE \Gamma"I , is psd-convex and h is affine. Hence, there
exist multipliers U   2 S n
Letting it follows from (33) and (34) that
or equivalently, F (U It remains to show that (U Clearly, we have
++ \Theta S n
++ due to the fact that G(x   ) OE 0. Moreover, using (34) we obtain
Clearly, this implies that (U
6 Maximal Monotonicity
In this section, we show that a mapping F satisfying the assumptions of Theorem 2 defines a family
of set-valued maps from S n
into itself which are maximal monotone in a restricted sense. For this
purpose, we introduce some definition and notation.
If M and N are two metric spaces, we shall denote a set-valued map A from M into subsets of
N by A
the graph of A is the set
is said to be a monotone set if for every (V; W
there holds
!W , with V and W being subsets
of M n , is called a monotone map if Gr(A) is a monotone set. The monotone map A
or its graph Gr(A), is said to be maximal monotone with respect to a subset T ' V \Theta W if there
exists no monotone set \Gamma ' T that properly contains T " Gr(A). If simply say
that the map A
!W is maximal monotone.
The following result establishes the maximal monotonicity with respect to the set U of certain
set-valued maps associated with a mapping F : S n
satisfying the assumptions
of Theorem 2.
Theorem 5 Suppose that F : S n
m is a continuous map which is (X; Y )-
equilevel-monotone, z-bounded (on S n
z-injective on S n
++ \Theta S n
defined by
is monotone, and maximal monotone with respect to U .
Proof. Using the fact that F is (X; Y )-equilevel-monotone, we easily see that AB is monotone.
To show that AB is maximal monotone with respect to U , let \Gamma ' U be a monotone set containing
We have to show that
Theorem 2(b) implies the existence of a triple
m such that
are in \Gamma, we
conclude that
In view of Lemma 5, the last relation together with the first equality of (35) and the fact that both
are in U imply that (X
have thus shown that and the result follows.
Observe that the set F given by (12) is equal to the set Gr(AB ) with hence F is a
maximal monotone set with respect to set U . We end this section by giving the following close
version of Theorem 5 for maps F defined over the whole space S n \Theta S n \Theta ! m .
Theorem 6 Suppose that F m is a continuous map which is (X; Y )-
monotone, z-bounded and z-injective. Then, for every B 2 F (S n \Theta S n \Theta ! m ), the set-valued map
AB defined in Theorem 5 is maximal monotone.
Proof. This follows immediately from Theorem 8 in Monteiro and Pang (1996) by using the fact
that S n is isomorphic to ! n(n+1)=2 .
7 An Alternative Map
Given a continuous map
consider in this section the map
defined by
and present conditions on the map F which guarantee the existence of a (unique) solution of the
system
-I
for every B 2 F (M n
++ \Theta S n
first establish two useful lemmas.
Lemma 11 Suppose that
m is a continuous map which is (X; Y )-
equilevel-monotone and z-injective on M n
++ \Theta S n
Then, the map H defined by (36) maps
++ \Theta S n
homeomorphically onto H(M n
++ \Theta S n
Proof. Since M n
++ \Theta S n
is an open subset of M n \Theta S n \Theta ! m , by the domain invariance
theorem it suffices to show that that H j M n
assume that (X; Y; z)
are two triples in M n
++ \Theta S n
m such that H(X; Y;
have
F (X; Y;
Y \GammaY . Using (38) and the fact that F is (X; Y )-equilevel-monotone, we
conclude that \DeltaX ffl \DeltaY - 0. Moreover, it is easy to see that (37) implies that (\DeltaX ) -
or equivalently \DeltaX = \GammaX \DeltaY -
Y \Gamma1 . Hence, we obtain
where the penultimate equality follows from the fact that tr
the matrix \DeltaY (X This observation, the fact that
imply that \DeltaY (X
Hence, we have We thus shown that
Y . This conclusion
together with (38) and the assumption that F is z-injective on M n
++ \Theta S n
imply that
z.
Lemma 12 Suppose that
m is a continuous map which is (X; Y )-
equilevel-monotone, z-bounded on S n
and z-injective on M n
++ \Theta S n
. Then the
defined by (36) satisfies the following two properties:
(a) H is proper with respect to (!++ \Delta I) \Theta F (M n
++ \Theta S n
(b) H restricted to S n
proper with respect to (!+ \Delta I) \Theta F (M n
++ \Theta S n
Proof. The proof of part (a) is very close to the one given for Lemma 2. Let K be a compact
subset of (!++ \Delta I) \Theta F (M n
++ \Theta S n
show that H \Gamma1 (K) is compact, from which
the result follows. The continuity of H implies that H \Gamma1 (K) is a closed set. Hence, it remains
to show that H \Gamma1 (K) is bounded. Indeed, suppose for contradiction that there exists a sequence
each Y k is in S n
and the
product is a positive multiple of the identity matrix, it follows that both sequences fX k g
and fY k g must belong to S n
++ . Since K is compact and fH(X we may assume
without loss of generality that there exists F 1 2 F (M n
++ \Theta S n
Clearly, we have F
++ \Theta S n
such that the set
++ \Theta S n
contains is an open set of M n
++ \Theta S n
m and every homeomorphism
maps open sets onto open sets, it follows from Lemma 11 that H(N1 ), and hence F (N1 ), is
an open set. Thus, by (39), we conclude that for all k sufficiently large, say k
Since F is (X; Y )-equilevel-monotone, we have (X
This
inequality together with fact that ( ~
imply
for every k - k 0 . Using the fact that fH(X k ; Y k ; z k )g ae K and K is bounded, we conclude that
g, and hence fX k ffl Y k g, is bounded. This fact together with the above inequality implies
that the sequences fX k g and fY k g are bounded. Since lim k!1 k(X must have
which implies that lim k!1 due to the fact that F is
z-bounded. But this last conclusion contradicts (39). This establishes part (a).
The proof of part (b) requires only a slight modification of a couple steps in the above proof. Indeed
let K be a compact subset of (!+ \Delta I) \Theta F (M n
++ \Theta S n
let the sequence f(X
be such that (X
We follow the above
argument. Although we can not deduce that (X
++ \Theta S n
++ , but utilizing the fact that
, we can still establish the boundedness of the sequence f(X )g. The
details are not repeated. Thus (b) holds.
Based on the above two lemmas, we can establish two additional properties of the mapping H .
Theorem 7 Suppose that
m is a continuous map which is (X; Y )-
equilevel-monotone, z-bounded on S n
and z-injective on M n
++ \Theta S n
addition to the conclusions of Lemmas 11 and 12, we have:
(a) H(S n
++ \Theta S n
++ \Theta S n
(b) H(S n
++ \Theta S n
Proof. Note that if we can show
++ \Theta S n
++ \Theta S n
then part (a) follows. In turn the proof of the displayed inclusion consists of showing that the sets
++ \Theta S n
++ \Theta S n
together with the map G j H satisfy the assumptions of Proposition 2.
Clearly, is a local homeomorphism by Lemma 11. Also H(I ; I ;
claim that H(MnM 0 assume that (X; Y; z) 2 M is such that H(X; Y; z) 2 N 0 .
, we conclude that both X and Y are in S n
++ .
Hence, (X; Y; z) 2 M 0 and the claim follows. By Lemma 12, we know that proper with
respect to E. Using Lemma 1(e), it is easy to see that the set N 0 is path-connected, and thus
connected. Hence, it follows from Proposition 2 that H(M 0 ) ' N 0 . This is precisely the inclusion
(40).
To prove (b), it suffices to show that (0; B) 2 H(S n
++ \Theta S n
For each scalar - ? 0, there exists (X
++ \Theta S n
must be symmetric
positive definite. By part (b) of Lemma 12, we conclude that lim sup -!0 k(X
Consequently, a simple limit argument completes the proof.
As the final result of this paper, we present a corollary of the above theorem which summarizes
the essential properties of the mapping ~
H defined in (6). This corollary is the analog of Theorem
2 for the alternative interior-point map ~
H .
Corollary 3 Suppose that ~
m is a continuous map which is (X; Y )-
equilevel-monotone, z-bounded on S n
and z-injective on S n
++ \Theta S n
Then, the
defined by
~
~
satisfies the following statements:
(a) ~
H is proper with respect to (!+ \Delta I) \Theta ~
F (S n
++ \Theta S n
(b) ~
H maps S n
++ \Theta S n
homeomorphically onto ~
++ \Theta S n
(c) ~
F (S n
++ \Theta S n
Proof. Consider the map
defined by F (X; Y;
. Using the assumptions about the map ~
F , it is
easy to see that F is (X; Y )-equilevel-monotone, z-bounded on S n
and z-injective on
++ \Theta S n
Hence, it follows that the associated
defined by (36) satisfies the conclusions of Lemma 11, Lemma 12 and Theorem 7, which easily
imply the desired conclusions (a), (b), and (c).
Corollary 4 Suppose that ~
m is a continuous map which is (X; Y )-
equilevel-monotone, z-bounded on S n
and z-injective on S n
++ \Theta S n
~
F (S n
++ \Theta S n
Proof. Let
F (S n
++ \Theta S n
Corollary 3(c), we know that
H is the map defined in Corollary 3. Hence, there exists (X; Y; z) 2 S n
such that I and ~
the relation obviously implies that
we conclude that B 2 ~

Acknowledgement

During this research, Dr. Monteiro was supported by the National Science Foundation under grants
INT-9600343 and CCR-970048 and the Office of Naval Research under grant N00014-94-1-0234; Dr.
Pang was supported by the National Science Foundation under grants CCR-9213739 and by the
Office of Naval Research under grant N00014-93-1-0228.



--R

Interior point methods in semidefinite programming with application to combinatorial optimization.

Complementarity and nondegeneracy in semidefinite programming.
A Primer of Nonlinear Analysis
Interior point trajectories in semidefinite programming


A predictor-corrector interior-point methods for the semidefinite linear complementarity problem using the Alizadeh-Haeberly-Overton search direction




Properties of an interior-point mapping for mixed complementarity problems
Interior Point Methods in Convex Programming: Theory and Application


Iterative Solution of Nonlinear Equations in Several Variables
A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming
Strong duality for semidefinite programming
Convex Analysis
First and second order analysis of nonlinear semidefinite programs.
Monotone semidefinite complementarity problems
Centers of monotone generalized complementarity problems
Existence of search directions in interior-point algorithms for the SDP and the monotone SDLCP
programming.
On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming
--TR

--CTR
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
interior point methods;maximal monotonicity;problems;mixed nonlinear complementarity problems;generalized complementarity;nonlinear semidefinite programming;weighted central path;monotone mappings;continuous trajectories