General Interior-Point Maps and Existence of Weighted Paths for Nonlinear Semidefinite Complementarity Problems.
Extending the previous work of Monteiro and Pang (1998), this paper studies properties of fundamental maps that can be used to describe the central path of the monotone nonlinear com-plementarity problems over the cone of symmetric positive semidefinite matrices. Instead of focusing our attention on a specific map as was done in the approach of Monteiro and Pang (1998), this paper considers a general form of a fundamental map and introduces conditions on the map that allow us to extend the main results of Monteiro and Pang (1998) to this general map. Each fundamental map leads to a family of "weighted" continuous trajectories which include the central trajectory as a special case. Hence, for complementarity problems over the cone of symmetric positive semidefinite matrices, the notion of weighted central path depends on the fundamental map used to represent the central path.
Introduction
section1
In a series of recent papers (see Kojima, Shida and Shindoh 1997, 1998, 1999, Kojima, Shindoh
and Hara 1997, Shida and Shindoh 1996, Shida, Shindoh and Kojima 1997, 1998), 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 for example Alizadeh 1995,
Alizadeh, Haeberly and Overton 1997, 1998 Luo, Sturm and Zhang 1996, 1998, Monteiro 1997, 1998,
Monteiro and Tsuchiya 1999, Monteiro and Zhang 1998, Nesterov and Nemirovskii 1994, Nesterov
This work has been partly supported by the National Science Foundation under grants CCR-9700448, CCR-9902010
and INT-9600343.
y School of Industrial and Systems Engineering, Georgia Tech, Atlanta, GA 30332. (monteiro@isye.gatech.edu)
and Todd 1997, 1998, Potra and Sheng 1998, Ramana, Tun-cel and Wolkowicz 1997, Shapiro 1997,
Vandenberghe and Boyd 1996, Zhang 1998).
denote the m-dimensional real Euclidean space, S n denote the space of n \Theta n real
symmetric matrices, S n
++ denote the subsets of S n consisting of the positive semidefinite
and positive definite matrices, respectively, and C(-) j
We denote the closure of a subset E of a metric space by cl E. Given a continuous map
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 such that
eq:psd cp
F (X; Y;
It is known (see the cited references) that there are several equivalent equations to represent the
complementarity condition (X; Y problem. Associated with each of these equivalent
equations, we can define an interior-point map that not only provides the foundation for developing
path-following interior point methods for solving problem (1) but also serves to generalize the notion
of weighted central path from linear programming to the context of the complementarity problem (1).
In the work of Monteiro and Pang (1998), they focus on the equivalent complementarity equation
(XY +Y several properties of the associated interior-point map. The main goal of
this paper is to generalize the work of Monteiro and Pang (1998) to other equivalent complementarity
equations having the general form \Phi(X; Y is a continuous map such that:
++ \Theta S n
In terms of
\Phi, problem (1) becomes equivalent to finding a triple (X; Y; z) 2 D \Theta ! m such that H(X; Y;
m is the fundamental interior-point map (associated with \Phi)
defined by
F (X; Y; z)
For the map \Phi(X; Y
and the open convex cone
++ , Monteiro and Pang (1998) establish under some monotonicity conditions on the map F
that the system
sys.H H(X; Y;
A
have the following properties:
(P1) it has a solution for every (A; B) 2 cl V \Theta F++ , where F++ j F (S n
++ \Theta S n
(P2) the solution, denoted (X(A; B); Y (A; B); z(A; B)), is unique when (A;
if a sequence converges to a limit (A1 ; B1 then the sequence
converges to (X(A1 ; B1
if a sequence converges to a limit (A1 cl V \Theta F++ , then the
sequence ))g is bounded, and that any of its accumulation
point
Note that when 0 2 F++ , (P1) implies the existence of a solution of (1), and (P2) implies the
well-definedness of the weighted central paths passing through points in V , that is paths consisting
of the unique solutions of system (3) with is a fixed
point in V .
Under appropriate conditions on the map \Phi and the open convex cone V , we show in this paper
that the above properties also hold with respect to the general interior-point map (2). We also
illustrate how our general framework applies to the following specific central-path maps:
where LX is the lower Cholesky factor of X , U Y is the upper Cholesky factor of Y and W is the unique
symmetric positive definite matrix such that
be easily verified to be a special case of our general framework using the results of Monteiro and
Pang 1998.) Observe that the third and fourth maps are only defined for points (X; Y ) in the set
++ \Theta S n
++ ), and hence they illustrate the need for considering maps \Phi whose domain are not
the whole set S n
. The approach of this paper is based on the theory of local homeomorphic
maps. One of the preliminary steps of our analysis is to establish that H restricted to the set U \Theta ! m
is a local homeomorphism, where U (V). For this property to hold for the above cited maps, it
is necessary to choose the set V to be an open convex cone smaller than S n
++ , which is the cone used
in connection with the map \Phi(X; Y in the analysis of Monteiro and Pang (1998).
In fact, the sets V associated with the four maps above are appropriate conical neighborhoods of the
line contained in S n
++ .
Sturm and Zhang (1996) define a notion of weighted center for semidefinite programming based
on the central path map \Phi(X; Y denotes the eigenvalues of XY arranged in
nondecreasing order. According to their definition, given a vector w
++ such that w
a point (X; Y; z) 2 S n
++ \Theta S n
is an w-weighted center if F (X; Y;
For linear maps F associated with semidefinite programming problems, they show the existence of
an w-center for any such w. However, their w-center is not unique and hence does not lead to the
notion of weighted central paths as our approach does.
Finally, we observe that interior-point algorithms for solving the complementarity problem (1)
which makes use of the fundamental interior-point map (2) have been proposed in Wang et al. (1996)
and Monteiro and Pang (1999).
This paper is organized as follows. Section 2 contains an exposition of the main results of this
paper whose proofs are given in the subsequent sections. Section 2 is divided into three subsections.
Subsection 2.1 summarizes some important definitions and facts from the theory of local homeomorphic
maps. Subsection 2.2 introduces the key conditions on the map F and the pair (\Phi; V), and gives
a few examples of pairs (\Phi; V) which satisfy these conditions. In Subsection 2.3, we state the main
result of this paper and some of its consequences, including its specialization to the context of the
convex nonlinear semidefinite programming problem. In Section 3, we provide the proof of the main
result. Finally, in Section 4, we develop some technical results which allow us to verify that the pairs
introduced in Section 2 satisfy our basic assumptions.
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. The set of all n \Theta n matrices with real entries is denoted by M n . Let M n
and M n
++ denote the set of matrices
? denote the subspace of M n consisting of the skew-symmetric matrices. For A 2 M n , let
A ii denote the trace of A. For
inner product in M n . For any matrix A 2 M n , let
- is an eigenvalue of A T Ag
. For a matrix A 2 M n with all real eigenvalues, we denote its smallest and
largest eigenvalues by - min (A) and - max (A), respectively. Finally, define the sets
Main Assumptions and Results
section2
In this section, we state the assumptions imposed on the map F and the pair (\Phi; V) and give a
few examples of pairs (\Phi; V) satisfying the required conditions. We also state the main result and
its consequences, including its specialization to the context of the convex nonlinear semidefinite programming
problem. This section is divided into three 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 and the Appendix 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 map F and the pair (\Phi; V), and
gives a few examples of pairs (\Phi; V) which satisfy these conditions. The third subsection states the
main result and its corollaries.
2.1 Local homeomorphic maps
subsection2.1
This subsection summarizes some important definitions and facts from the theory of 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. The set
simply denoted by G \Gamma1 (v). Given G 2 C(M;N ),
that G(D) ' E, the restricted map ~
defined by ~
denoted by
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 of M for which both O 1 and O 2 are non-empty and open.
In the rest of this subsection, we will assume that M and N are two metric spaces and that
1 The map G 2 C(M;N) is said to be proper with respect to the set E ' N if G
M is compact for every compact set K ' E. If G is proper with respect to N , we will simply say
that G is proper.
Our analysis rely upon the following two well-known results. The first one is a classical topological
result whose proof can be found in Chapter 3 of Ambrosetti and Prodi (1993) and in the Appendix
of Monteiro and Pang (1996).
Proposition 1 main Assume that G : M ! N is a local homeomorphism. If N is connected
G is proper if and only if the number of elements of G \Gamma1 (v) is finite and constant for v 2 N .
The next result is derived in Section 2 of Monteiro and Pang (1996) and its proof is an immediate
consequence of classical topological results.
Proposition 2 cor1 Let M 0 ' M and N 0 ' N be given sets satisfying the following conditions:
is a local homeomorphism and ; . Assume that G is proper with respect to
some set E such that N 0 ' E ' N . Then G restricted to the local
homeomorphism. If, in addition, N 0 is connected, then G(M 0 cl N 0 .
2.2 Fundamental assumptions and examples of central-path maps
subsection2.2
In this subsection, we state the conditions that will be imposed on the map F and the pair (\Phi; V)
during our analysis of the properties of the fundamental map (2). We also give a few examples of
pairs (\Phi; V) which satisfy the required conditions.
We start by giving a few definitions.
defined on a subset dom (J) of M n \Theta M n \Theta ! m
is said to be (X; Y )-equilevel-monotone on a subset H ' dom (J) if for any (X; Y; z) 2 H and
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
/(w; z) is a function defined on a subset of W \Theta Z with values in N .
z-boundedness The function /(w; z) is said to be z-bounded on a subset H '
dom (/) if for every sequence f(w k ; z k )g ' H such that fw k g and f/(w k ; z k )g are bounded, the
sequence fz k g is also bounded. When dom (/), we will simply say that / is z-bounded.
Definition 4 z-injective The function /(w; z) is said to be z-injective on a subset H '
dom (/) if the following implication holds: (w; z)
dom (/), we will simply say that / is z-injective.
We now state the main assumptions that will be made on the map F and the pair (\Phi; V).
Assumption 1 ass1 The
monotone, z-injective on S n
++ \Theta S n
Assumption 2 ass2 We impose the following conditions on the pair (\Phi; V):
is a continuous map such that C(0) [ (S n
++ \Theta S n
is an open
connected set such that
(b) for any (X; Y ) 2 D and - 0, we have
is a continuous strictly increasing function such that
(c) if the sequence f(X k ; Y k )g ' D is such that f\Phi(X k ; Y k )g is bounded, then fX k ffl Y k g is
(d) the set U j \Phi \Gamma1 (V) is contained in S n
++ \Theta S n
is a closed set;
(e) \Phi is differentiable on S n
++ \Theta S n
++ and for every (X; Y the following implication holds:
We now make a few remarks regarding the above assumptions. First, condition (a) is stated so
as to cover some relevant examples of maps \Phi which are defined only in the set C(0) [ (S n
++ \Theta S n
(see Examples 4 and 5 below). Second, Assumption 2(c) implies that the map ' is onto, and hence
that its inverse is defined everywhere in !+ . Third, conditions (a), (b) and (d) of Assumption 2
imply that U is a nonempty open set. Fourth, condition (b) implies that the curve consisting of the
solutions of the systems
eee
as - ? 0 varies, is a parametrization of the central path associated with the complementarity problem
(1), that is the set of solutions of the systems
condition (e) is probably the most crucial one. Under Assumption 1, this condition is equivalent to
the well-definedness of the Newton direction with respect to system (4) for any point (X; Y; z) in U .
We next give some examples of pairs (\Phi; V) which satisfy Assumption 2.
Example 1: Let D j S n
be the map defined by \Phi(X; Y
++ .
Example 2: Let D j S n
be the map defined by \Phi(X; Y
Example 3: Let D j S n
be the map defined by \Phi(X; Y
Example 4: Let D
++ \Theta S n
be the map defined by
++ \Theta S n
where LX is the lower Cholesky factor of X , that is LX is the unique lower triangular matrix
with positive diagonal elements satisfying
Example 5: Let D
++ \Theta S n
be the map defined by
++ \Theta S n
where LX is the lower Cholesky factor of X and U Y is the upper Cholesky factor of Y , that is U Y is
the unique upper triangular matrix with positive diagonal elements satisfying U Y U T
Example
++ \Theta S n
be the map defined by
++ \Theta S n
is the unique symmetric positive definite matrix satisfying
The map of Example 1 was extensively studied in Monteiro and Pang (1998), and is a special
case of the general framework studied in this paper. The verification that these examples satisfy
Assumption 2 will be given in Section 4. The next result shows that each map above generates a
whole family of maps that satisfy Assumption 2.
Proposition 3 scale-family Let (\Phi; V) be a pair satisfying Assumption 2. Then:
i) for every ff ? 0, the pair (ff\Phi; ffV) satisfies Assumption 2;
ii) for every nonsingular matrix P , the pair (\Phi P ; V) satisfies Assumption 2, where \Phi
S n is the map defined as \Phi P (X; Y
Proof. The proof is just a simple verification.
In all six examples above, the domain D P of the map \Phi P remains invariant, that is D
every P . For a pair (V ; \Phi) and a nonsingular matrix P , let U
P (V). In general, U P may differ
from U , but for the maps of Examples 2 and 4, we have U every nonsingular matrix P .
Moreover, the maps \Phi P corresponding to Examples 1-6 become
e
e
Y
e
Y
respectively, where L e
X is the lower Cholesky factor of e
Y is the upper Cholesky
factor of e
In the last equation, we used the fact that f
is the unique
symmetric matrix such that f
Y .
2.3 The main result and its consequences
subsection2.3
In this subsection we state the main result of this paper. We also state some of its consequences,
including its specialization to the context of the convex nonlinear semidefinite programming problem.
The main result extends Theorem 2 of Monteiro and Pang (1998) to fundamental maps (2) associated
with pairs (\Phi; V) satisfying Assumption 2. It essentially states that the fundamental map (2) has
some nice homeomorphic properties.
Theorem 1 main2 Assume that F : S n
Assumption 1 and the
Assumption 2. Then the following statements hold for the map H:
(a) H is proper with respect to cl V \Theta F++ ;
(b) H maps U \Theta ! m homeomorphically onto V \Theta F++ , where U
cl V \Theta F++ .
Theorem 1 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 0 2 F++ .
The 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 co:path existence Suppose that F : S n
Assumption
1 and the pair (\Phi; V) satisfies Assumption 2. Assume that (0; cl V \Theta F++ and let
be paths such that P
every t 2 (0; 1]. Then there exist (unique) paths
++ such that
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 co:solution existence Assume that F : S n
Assumption 1 and the pair (\Phi; V) satisfies Assumption 2. If there exists (X
that F (X cl V, the system
cl U
has a solution, which is unique when A 2 V.
We now discuss the specialization of Theorem 1 to the context of the convex nonlinear semidefinite
program. The complementarity problem (1) arises as the set of first-order necessary optimality
conditions for the following nonlinear semidefinite program (see for example Shapiro 1997):
eq:psd nlp
minimize '(x)
subject to G(x) 2 \GammaS n
are given smooth maps. 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
Letting
r x L(x; U;
we see that the first-order necessary optimality conditions for problem (5) are equivalent to the
complementarity problem (1) with
The is said to be positive semidefinite convex (psd-convex) if
The following result follows as an immediate consequence of Theorem 1 and the results of Section 5
of Monteiro and Pang (1996b).
Theorem 2 properties of F Suppose that (\Phi; V) is a pair satisfying Assumption 1, the function
continuously differentiable and convex, G continuously differentiable
and is an affine function such that the (constant) gradient matrix rh(x)
has full column rank and the feasible set X j fx 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 (8) and (2), respectively:
(i) H is proper with respect to cl V \Theta F (S n
++ \Theta S n
homeomorphically onto V \Theta F (S n
++ \Theta S n
cl V \Theta F (S n
++ \Theta S n
(iv) the set F (S n
++ \Theta S n
Proof. The assumptions of the theorem together with Proposition 4, Lemmas 7, 8 and 9 of Monteiro
and Pang (1996b) imply that the map F given by (8) is (U; V )-equilevel-monotone on S n
(x; j)-injective on S n
++ \Theta S n
j)-bounded on S n
Hence, the conclusions
(i), (ii) and (iii) of the theorem follows directly from Theorem 1. It was shown in Theorem 4(iii) of
Monteiro and Pang (1996b) that the set F ( e
U \Theta ! m+p ) is convex, where e
++ \Theta S n
g. Since C(-) ' e
U
++ \Theta S n
++ for all - ? 0, it follows from Lemma 1(b) that
U \Theta ! m+p
++ \Theta S n
holds.
3 Proof of the Main Results
section3
The goal of this section is to give the proof of Theorem 1. In the process of doing this, we will
first establish Theorem 1 for the case in which the map F is affine. Apart from the fact that an affine
considerably simplifies the analysis, we obtain through this case an important technical result
(Lemma 5) which plays an important role in establishing Theorem 1 for the case of a nonlinear map
F satisfying Assumption 1.
We first establish two important technical lemmas that hold for nonlinear maps F satisfying
Assumption 1.
m be a map satisfying Assumption 1.
Then, the following statements hold:
(a) F restricted to S n
++ \Theta S n
is an open map; in particular, F++ is an open set;
Proof. We first establish (a). Let ~
m be defined by ~
F (X; Y;
. Using the fact that F satisfies Assumption 1, it
is easy to see that ~
F is (X; Y )-equilevel-monotone, z-injective on M n
++ \Theta S n
Then, it follows from Lemma 11 of Monteiro and Pang (1998) that the map ~
defined by
~
~
F (X; Y; z)
maps M n
++ \Theta S n
homeomorphically onto ~
++ \Theta S n
By the domain invariance
theorem, this implies that ~
H , and hence ~
F , restricted to M n
++ \Theta S n
is an open map. This
conclusion together with a simple argument shows that F restricted to S n
++ \Theta S n
is also an
open map.
We now show (b). Clearly, F (C(-) To prove the other inclusion,
let B be an arbitrary element of F++ . Since by Corollary 3 of Monteiro and Pang (1998), the system
F (X; Y; has a (unique) solution in S n
++ \Theta S n
conclude that
A consequence of Lemma 1(b) is as follows. Assumption 2(a) implies the existence of
such that - 0 I 2 V . This together with (b) and (d) of Assumption 2 imply that C('
++ \Theta S n
++ . Hence, in view of Lemma 1(b), it follows that F (U \Theta ! m
properness
m be a map satisfying Assumption 1,
(\Phi; V) be a pair satisfying Assumption 2, and m be the map defined in
(2). Then, H is proper with respect to cl V \Theta F++ .
Proof. Let K be a compact subset of cl V \Theta F++ . We will show that H \Gamma1 (K) is compact from which
the result follows. We first show that H \Gamma1 (K) is closed. Since K is closed and H is continuous,
closed with respect to dom Hence, the closeness of H \Gamma1 (K) follows
if we show that H \Gamma1 (K) is contained in a closed subset of dom (H). Indeed, the definition of
H implies that H \Gamma1 (K) is contained in \Phi \Gamma1 (cl V) \Theta ! m , which by Assumption 2(d), is a closed
set. We next 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++ such
that
Clearly, we have F
++ \Theta S n
++
and Y 1 - 0, there exists j ? 0 such that the set
++ \Theta S n
contains clearly have that N1 is open, and using Lemma 1(a), it follows that
is an open set. Thus, by (10) and the fact that F 1 2 F (N1 ), we conclude that for all k
sufficiently large, say k
This inequality together with fact that ( e
imply
for every k - k 0 . Using the fact that fH(X k ; Y k ; z k )g ' K and K is bounded, we conclude that
Using Assumption 2(c) we have that 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
must have lim k!1 kz k 1. From the fact that F is z-bounded,
we conclude that lim k!1 contradicting (10).
We now turn our attention to the case of an affine map F and derive a version of Theorem 1 in
this context (see Theorem 3 below). We begin with a result that contains some elementary properties
of affine maps.
Lemma 3 easy Assume that G is an affine map and let G
its linear part. Then the following statements hold:
(a) G is (X; Y )-equilevel-monotone if and only if
iii1
(b) G is z-injective if and only if
(c) G is z-injective if and only if G is z-bounded.
Proof. See Lemma 3 in Monteiro and Pang (1998).
The next lemma is an important step towards establishing the main result for the case in which
F is affine.
m be an affine map which is (X; Y )-
equilevel-monotone and z-injective, and let (\Phi; V) be a pair satisfying Assumption 2. Then the map
H defined in (2) 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;
is an 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 (14) and Lemma 3(a), we have \DeltaX ffl \DeltaY - 0. This together with (15) and Assumption 2(e)
imply that Hence, by (14) and Lemma 3(b) we conclude that \Deltaz = 0. We have
thus shown that the implication (13) holds.
We are now ready to establish a version of the main result for the affine case.
Theorem 3 main1 Assume that F is an affine map which is
(X; Y )-equilevel-monotone and z-injective, and (\Phi; V) is a pair satisfying Assumption 2. Then, the
following statements hold:
(a) H maps U \Theta ! m homeomorphically onto V \Theta F++ ;
cl V \Theta F++ .
Proof. Let cl V \Theta F++ .
We will show first that these sets and the map G j H satisfy the assumptions of Proposition 2.
Indeed, first observe that H j M 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) imply that F is z-bounded.
Hence, it follows from Lemma 2 that H is proper with respect to E. By the definition of M 0 ,
To show that H note that by Assumption 2(a),
there exists Letting we have by Assumption 2(b)
that \Phi(- 0 I
By Assumption 2(a) and the fact that a continuous map carries connected sets onto connected
sets, we conclude that N 0 j V \Theta F++ is a connected set. By Proposition 2, we conclude that H
restricted to the pair (H local homeomorphism, H(M 0
cl N 0 . Clearly, the last inclusion implies the second inclusion in b). The
first inclusion follows from the fact that \Phi \Gamma1 (cl V) being closed by Assumption 2(d) implies that
cl U ' \Phi \Gamma1 (cl V) ' D.
We now show (a). We have already shown that H maps M 0 onto N 0 and that ~
is a proper local homeomorphism. It remains to show that ~
H is one-to-one. Since N 0 is connected,
by Proposition 1 it remains to show that for some (A; B) 2 N , the inverse image
~
has at most one element. Indeed, let I and take B 2 F++ arbitrarily. Assume
that ( -
is such that ~
by the
definition of H , we have F ( -
I , which by Assumption 2(b) implies that
by Corollary 3 of Monteiro and Pang (1998), the system F (X; Y;
has a unique solution in S n
++ \Theta S n
++ \Theta S n
we conclude that ( -
is the only solution of ~
We use the above result to prove the following very important technical lemma.
Lemma 5 technical Let (\Phi; V) be a pair satisfying Assumption 2. Let (X
be elements of U such that
Proof. Assume for contradiction that (X It has been shown in the proof of Lemma 5
of Monteiro and Pang (1998) that there exists an affine which is (X; Y )-
equilevel-monotone and satisfies F (X Assumption 1 with
variable z is present). By Theorem 3(a), it follows that the associated map H (with
restricted to U is one-to-one. Moreover, (16) and the relation F (X imply that
The last two conclusions together with the fact that (X
then imply that (X
We are now ready to give the proof of Theorem 1.
Proof of Theorem 1: The proof is close to the one given for Theorem 3. It consists of showing
that the sets M j D cl V \Theta F++ ,
together with the map G j H , satisfy the assumptions of Proposition 2. But instead of using
Lemma 4 to show that H j M 0
is a local homeomorphism, we use Lemma 5 to prove that H j M 0
maps
homeomorphically onto H(M 0
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
is one-to-one. For this purpose, assume that H( -
U
Then, by the definition of H , we have F ( -
z) and
Y ). Since F is (X; Y )-equilevel-monotone, we conclude that ( -
Hence, by Lemma 5, we have ( -
Y ). This implies that F ( -
z), and by the
z-injectiveness of F it follows that - z = ~ z. We have thus proved that H j M 0
maps M 0 homeomorphically
is clearly a local homeomorphism and F is (X; Y )-equilevel-monotone and
z-bounded by assumption, it follows from Lemma 2 that a) holds. The proofs of b) and c) use the
same arguments as in the proof of Theorem 3.
4 Verification of Assumption 2 for Several Central-Path Maps
section4
In this section we verify that the maps of Examples 1 to 6 satisfy Assumption 2.
Verification for Example 1: Let D j S n
be the map defined by \Phi(X; Y
++ . Conditions (a), (b) and (c) of Assumption 2 are straightforward, and
clearly we have that U is contained in S n
++ \Theta S n
++ . Since \Phi is continuous and its domain is closed, the
set \Phi \Gamma1 (cl V) is closed, and hence Assumption 2(d) holds. Assumption 2(e) follows from Theorem
3.1(iii) in Shida, Shindoh and Kojima (1998).
Verification for Example 2: Let D j S n
be the map defined by \Phi(X; Y
Conditions (a), (b) and (c) of
Assumption 2 are straightforward. As in Example 1, we easily see that \Phi \Gamma1 (cl V) is closed. Hence,
Assumption 2(d) holds. Finally, it follows from the proof of Lemma 2.3 of Monteiro and Tsuchiya
that the implication of Assumption 2(e) holds.
Verification for Example 3: Let D j S n
be the map defined by \Phi(X; Y
Conditions
(a), (b) and (c) of Assumption 2 are straightforward. As in Example 1, we easily see that \Phi \Gamma1 (cl V)
is closed. Hence, Assumption 2(d) holds. Finally, Assumption 2(e) follows from Proposition 4 below
with
Verification for Example 4: Let D
++ \Theta S n
be the map defined by
++ \Theta S n
where LX is the lower Cholesky factor of X . Also, let
Observe that the continuity of the map \Phi required in Assumption 2(a) follows from Lemma 6. The
remaining requirements in (a) and conditions (b) and (c) of Assumption 2 are straightforward. We
easily see that
++ \Theta S n
which, in view of Lemma 6, is a closed set. Hence, Assumption 2(d) holds. Finally, Assumption 2(e)
follows from Lemma 2.4 of Monteiro and Zanj'acomo (1997) with
Verification for Example 5: Let D
++ \Theta S n
be the map defined by
++ \Theta S n
where LX and U Y are the lower Cholesky factor of X and the upper Cholesky factor of Y , respectively.
Also, let
0g. Observe that the continuity of
the map \Phi required in Assumption 2(a) follows from Lemma 6. The remaining requirements in (a)
and conditions (b) and (c) of Assumption 2 are straightforward. We easily see that
++ \Theta S n
-pfor some - ? 0
which, in view of Lemma 6, is a closed set. Hence, Assumption 2(d) holds. Finally, Assumption 2(e)
follows from Proposition 5 below with
Verification for Example
++ \Theta S n
be the map defined by
++ \Theta S n
is the unique positive definite matrix such that
0g. Observe that the continuity of the map \Phi required in
Assumption 2(a) follows from Lemma 6. The remaining requirements in (a) and conditions (b) and
(c) of Assumption 2 are straightforward. We easily see that
ae
++ \Theta S n
oe
which, in view of Lemma 6, is a closed set. Hence, Assumption 2(d) holds. Assumption 2(e) follows
from Proposition 6 below.
Note that all the sets V in the above examples are convex cones containing the line f-I
We now present the technical results needed for the verification of the Examples 1 to 6 described
above.
Lemma 6 sets Let jjj \Delta jjj be an arbitrary norm in S n such that jjjH jjj - kHk for all H 2 S n .
++ \Theta S n
denote the map of Example 4, 5 or 6 described above. Then, \Phi is
a continuous map and, for any fl 2 (0; 1), the set defined by
++ \Theta S n
is a closed set.
Proof. First note that for (X; Y
++ \Theta S n
++ , we have
and
where the first equality of (19) follows from the fact that W 1=2 XYW \Gamma1=2 is a symmetric matrix. To
establish the continuity of the three maps, it is sufficient to show that if f(X
++ \Theta S n
converges to a point ( -
then the sequences f(W k
converge to 0. Indeed, ( -
implies that fX k ffl Y k g converges to 0, which, in
view of (18) and (19), implies that these three sequences converge to 0.
We now establish the closedness of the set (17), which we denote by -
N fl . It is sufficient to show
that if f(X
converges to ( -
.
and hence
due to the fact that jjj \Delta jjj - k \Delta k. Using (18), we easily see that fE k g is bounded. In view of (21),
this implies that f- k g is bounded. Without loss of generality, we may assume that f- k g converges to
some -
We now consider the two possible cases: -
implies that
equivalently lim k!0 \Phi(X For the map of Example 4, this means that
lim k!0 L T
and for the one in Example 5, that lim k!0 U T
Using
the fact that U T
lower triangular, the last limit implies that lim k!0 U T
both maps \Phi, it follows from (18) that fX k ffl Y k g converges to 0, and hence that ( -
Assume now that - ? 0. We will show that ( -
++ \Theta S n
++ , from which the conclusion that
letting k tend to infinity in (20) and using the fact that -
is continuous on S n
++ \Theta S n
++ . Indeed, assume for contradiction that ( -
++ \Theta S n
++ . Without
loss of generality, we may assume that -
X is singular. Consider first the map \Phi of Example 4. We
have
and since lim k!0 - min (X k Y k
we conclude that lim k!0 - min By (21) this
implies that -
contradicting the assumption that -
Consider now the map \Phi of Example 5. We have
where the inequality follows from the fact that the real part of the spectrum of a real matrix is
contained between the largest and the smallest eigenvalues of its Hermitian part (see p. 187 of Horn
and Johnson (1991), for example) and the fact that U T
being lower triangular has only real
eigenvalues. Note that the sequences fU Y k g and fL X kg are bounded, since kU Y k
U and -
L be accumulation points of fU Y k g and fL X kg, respectively. Clearly,
X, and since -
X is singular, it follows that -
L is also singular. Letting k tend to infinity in
(22), we conclude that
which as above yields the desired contradiction.
Finally, consider the map \Phi of Example 6. We have
and since lim k!0 - min (X k Y k
we conclude that lim k!0 - min By (21) this
implies that -
contradicting the assumption that -
The next three lemmas are used in the proof of Proposition 4.
Lemma 7 ineqtr Let G 2 M n be such that tr
Proof. Defining
? , and using the identities
easily see that
tr
The result now follows by adding the two identities and using the assumption that tr
be a matrix whose eigenvalues are all real and let
(0; 1=
be given. Then, the following implication holds:
Proof. Assume that the left hand side of the implication holds. Using the fact that E, and hence
I , has only real eigenvalues, it is easy to see that tr
and hence the first inequality of the right hand side of the implication holds. The second inequality
follows from Lemma 2.3.3 of Golub and Van Loan [5] and the fact that
Lemma 9 Lyap The following statements hold:
a) for every A 2 S n
++ and H 2 S n , the equation AU has a unique solution U
moreover, this solution satisfies kAUk F - kHk
++ denote the square root function is an analytic function
is the unique solution of X (X) is the
derivative of ' at X and ' 0 (X)H is the linear map ' 0 (X) evaluated at H.
Proof. See Lemmas 2.2 and 2.3 of Monteiro and Tsuchiya (1999).
Proposition 4 tech-bound2 Suppose that
the map of Example 3. If (X; Y
++ is a point such that k(X 1=2 Y 1=2 +Y 1=2 X 1=2 )=2\Gamma-I k F -
fl- for some - ? 0, then
F
where g
Proof. Using Lemma 9(a), it is easy to see that the equation \Phi 0 (X; Y )(\DeltaX; \DeltaY
to
where U and V are the unique solutions of the Lyapunov equations
Multiplying the first (resp., second) equation on the left and on the right by X \Gamma1=2 (resp., Y \Gamma1=2 )
and using Lemma 9(a), we obtain
Using the definition of g
\DeltaX and g
\DeltaY , it follows from (24) and (25) that
Taking the Frobenius norm of both sides of the last equation and using (26), Lemma 8 with
the triangular inequality for norms and the fact that g
obtain
F
F
\DeltaY k F
F
from which (23) follows.
The next result has a proof similar to the one of Proposition 4, and hence we omit it. Instead of
Lemma 9, its proof relies on lemma 2.2 of Monteiro and Zanj'acomo (1997).
Proposition 5 tech-bound3 Suppose that
++ \Theta
is the map in Example 5. If (X; Y
++ \Theta S n
++ is a point such that k(U T
F
where d
Y \DeltaX L \GammaT
X and d
Y \DeltaY LX .
Proposition 6 proposNT Let \Phi : C(0)[ (S n
++ \Theta S n
denote the map of Example 6 and
++ \Theta S n
++ be a point such that k\Phi(X; Y
Then,
Proof. Using the identity easily see that \Phi(X; Y Letting
we have that \Phi(X; Y Hence, the directional derivative of
denote the directional derivative of the function V at the point (X; Y ) along the
direction (\DeltaX; \DeltaY
++ , the condition \Phi 0 (X; Y )(\DeltaX; \DeltaY is equivalent to V
denote the directional derivative of the function W at the point (X; Y ) along the
direction (\DeltaX; \DeltaY ). Then, T satisfies the following equation
obtained from the identity Using Lemma 9(b) and the definition of V , it is easy to see
that the condition is equivalent to
where U is the unique solution of the Lyapunov equation
Letting g
\DeltaX
\DeltaY
the
identities (29), (30) and (31) become
~
\DeltaY tec2NT2 (32)
~
~
Subtracting (33) from (32) and using (34), we obtain that g
U T . This identity together
with (33) and the fact that
imply that
F
last relation implies that ~
Hence, by (32)-(34), we conclude that
equivalently



--R

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

A Primer of Nonlinear Analysis
Matrix Computations: Second Edition
Topics in Matrix Analysis
Reduction of monotone linear complementarity problem over cones to linear programs over cones.
Local convergence of predictor-corrector infeasible- interior-point algorithms for SDPs and SDLCPs
A predictor-corrector interior-point algorithm for the semidefinite linear complementarity problem using the Alizadeh-Haeberly-Overton search direction

Duality and self-duality for conic convex program- ming
Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming

Polynomial convergence of primal-dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions
Properties of an interior-point mapping for mixed complementarity problems
On two interior-point mappings for nonlinear semidefinite complementarity problems
A potential reduction Newton method for constrained equations.
Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming
Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants
A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming
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
On Weighted Centers for Semidefinite Programming
programming.
An interior point potential reduction method for constrained equations.
On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming
--TR
interior point methods;maximal monotonicity;generalized complementarity problems;monotone maps;mixed nonlinear complementarity problems;nonlinear semidefinite programming;weighted central path;continuous trajectories