Interior Point Trajectories in Semidefinite Programming.
In this paper we study  interior point trajectories in semidefinite programming (SDP) including the central path of an SDP. This work was inspired by the seminal work of Megiddo on linear programming trajectories [ Progress in Math. Programming: Interior-Point Algorithms and Related Methods, N. Megiddo, ed., Springer-Verlag, Berlin, 1989, pp. 131--158].  Under an assumption of primal and dual strict feasibility, we show that the primal and dual central paths exist and converge to the analytic centers of the optimal faces of, respectively, the primal and the dual problems. We consider a class of trajectories that are similar to the central path but can be constructed to pass through any given interior feasible or infeasible point, and study their convergence. Finally, we study the    derivatives of  these trajectories and their convergence.
Introduction
The purpose of this paper is to study properties of the trajectories associated
with interior point methods for semidefinite programming (SDP) prob-
lems. Since many aspects of semidefinite programming find close analogs
in linear programming, several interior point methods designed for linear
programming (LP) have been successfully extended to apply to semidefinite
programming (e.g., see [2], [4], [10], [12], [17], [19], [20], [21], [25]). Many
Research supported in part by NSF Grants DMS 91-06195, DMS 94-14438 and DMS
95-27124 and DOE Grant DE-FG02-92ER25126
y This author was supported in part by an IBM Cooperative Fellowship
of these aspects have also been studied in the more general framework of
self-scaled cones in [20], [21].
Many interior point methods can be viewed as iterative approximations
to continuous path-following methods. Our aim is to provide a theoretical
basis for such methods for SDP by describing the limiting behavior of the
continuous central path and related trajectories for such problems.
This work is an extension of the linear programming results in [15] to
semidefinite programming. We characterize the optimal face of an SDP
problem and prove that the central path converges to the analytic center
of the optimal face. Unlike LP problems, an SDP problem does not always
have a strictly complementary primal-dual pair of solutions (e.g, see [3],
[12]). Thus the SDP central path cannot be guaranteed to converge to such
a pair as it does in LP. However, we show that it converges to a "least
nonstrictly complementary" pair, in the sense that the sum of the ranks of
the primal and the dual solutions (viewed as matrices) is as large as possible.
Another issue that makes SDP different from LP is the absence (at least
as far as we know) of a suitable concept of a weighted central path. Given
that it is difficult in practice to obtain a point on the central path, it is
important to have a class of trajectories that have properties similar to the
properties of the central path and that pass through any given pair of interior
primal and dual solutions. Such trajectories for linear programming are introduced
in [6] and [1] and are called primal affine scaling (PAS) trajectories
due to the fact that they correspond to continuous versions of primal affine
scaling iterative algorithms. We study the SDP analogs of PAS-trajectories
and prove that the main convergence results of [1] hold.
We show that under the assumptions of primal and dual nondegeneracy
and strict complementarity defined in [3], the first order derivatives of the
central path are bounded in the limit. We also provide formulae for the
limit of these derivatives and show that the factorization of only one matrix
is required to compute these and all higher order derivatives of a solution
on the central path.
The paper is organized as follows. In Section 2 we describe the central
path for a primal-dual pair of SDP problems and introduce our basic assumptions
and some notation. In Section 3 we characterize the optimal faces of
the primal and the dual SDP problems, and prove our main convergence
result for the primal-dual central path in Section 4. We extend the results
of Section 4 to the shifted central path (an analog of the PAS-trajectory)
in Section 5. Finally, in Section 6 we analyze the limiting properties of the
derivatives of the central path and show that computation of the derivatives
requires factorizing a single matrix for all orders of the derivatives.
2 The Central Path
In this paper we consider the semidefinite programming problem, henceforth
referred to as the primal problem,
n\Thetan denotes the space of real
. The inner product on S n\Thetan is
we mean that X
is positive semidefinite (positive definite).
The problem dual to (P ) is the semidefinite programming problem:
(D) s:t:
Throughout the paper the following are assumed to hold:
Assumption 2.1 The matrices A are linearly independent; i.e.,
implies that u
Assumption 2.2 Both the primal and the dual problem have interior feasible
solutions, i.e.
and
Under Assumption 2.2 both primal and dual problems have finite optimal
solutions, -
X and (-y; -
Z), and the duality gap -
[19]. The optimal
solutions also satisfy -
The central path for the problem (P ) is a trajectory of the solutions
n\Thetan to the following parametric family of problems for values of
the parameter - ? 0 ([13],[19],[25]):
From Assumption 2.2 and the strict convexity of the logarithmic barrier
objective function for any - ? 0, problem (P - ) has a unique solution that
satisfies the Karush-Kuhn-Tucker optimality conditions for (P -
The central path for the dual problem can be defined in an analogous
manner and is the trajectory (y(-); Z(-)) n\Thetan whose points satisfy
the same system (CP - ) as the points X(-) on the primal central path.
Hence it makes sense to refer to the trajectory (X(-); y(-); Z(- ? 0 of
solutions to (CP - ) as the primal-dual central path. Under Assumption 2.2,
not only does this path exist, but also it converges to an optimal primal-dual
solution (e.g, see [13], [19], [26]).
To conclude this section we introduce some notation that we will use
later in the paper. First, we note that the variables X and Z can be viewed
both as symmetric matrices and as vectors (obtained from these matrices by
stacking their columns one after the other), lying in a n(n+1)=2-dimensional
subspace of R n 2
. Whenever we refer to the matrix X as a vector, we denote
it by vec(X). By the constraint matrix A we denote the m \Theta n 2 matrix, the
i-th row of which equals . Note that C ffl
the usual inner product.
The Kronecker product
M\Omega N of matrices M 2 R n\Thetan and N 2 R n\Thetan
is defined as
There are two properties of the Kronecker product that we will need later:
T\Omega M)vec(N) and
(M\Omega P
(MN)\Omega (PS) [7].
If X is a positive semidefinite symmetric matrix, then X has a spectral
is an orthogonal matrix of eigenvectors
of X and   is a diagonal matrix with the eigenvalues of X on the diagonal.
Throughout this paper the upper case letter Q will always denote a matrix
with orthonormal columns and
and\Omega will always denote diagonal matrices
of eigenvalues.
Lastly, from properties of the trace we have
Property 2.3 Let A 2 R n\Thetan , X 2 R r\Thetar and P 2 R n\Thetar . Then A ffl
Property 2.4 Let A 2 R n\Thetan , A - 0 and B 2 R n\Thetan , B - 0. Then
3 Optimal Faces of the Primal and Dual Problem

Properties of the faces of the cone of positive semidefinite matrices, are
studied in [5]. The facial structure of semidefinite programming problems
(i.e., the intersection of the cone of positive semidefinite matrices with an
affine subspace) is studied in general terms in [22], [23]. Here we derive a
particular system which describes the optimal face of an SDP problem.
Let us introduce some more notation and recall some well-known facts.
Let R(X) denote the range (column space) of X . If X is a positive semidefinite
symmetric matrix, it can be factorized as
where   is a diagonal matrix whose diagonal elements are the positive eigen-values
of X and Q is a matrix with orthogonal columns that are eigenvectors
corresponding to these eigenvalues. Clearly, span(Q), the subspace
spanned by the columns of Q, and the dimension of this subspace (i.e., the
number of positive eigenvalues of X) equals the rank of X .
Z be an optimal primal-dual pair of solutions. It is well
known that they can be represented as -

and\Omega are diagonal matrices with the positive eigenvalues of -
Z,
respectively, on their diagonals and Q T
and R( -
X).
O P denote the primal optimal face, i.e., the set of primal optimal
solutions, and let OD denote the dual optimal face. Note that both O P and
OD are convex subsets of affine subspaces of S n\Thetan . By ri O P (ri OD ) we
denote the relative interior of O P (OD ). Then the following lemma holds
[5]:
Lemma 3.1 For any -
any ~
riO D ), R( -
Z)).
This lemma shows that any ~
riO P is an optimal solution of maximum
rank. Moreover, if both -
X and ~
X are in ri O P , it follows from Lemma 3.1
that R( -
X). Let us denote this subspace by R P . Analogously,
let RD be the subspace spanned by the eigenvectors corresponding to the
positive eigenvalues of Z for any dual solution (y; Z) in the relative interior
of OD .
Let dim R From the complementarity of any
primal-dual pair of optimal solutions R P ?RD . Hence, r
we say that the primal-dual pair of problems does not satisfy strict
complementarity. Note that this can never happen in linear programming.
If we define
we have a partition of R n into three mutually
orthogonal subspaces.
be any n \Theta r matrix whose columns form an orthonormal basis
for R P . Then any solution X O P can be written as
so the optimal face of (P ) is given by the set of the solutions to the following
system:
Indeed, for any U feasible for (1), Q P
is feasible for (P ), and since
and Z satisfy
complementary slackness. Therefore, Q
is an optimal solution to (P ).
Similarly, let the columns of Q D
form an orthonormal basis for RD .
Then any optimal dual solution can be written as
the optimal face of (D) is given by the set of solutions to the system:
Notice that the definitions of the primal and dual optimal faces are
invariant with respect to the choices of Q P
and Q D
as long as their columns
form orthonormal bases for the subspaces R P and RD , respectively.
The following lemma shows that under Assumptions 2.1 and 2.2 both
primal and dual optimal faces are bounded. Thus their analytic centers are
well defined, which is important for the results of the next section.
Lemma 3.2 Let Assumptions 2.1 and 2.2 hold, then the optimal sets of the
primal and the dual problems are bounded.
Proof. Suppose that the set of optimal dual solutions is unbounded. That
is, there exists a nonzero direction (u; V ), satisfying:
Multiplying the second equation by an interior feasible primal solution X
which exists by Assumption 2.2, we obtain
Therefore
It then follows that
which by Assumption 2.1 implies
that
The boundedness of the set of optimal primal solutions can be proved in
a similar manner. 2
4 Convergence of the Central Path
We prove in this section that the primal central path converges to the analytic
center of the optimal face O P . First we show that the limit -
X of the
central path is in the relative interior of the optimal face. Then we show
that -
is, in fact, the analytic center of the optimal face. We then extend
these results to the dual central path.
In [27] it is shown that in the case of convex homogeneous self-dual
cones, which includes the case of the cone of positive semidefinite matrices,
the central path converges to a strictly complementary solution provided
that one exists. In [14], under the assumption of strict complementarity, it
is shown that the primal-dual central path of an SDP problem converges to
the analytic center of the optimal face. We obtain the same results without
assuming strict complementarity.
X be the limit of the primal central path as - ! 0.
Lemma 4.1 There exists a spectral factorization -
and a sequence
such that X(- k
, where
spectral factorization of X(- k ).
Proof. The proof follows trivially from the compactness of the set of the
orthogonal matrices. Notice that the limit -
is uniquely defined by -
the limit -
Q, generally speaking, depends on the sequence f- k g. 2
We know that -
X and (-y; -
Z) are optimal solutions to the primal and dual
problems, respectively. We first want to prove that each is in the relative
interior of the optimal face for its respective problem.
Lemma 4.2 -
Z)) belongs to the relative interior of the primal (dual)
optimal face.
Proof. Let (X(-); y(-); Z(-)) be a point on the central path. Let ~
and (~y; ~
riO D . It is trivial to verify that
and since ~
~
Now both terms on the left side of (3) are nonnegative by Proposition 2.4;
hence
~
Consider the sequence f- k g as defined in Lemma 4.1, such that X(- k
X and the spectral factorizations
~
~
(The columns
of ~
Q are eigenvectors of ~
X that span R P .) Let us order the columns of
Q and partition -
into two parts [ -
QND ] so that -
Q P has r columns
and -
~
Q P is nonsingular. This is always possible since -
Q P has full
column rank. Let us order the columns of Q(- k ) and the columns and
rows of -
and  (- k ) and partition them according to the column order and
partitioning of -
Q. Then -
ND (- k ), and from (4)
~
~
~
~
~
Since both terms in this sum are nonnegative by Proposition 2.4, it follows
from Property 2.3 that
~
~
~
~
~
U P
~
~
~
U P
~
~
It then follows
from (5) that
r
the sum of the ratios ( -
finite, it follows that
X has rank r proving
that -
ri O P . Similarly, it can be shown that (-y; -
ri OD . 2
From Lemma 3.2 it follows that the analytic center of the optimal face
O P is well defined. We now show that -
is, in fact, this analytic center.
Theorem 4.3 Let -
X be the limit of the primal central path as - ! 0. Then
U depends on he choice of the orthonormal basis Q P
for R P and is the unique solution to the problem
X is the analytic center of the primal optimal face.
Proof. Problem (6) can be rewritten in an equivalent form:
where c(0) is the optimal objective function value. The solution of this
problem is unique and satisfies the following system of optimality conditions:
For any fixed - ? 0, let C ffl is the solution to
the problem (CP - ). Then X(-) is a solution to the following problem:
Using notation of Lemma 4.2 -
QND ] is a matrix of eigenvectors of -
P is a diagonal
matrix of positive eigenvalues of -
X (r of them) and -
4.2 it follows that -
As in Lemma 4.2 consider the convergent sequence X(- k
to -
Q and  (- k ) converges to -
as
and  (- k ) is diagonal, requiring X in (9) to be of the form
where U - 0 and V is equal to   ND (- k ), does not affect the solution
of problem (9). We restrict V and not U because, as we have already
shown, the sequence of the solutions converges to an
optimal solution, where and U is a positive definite matrix. Also,
. Therefore from (9) and Property 2.3 we obtain
the following maximization problem:
The unique optimal solution satisfies the following
system:
As
Q and the system (11) converges to (8) with Q
Since   P (- k ) is the solution to (11), then the limit -
has to satisfy
(8). This proves that -
X is the analytic center of the primal optimal face. 2
As in LP, problems (P ) and (D) can be written in a "symmetric" form.
Specifically, we can use the "conic" formulation given in Chapter 3 of [19]
(see also [25]). Let L be the subspace of S n\Thetan spanned by A
and D 2 S n\Thetan be such that A i ffl
and (D) can be formulated as
and
(D
Consequently, all the results in this section extend to the dual problem, and
in particular, in terms of formulation (D) of the dual, we have the following:
Theorem 4.4 Let (-y; -
Z) be a limit point of the dual central path. Then
W depends on the choice of the orthogonal basis Q D
for RD and is the unique solution to the problem
Z) is the analytic center of the dual optimal face.
5 Shifted Central Paths
In this section we present a class of primal affine scaling trajectories analogous
to those introduced by Bayer and Lagarias [6] and later studied by
Adler and Monteiro [1]. Affine scaling vector fields associated with semidefinite
programs are studied in [8] and [9]. Here we analyze the limiting
behavior of affine scaling trajectories in SDP.
As far as we know there is no suitable concept of a scaled or weighted
central path, defined as a trajectory of solution of a class of minimization
problems, passing through any given pair of primal and dual interior solu-
tions. Therefore, we do not consider weighted trajectories as in [15]. How-
ever, we can consider "shifted" central paths, or primal affine scaling (PAS)
trajectories, as they are called in [1] or A-trajectories as they are called in
[6]. We study the properties and convergence of these trajectories, using the
same techniques that we used for the central path.
In [1] it is shown that the tangent to a PAS trajectory at any given point
has the same direction as the primal affine scaling step. The same is true in
semidefinite programming [9].
Consider the family of problems dependent on a parameter - ? 0
n\Thetan is some arbitrary fixed symmetric matrix. If problem (SP - )
has a solution for some - ? 0 then that solution is unique and satisfies the
Karush-Kuhn-Tucker necessary conditions
The trajectory of dual solutions (y(-); Z(-)) defined by the system (SCP - ),
parametrized by -, is generally different from the dual shifted central path
associated with T . Thus, when referring to the shifted central path, we
mean the primal and dual trajectories defined by (SCP - ).
For any given - ? 0 and T 2 S n\Thetan if there exists a (y n\Thetan
such that
-T and Z 0 - 0 then (SCP - ) has a unique
solution. Using the notation of [1], let Y (T ;
and I(T ;g. By Assumption 2.2, Y (T ;
T , and it is easy to see that I(T ) is an open interval, which is nonempty
as long as C \Gamma -T is not spanned by the matrices A i m). Thus
Lemma 5.1 If the feasible set of problem (P ) is bounded, then I(T
(0; 1) for any T 2 S n\Thetan ; i.e., (SCP - ) has a unique solution for all
1.
This lemma is proved in [24] and a similar, but more general, result is
proved as Theorem 2.4 in [9]. We want to choose T so that the shifted
central path passes through an arbitrary given primal-dual pair of interior
solutions. Specifically, given (X
then it is easy to verify that I(T consequently, that I(T ) 3
In other words this choice guarantees the existence of a trajectory
passing through the primal-dual point (X
It is shown in [1] (Proposition 2.4) that in linear programming the choice
of the initial dual solution (y does not affect the PAS trajectory. The
same is true in the case of the shifted central path (i.e., PAS trajectory) for
a semidefinite program. The proofs are identical.
We are ready to discuss the limiting behavior of the shifted central path.
Z) be a limit point of the solution (X(-); y(-); Z(-)) to (SCP - )
In [9] it is shown that -
X is an optimal solution to (P ) and (-y; -
is an optimal solution to (D). As in the case of the central path, we can
show that -
X is in the relative interior of the primal optimal face and (-y; -
is in the relative interior of the dual optimal face. The proof is analogous
to the proof of Lemma 4.2 with the exception that X(-) ffl Z(- N- for
some large number N .
More importantly, it is trivial to extend the proof of Theorem 4.3 to give
Theorem 5.2 -
U is the unique solution to the problem
X is the "shifted" analytic center of the primal optimal face.
Just as in the case of LP [1], the dual solutions of the shifted central
path converge to the analytic center (not shifted) of the dual optimal face.
Theorem 5.3 Let (-y; -
Z) be a limit dual point of the shifted central path,
then -
W is the unique solution to the problem
Z) is the analytic center of the dual optimal face.
Proof. First we observe that the dual solution (y(-); Z(-)) associated
with the system of optimality condinions (SCP - ) is the unique optimal
solution to the system
s:t:
Given a sequence Z(- k
Z, we know that Z(- k
Z. Let
be a sequence of dual solutions on the shifted central path,
which converges to (-y; -
Z) and for which the sequence of spectral factorizations
converges. By a similar argument
to that used in the proof of Theorem 4.3,
=\Omega D (- k ) is a
solution to the following problem
When the solution to the above problem converges to the solution
to the problem
which is equivalent to Problem (14) defining the analytic center of the dual
optimal face. Thus (-y; -
W ) is the unique solution of Problem (14). 2
Thus, the choice of the initial point (X affects the limit of the
trajectory of the primal solutions (obviously, only if the optimal face is
of dimension greater than zero), but does not affect the limit of the dual
trajectory.
Remark. Notice, that the dual problem (15) is in fact a shifted barrier
problem for the original dual (D).
We now consider the tangent to a shifted central path at an arbitrary
point on it. Our results apply to the central path as a special case
Let (X; (we omit the argument - for simplicity) be on the shifted
central path corresponding to a given shift T . Differentiating the system
respect to - for any - ? 0, yields
In [9] it is shown that this system of differential equations is generated
by the generalized primal affine scaling vector field. In our terms, this is
equivalent to the fact that we can rewrite the above system as
y, -
X\Omega X and H
(i.e., the rows of -
A equal
and vec( -
can be viewed as an orthogonal
projection of a scaled objective vector onto the kernel of a scaled constraint
matrix, where the scaling depends only on the primal solution. The direction
of the tangent is
and the directions -
y and -
Z can be calculated from the dual estimates y E
and
Z , which in turn, can be computed from the projection
operator.
Remark. We would like to study the limiting behavior of the dual estimates
Z that are computed at every step of an algorithm that
uses an affine scaling direction. In the next section we show that under
assumptions of strict complementarity and primal and dual nondegeneracy
the limit of (y the limit of (y(-); Z(-)) as - ! 0.
6 Derivatives of the Central and Shifted Central
We begin this section by showing that as in case of linear programming
[15] the computation of derivatives of any order of solutions on the central
path or a shifted central path involves inverting a single matrix. In contrast
with LP, the Schur complement of this matrix, which we must factorize, is
fully dense, even if the constraint matrices are sparse. Consequently, this
factorization step is very expensive in SDP and it is desirable to use as
much information (e.g. higher order derivatives) as possible from it, as in
the interior point LP methods proposed in [18] and [16].
Let us consider solutions X and (y; Z) on the shifted central path corresponding
to a shift T . ( X , y and Z depend on -, but we omit the argument.)
As shown in the previous section (see (17)) the derivatives -
y in vector
form satisfy
y
For the second derivatives we have
y
and it can be easily shown by induction that the k-th derivatives X (k) and
y (k) on the central path must satisfy a system of equations of the form
y
where R is a function of (T ; X; -
We now turn to the limiting properties of the first order derivatives of
the central path. As earlier, let ( -
Z) be the limit of the central path.
We need the following assumption:
Assumption 6.1 i) The primal and dual solutions -
X and (-y; -
are
strictly
ii) The primal solution -
X is nondegenerate; i.e., the matrices
QD
are linearly independent in S n\Thetan .
iii) The dual solution (-y; -
Z) is nondegenerate; i.e., the matrices
span S r\Thetar .
For these and other equivalent definitions of primal and dual nondegeneracy
see Alizadeh, Haeberly, and Overton [3]. They also prove that under
Assumption 6.1 the optimal primal-dual solution is unique. Hence if Assumption
6.1 holds it makes sense to say that Problems (P ) and (D) are
nondegenerate and strictly complementary. For the remainder of this section
we shall assume that Assumption 6.1 holds.
To show that the first order derivatives of the central path converge to
finite limits as - ! 0, we consider the following system which, as shown in
[4], is equivalent to (CP - ):2 (XZ
Viewing all symmetric matrices in the above system as vectors in R n(n+1)=2
and differentiating, we obtain the following system6 4
Z   I 0 X   I
y
where svec maps a matrix in S n\Thetan into a vector in R n(n+1)=2 and   denotes
"symmetric" Kronecker product. See [4] for definitions and properties of
svec and  . Alizadeh, Haeberly, and Overton in [4] prove that under Assumption
6.1 the coefficient matrix of (21) is nonsingular at the limit
Therefore, -
y and -
Z are bounded and converge as - ! 0. Geometrically
this means that the central path approaches the boundary of the feasible
region at a strictly positive angle; i.e., the angle between the tangent to
the central path and the tangent to the boundary at the optimal solution is
strictly positive. From
X, and the boundedness of the derivative of X
we conclude that -
X, where -
X(0) is
the right derivative of X(-) at
Similar arguments prove that the derivatives of the primal and dual
solutions on the shifted central path are bounded and converge as - ! 0.
We obtain system similar to (21), with the same coefficient matrix and the
right hand side, which depends on the shift T and on X and is uniformly
bounded as - ! 0.
Let us consider the derivatives of the eigenvalues of X and Z on the
central path. Since is symmetric and is a smooth function of a
single parameter, its eigenvalues can be ordered so that - of X is
in C 1 [11]. If - i is an eigenvalue of multiplicity k then -
the vector of eigenvalues of the matrix
where Q i is a matrix of eigenvectors of X corresponding to - i . If
and -
does not generally converge; however, the
subspace spanned by the columns of Q i converges as - ! 0 and therefore
any accumulation point of the matrices (22) has the same eigenvalues. Thus
the limit of -
exists. The same can be shown for the derivatives -
i of the
of the the dual slack matrix Z.
Let us consider the eigenvalues of X and Z that converge to zero. The
multiplicity of the zero eigenvalue of -
s. The multiplicity of the
zero eigenvalue of -
Z is r. We know that for X and Z on the central path,
and therefore
Z as - ! 0,
Considering the above system in more detail, we obtain
QD
QD
QD
QD
From the diagonal blocks of this matrix equa-
tion, it then follows that
and
Therefore, we can conclude that there are orderings of the eigenvalues of -
and -
Z , for which -
D and
P . This generalizes the result on
the limits of the derivatives of nonbasic variables (i.e., variables converging
to zero) in linear programming. Complete information on -
Z can be
obtained by solving the system (21).
We can now conclude, that the dual estimates y
y and Z
Z that appear in (18) converge to the same limits as y and Z, since -
y
and -
Z are bounded as - ! 0.
Remark. To prove the convergence of the derivatives of the central
path as - ! 0 we assumed primal and dual nondegeneracy and strict com-
plementarity. These assumptions imply the uniqueness of the primal and
dual solutions [3]. However, we conjecture that it is sufficient to only assume
strict complementarity. Note that strict complementarity is necessary
for boundedness of the derivatives, since if there is an index i such that both
primal and dual eigenvalues - i (-
then from
hence that
both -
cannot be finite at the limit as - ! 0.
In [14] it is shown that assuming strict complementarity,
O(-) and
which implies that the derivatives of the
central path are bounded as - ! 0.

Acknowledgement

. The authors are grateful to Yurii Nesterov for
bringing the question of the convergence of the central path in SDP to their
attention, to Michael Overton for many stimulating discussions on SDP, and
to Jean-Pierre Haeberly and two anonymous referees for helpful comments
on earlier versions of the paper.



--R

"Limiting behavior of the affine scaling continuous trajectories for linear programming problems"
"Interior point methods in semidefinite programming with applications to combinatorial optimization"
"Complementarity and nondegeneracy in semidefinite programming"
"Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical results"
"Cones of diagonally dominant matri- ces"
"The nonlinear geometry of linear pro- gramming. I. Affine and projective scaling trajectories"
Kronecker Products and Matrix Calculus: with Applica- tions
"On a matrix generalization of affine-scaling vector fields"
"A Hamiltonian structure of generalized affine scaling vector fields"
"An interior-point method for semidefinite programming"
A Short Introduction to Perturbation Theory for Linear Op- erators
"Local convergence of predictor-corrector Infeasible-Interior-Point Algorithms for SDPs and SDLCPs"
"Interior-point methods for monotone semidefinite linear complementarity problem in symmetric matri- ces"
"Superlinear convergence of a symmetric primal-dual path following algorithms for semidefinite program- ming"
"Pathways to the optimal set in linear programming"
"Higher order methods and their performance"
"Primal-dual path following algorithms for semidefinite programming"
"A polynomial time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension"
Interior point Methods in Convex Programming: Theory and Application
"Self-scaled cones and interior-point methods in nonlinear programming"
"Primal-dual interior point algorithms for self-scaled cones"
"On the facial structure of cone-LP's and semi-definite pro- grams"
"Strong duality for semidefinite programming"
"Issues in interior point methods in semidefintie and linear programming"
"A primal-dual potential reduction method for problems involving matrix inequalities"
"Positive-definite programming"
"Convergence behavior on central paths for convex homogeneous self-dual cones"
"On Extending primal-dual interior-point algorithms from linear programming to semidefinite programming"
--TR

--CTR
Anthony Man-Cho So , Yinyu Ye, Theory of semidefinite programming for sensor network localization, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
interior point methods;central path;semidefinite programming