Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming.
This paper establishes the superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming (SDP) under the assumptions that the semidefinite program has a strictly complementary primal-dual optimal solution and that the size of the central path neighborhood tends to zero. The interior point algorithm considered here closely resembles the Mizuno--Todd--Ye predictor-corrector method for linear programming which is known to be quadratically convergent. It is shown that when the iterates are well centered, the duality gap is reduced superlinearly after each predictor step. Indeed, if each predictor step is succeeded by r consecutive corrector steps then the predictor reduces the duality gap superlinearly with order 2 The proof relies on a careful analysis of the central path for SDP. It is shown that under the strict complementarity assumption, the primal-dual central path converges to the analytic center of the primal-dual optimal solution set, and the distance from any point on the central path to this analytic center is bounded by the duality gap.
Introduction
Recently, there have been many interior point algorithms developed for semidefinite programming
(SDP), see for example [1, 2, 5, 9, 11, 13, 17]. These algorithms differ in their choices of scaling
matrix, the size of the central path neighborhoods, and stepsize rules, among others. In particular,
the algorithms of Kojima-Shida-Hara [5] and Nesterov-Todd [11] are based on the primal-dual
scaling and they both can be viewed as extensions of the predictor-corrector method for linear
programming [8]. It has been shown [4, 6, 11, 13, 17] that these algorithms for SDP retain many
important properties of the interior point algorithms for linear programming including polynomial
complexity. For an overview of SDP and its applications, we refer to Vanderberghe and Boyd [15].
However, there exists considerable difficulty in extending one key property of the predictor-corrector
method for linear programming to the interior point algorithms for SDP. This is the
property of quadratic convergence of the duality gap (see [16] for a proof of the LCP case). In
some sense, the need for superlinear convergence in solving SDP is more pronounced than that for
the linear programming case. This is because for SDP there cannot exist any finite termination
procedures as in the case of linear programming. Indeed, the recent papers of Kojima-Shida-Shidoh
[4] and Potra-Sheng [12] are both focused on the issue of superlinear convergence for solving SDP.
In particular, the latter reference provided a sufficient condition for the superlinear convergence of
an infeasible path following algorithm, while the former reference [4] established the superlinear
convergence of their algorithm [5] under certain key assumptions. These assumptions are: (1) SDP
is nondegenerate in the sense that the Jacobian matrix of its KKT system is nonsingular; (2) SDP
has a strictly complementary optimal solution; (3) the iterates converge tangentially to the central
path in the sense that the size of the central path neighborhood in which the iterates reside must
tend to zero. Among these three assumptions for superlinear convergence, (2) is inevitable since it
is needed even in the case of LCP (see [16]). Assumption (3) is needed to ensure the duality gap
is reduced superlinearly after each predictor step for all points in the central path neighborhood.
In the reference [4], an example was given which showed that, without the tangential convergence
assumption, the duality gap is reduced only linearly after one predictor step for certain points in
the central path neighborhood.
Our goal in this paper is to establish the superlinear convergence of a symmetric path following
algorithm for SDP under the only assumptions of (2) and (3) (i.e., without the nondegeneracy
assumption). In particular, we consider the primal-dual path following algorithm of Nesterov-
Todd [11] (later discovered independently by Sturm and Zhang [13] using a V -space notion). In
this paper we adopt the framework of [13] since it greatly facilitates the subsequent analysis. We
show that this symmetric primal-dual path following algorithm has an order of convergence that
is asymptotically quadratic (i.e., sub-quadratic). Indeed, for any given constant positive integer r,
the algorithm can be set so that the duality gap decreases superlinearly with order 2
1+2 \Gamma2r after one
predictor (affine scaling) step followed by (at most) r corrector steps. The cornerstone in our bid
to establish this superlinear convergence result is a bound on the distance from any point on the
central path to the optimal solution set (see Section 3). Specifically, it is shown that, under the
strict complementarity assumption, the primal-dual central path converges to the analytic center
of the optimal solution set, and that the distance to this analytic center from any point on the
central path can be bounded above by the duality gap. These properties of the central path are
algorithm-independent and are likely to be useful in the analysis of other interior point algorithms
for SDP.
The organization of this paper is as follows. At the end of this section, we describe some basic
notation to be used in this paper. In Section 2, we will discuss some fundamental background
notions, and we will make two assumptions concerning the solution set of the SDP. In Section 3
we will analyze the limiting behavior of the primal-dual central path. In Section 4, the notion
of V -space for SDP is reviewed and a path following algorithm in the spirit of [13] is introduced.
The superlinear convergence of this algorithm is established in Section 5. Finally, some concluding
remarks are given in Section 6.
Notation. The space of symmetric n \Theta n matrices will be denoted S. Given X and Y in ! n\Thetan ,
the standard inner product is defined by
where tr (\Delta) denotes the trace of a matrix. The notation X ? Y denotes orthogonality in the sense
that The Euclidean norm and its associated operator norm, viz. the spectral norm,
are both denoted by k\Deltak. The Frobenius norm of X is kXk
positive
(semi-) definite, we write (X - The cone of positive semi-definite matrices is denoted
by S+ and the cone of positive definite matrices is S++ . The identity matrix is denoted by I. We
use the standard "big O" and "small o" notation. In particular, w(-) = O(-) with - ? 0 means
that there is a positive constant \Gamma, possibly dependent on problem data but independent of -, such
that w(- \Gamma- for all -; means that lim -!0
O(w(-)). For a positive definite
matrix, we use "O" and "\Theta" to denote the order of all its eigenvalues. Hence, for W (-) 2 S++ ,
the notation W signifies the existence of \Gamma ? 0 such
Problem formulation
A semidefinite programming (SDP) problem is given as
subject to A (i) ffl
. The decision variable is S. The
corresponding dual program can be formulated as
subject to
Denote the feasible sets of (P) and (D) by F P and FD respectively, i.e.
and
We make the following assumptions throughout this paper.
Assumption 1 There exist positive definite solutions X 2 F P and Z 2 FD for (P) and (D)
respectively.
Assumption 2 There exists a pair of strictly complementary primal-dual optimal solutions for (P)
and (D). Specifically, there exists (X   ; Z   FD such that
0, we can diagonalize X   and Z   simultaneously. Therefore, by applying
an orthonormal transformation to the problem data if necessary, we can assume without loss of
generality that X   , Z   are both diagonal and of the form
positive scalars Here the subscripts B and N signify the "basic" and
"nonbasic" subspaces (following the terminology of linear programming). Throughout this paper,
the decomposition of any n \Theta n matrix X is always made with respect to the above partition B
and N . In fact, we shall adhere to the following notation throughout:
U XN
so XU will always denote the off-diagonal block of X with size K \Theta (n \Gamma K), etc.
Notice that X 2 F P is an optimal solution to (P) if and only if XZ  Hence, by Assumption
2, the primal optimal solution set can be written as
F
Analogously, the dual optimal solution set is given by
F
Given - 2 !++ , the pair (X; Z) 2 F P \Theta FD is said to be the -center (X(-); Z(-)) if and only
if
We refer to [5, 14] for a proof of the existence and uniqueness of -centers. The central path of the
problem (P) is the curve
To be consistent with the above definition of the central path, we define the analytic center of
F
P as the unique solution X a of the system
X a
P and ZB - 0:
In a similar fashion, we define the analytic center of F
D as the unique solution Z a of the system
XNZ a
A (i)
3 Properties of the central path
The notion of central path plays a fundamental role in the development of interior point methods
for linear programming. In this section, we shall study the analytic properties of the central path
in the context of semidefinite programming. These properties will be used in Section 5 where we
perform convergence analysis of a predictor-corrector algorithm for SDP.
For linear programming (i.e., A (i) 's and C are diagonal), it is known that the central path
curve converges: (X(-); being the analytic center of
the primal and dual optimal solution sets F
P and F
respectively ([7]). It is also known for linear
programming that the central path does not approach (X a ; Z a ) tangentially to the optimal solution
set, viz. it is shown in [10] that
In the following we shall extend these result to the semidefinite programs (P) and (D).
The following lemma shows that the set
is bounded.
Lemma 3.1 For any - ? 0 there holds
Proof. We have
where we used the property (X(-) in the second equality. Since X(1) - 0
and Z(1) - 0, we have
Q.E.D.
It follows from Lemma 3.1 that the central path has a limit point. We will now show that
any limit point of the central path f(X(-); Z(-))g is a strictly complementary optimal primal-dual
Lemma 3.2 For any - 2 (0; 1) there holds
Hence, any limit point of f(X(-); Z(-))g as - ! 0 is a pair of strictly complementary primal-dual
optimal solutions of (P) and (D).
Proof. Let 1. For notational convenience, we will use X and Z to denote the matrices
X(-) and Z(-). Let (X   ; Z   ) be the pair of strictly complementary primal-dual optimal solutions
postulated by Assumption 2. Since A (i) ffl
Therefore, we have
where the last step follows from (2.1). Since (by the
positive semidefiniteness of X and Z), we obtain
From
Now consider the identities
log det
log det
U
log det XB log det
log det ZN log det
By the estimates (3.1) and using Lemma 3.1, we see that
Therefore each of the four logarithm terms in the preceding equation are bounded from above as
these four terms sum to zero, we must have
Together with (3.1), this implies
This completes the proof of the lemma. Q.E.D.
Lemma 3.2 provides a precise result on the order of the eigenvalues of XB (-); XN (-); ZB (-)
and ZN (-). We will now prove a preliminary result on the order of the off-diagonal blocks XU (-)
and ZU (-).
Lemma 3.3 For - 2 (0; 1), there holds
\GammaX U (-) ffl ZU
Proof.
By the central path definition, we have
Expanding the right-hand side and comparing the upper-right corner of the above identity, we have
or equivalently,
Using XB Lemma 3.2), this implies that
This proves the first part of the lemma.
We now prove (3.2). Let f(X(- k ); Z(- k :::g be an arbitrary convergent sequence
of the central path with - k ! 0. By Lemma 3.2, the limit of this sequence satisfies strict comple-
mentarity. Let (X   ; Z   ) denote this limit point so that
As before, we assume without loss of generality that X   and Z   are diagonal. In addition, since
(3.2) holds trivially when kXU (- k
First, we divide both sides of (3.3) by kXU (- k )k and let k !1 to obtain
U Z
U and Z 1
U are defined by
U := lim
U := lim
(If the above limits do not exist, then we define X 1
U and Z 1
U to be any two limit points of the
corresponding sequences.) Since X
B and Z
are both positive diagonal matrices, it follows that
the nonzero entries of the matrices X 1
U must have opposite signs. By kX 1
that
This establishes (3.2) along the sequence f(X(- k ); Z(- k :::g. Since this sequence is
arbitrary, we see (3.2) holds.
It remains to establish the last part of the lemma. Once again, we consider an arbitrary
convergent sequence f(X(- k ); Z(- k on the central path with - k ! 0; we continue
to use the same notation X   , Z   , X 1
U defined above. Since kZU (- k
only need to show kXU (- k . Assume this is not the case. Using Lemma 3.2 and
passing onto a subsequence if necessary, we have kXU (- k
Dividing both sides of this equation by kXU (- k )k 2 and taking limit yields
U
Therefore, the limit in the preceding equation equals zero, implying
But this contradicts (3.5), so we must have
The proof is complete. Q.E.D.
We now use Lemma 3.2 and Lemma 3.3 to prove that the central path f(X(-); Z(- ? 0g
converges to (X a ; Z a ), and to estimate the rate at which it converges to this limit.
Lemma 3.4 The primal-dual central path f(X(-); Z(- ? 0g converges to the analytic centers
(X a ; Z a ) of F
P and F
D respectively. Moreover, if we let
ffl(-) := kXU (-)k
then
Proof. Suppose 1. By expanding X(-)Z(-I and comparing the upper-left block,
we obtain
Pre-multiplying both sides with
Let J be an index set of minimal cardinality such that
As Z
it follows from the dual feasibility and (3.6) that-
Now consider the following nonlinear system of equations:
A (i)
By (2.3), we know that X a
B is a solution of (3.8) for some - a
. Using the linear independence
of the matrices A (i)
using the fact that X a
B is positive definite, it can be checked that
the Jacobian (with respect to the variables XB and - i , of the nonlinear system (3.8) is
nonsingular at the solution X a
Hence we can apply the classical inverse function
theorem to the above nonlinear system at the point:
By (3.7) we have
and from X(-) 2 F P we obtain
Combining this with (3.9) and (3.10) yields
It can be shown with an analogous argument that
The proof is complete. Q.E.D.
Lemma 3.4 only provides a rough sketch of the convergence behavior of the central path as
Our goal is to characterize this convergence behavior more precisely.
Theorem 3.1 Let - 2 (0; 1). There holds
and
Proof. The estimate (3.11) is already known from Lemma 3.2, so we only need to prove (3.12).
By Lemma 3.3 and Lemma 3.4, it is sufficient to show that
Suppose to the contrary that there exists a sequence
with kXU (- k )k ? 0 for all k and
lim
0:
To simplify notations, we introduce
(By virtue of Lemma 3.4, we can assume the above limit exists because otherwise we can always
pass onto a convergent subsequence.) From Lemma 3.3 it follows that
lim
Since for each Z 2 FD we have
it follows
We know from Lemma 3.2 that ZB (- k so that the above relation implies
lim
0:
Analogously, it can be shown that
lim
0: (3:15)
As (X(- k we have from (3.14) and (3.15) that
which clearly contradicts (3.2). The proof is complete. Q.E.D.
Theorem 3.1 characterizes completely the limiting behavior of the primal-dual central path as
We point out that this limiting behavior was well understood in the context of linear
programming and the monotone horizontal linear complementarity problem, see Megiddo [7] and
Monteiro and Tsuchiya [10] respectively. Notice that under a Nondegeneracy Assumption (i.e.,
the Jacobian of the nonlinear system (2.2) is nonsingular at (X a ; Z a )), the estimates (3.12) follow
immediately from the application of the classical inverse function theorem. Thus, the real contribution
of Theorem 3.1 lies in establishing these estimates in the absence of the nondegeneracy
assumption.
It is known that in the case of linear programming the proof of quadratic convergence of
predictor-corrector interior point algorithms required an error bound result of Hoffman. This error
bound states that the distance from any vector x 2 ! n to a polyhedral set P ag can
be bounded in terms of the "amount of constraint violation" at x, namely
denotes the positive part of a vector. More precisely, Hoffman's error bound ([3]) states that there
exists some constant - ? 0 such that
Unfortunately, this error bound no longer holds for linear systems over the cone of positive semidefinite
matrices (see the example below). In fact, much of the difficulty in the local analysis of interior
point algorithms for SDP can be attributed to this lack of Hoffman's error bound result (see the
analysis of [4, 12]). Specifically, without such error bound result, it is difficult to estimate the
distance from the current iterates to the optimal solution set. In essence, what we have established
in Theorem 3.1 is an error bound result along the central path. In other words, although Hoffman
type error bound cannot hold over the entire feasible set of (P), it nevertheless still holds true on
the restricted region "near the central path". One consequence of this restriction to the central
path is that we will need to require the iterates stay "sufficiently close" to the central path in order
to establish the superlinear convergence of the algorithm. Such a requirement on the iterates was
called "tangential convergence to the optimal solution set" by Kojima et. al. [4]. Notice that
the analysis in this reference required the additional nondegeneracy assumption to establish their
superlinear convergence result. In contrast, this assumption is no longer needed in our analysis
because Theorem 3.1 holds without the nondegeneracy assumption.
Example. Consider the following linear system over the cone of positive semidefinite matrices in
Clearly, there is exactly one solution X   to the above linear system, namely
For each ffl ? 0, consider the matrix
Clearly, X(ffl) - 0. The amount of constraint violation is equal to ffl 2 . However, the distance
\Theta(ffl). Thus, there cannot exist some fixed - ? 0 such that
for all ffl ? 0. Instead, we have in this case that is, the error bound
holds with an exponent of 1=2.
4 A polynomial predictor-corrector algorithm
We begin by summarizing some of the results on V -space path following for SDP that were obtained
in [13].
Let (X; Z) 2 F P \Theta FD with X - 0; Z - 0. Then, there exists a unique positive definite matrix
S++ such that ([13, Lemma 2.1])
Let L be such that
and let V := L T ZL. It follows that
The quantity
serves as a centrality measure, with - := X ffl Z=n. It is easy to see that the central path is the set of
solutions (X; Z) with ffi(X; equivalently, those solutions for which
we have
In V -space path following, we want to drive the V -iterates towards the origin by Newton's method,
in such a way that the iterates reside in a cone around the identity matrix. Before stating the
Newton equation, we need to introduce the linear space A(L),
and its orthoplement in S
A Newton direction for obtaining a (fl-center, for some fl 2 [0; 1], is the solution (\DeltaX; \DeltaZ ) of
the following system of linear equations ([13], equation (17)):
\DeltaX
For we denote the solution of (4.4) by (\DeltaX p ; \DeltaZ p ), the predictor direction. For
solution is denoted by (\DeltaX c ; \DeltaZ c ), the corrector direction. If we let
then we can rewrite (4.4) as
It follows from orthogonality that
F
F
The corrector direction does not change the duality gap,
whereas
for any t 2 !, see equation (16) of [13].
Algorithm SDP
Given positive integer r.
REPEAT (main iteration)
Compute the largest step t k such that for all there holds
and
IF ffi(X; Z) - fi k THEN exit loop.
Compute
UNTIL convergence.
Interestingly, each corrector step reduces ffi(\Delta; \Delta) at a quadratic rate as stated in the following
result:
Lemma 4.1 If ffi(X; Z) - 1
Proof. It follows from Lemma 4.5 in [13] that
Hence, the desired result is an immediate consequence of Lemma 4.4 in [13]. Q.E.D.
Also, it follows from (4.6), (4.7) and Lemma 4.1 that for any k ? 1
Furthermore, if fi only one corrector step (i.e., needed to recenter the iterate
(see [13]). In other words, the iterations of Algorithm SDP are identical to that of the primal-dual
predictor-corrector algorithm of [13], for all k with
We can therefore conclude from Theorem 5.2 in [13] that the algorithm yields - k - fflfor -
O(
log(- 0 =ffl)). Thus, we have the following polynomial complexity result.
Theorem 4.1 For each generate an iterate (X
ffl in at most O(
predictor-corrector steps.
In addition to having polynomial complexity, Algorithm SDP also possesses a superlinear rate
of convergence. We prove this in the next section.
5 Convergence analysis
We begin by establishing the global convergence of Algorithm SDP. Notice that Algorithm SDP
chooses the predictor step length t k to be the largest step such that for all there holds
oe
It was shown in [13] (equation (21) therein) that
Combining (5.1) and (5.2), we can easily establish the global convergence of Algorithm SDP.
Theorem 5.1 There holds
lim
i.e. Algorithm SDP is globally convergent.
Proof. Due to (4.7), - . is a monotone decreasing sequence. Hence, the sequence has a
limit. Suppose contrary to the statement of the lemma that
Then, we obtain from (4.5), (5.1) and (5.2) that t Together with (4.7) this implies that
= \Theta(1), which contradicts (5.3). Q.E.D.
Next we proceed to establish the superlinear convergence of Algorithm SDP. In light of (4.7),
we only need to show that the predictor step length t k approaches to 1. Hence we are led to bound
t k from below. For this purpose, we note from (5.2) that, for t 2 (0; 1),
Thus, if we can properly bound
, then we will obtain a lower bound on the predictor
step length t k .
To begin, let us consider L - with
Remark that
Now define the predictor direction starting from the solution (X(-); Z(-)) on the central path as
Z a ) be the analytic center of the optimal solution set in the L -transformed space,
Z a := L T
- Z a
We will show in Lemma 5.1 below that \Delta -
is close to the optimal step -
We will bound the difference between \Delta -
afterwards.
Lemma 5.1 There holds
X a
Z a
Proof. Since
it follows
Z a
Z a
X a
Therefore, the matrix (
Z a ), or equivalently, the matrix
is symmetric. By the property of F-norm, we obtain
Z a )
where the last step follows from Theorem 3.1. Now since -
we have
Z a )
Z a
As
Z a 2 A(L - );
it follows that fl fl
X a
F
Z a
F
F
where last step is due to (5.5). This proves the lemma. Q.E.D.
Lemma 5.1 applies only to (\Delta -
namely the predictor directions for the points
located exactly on the central path. What we need is a similar bound for (\Delta -
at points close to the central path). This leads us to bound the difference \Delta -
our next goal is to show (Lemma 5.5) that
O(
We prove this bound by a sequence of lemmas. Let D be given by (4.1) and define
so that -
Choose L by
and notice that indeed LL stipulated by (4.2).
Lemma 5.2 Suppose ffi(X; Z) - 1. There holds
Proof. Let
Clearly, \Delta x (-) and \Delta z (-) are symmetric and \Delta x (-) ? \Delta z (-). Let ae denote the smallest eigenvalue
of
aeIg:
tr
where the last step follows from (X(-)
Consider
tr
0:
By (4.3), the matrix V is symmetric positive definite and Diagonalize the symmetric
matrix
the diagonal entries of QV Q T must be \Theta(1). Therefore, the preceding
equation implies that the diagonal matrix   must have a nonpositive eigenvalue and that its diagonal
entries are of same order of magnitude. In other words, ae - 0 and O(jaej). This further
implies
By the definition of the central path, we have
Now using the fact that the above matrix is symmetric, it follows that
and therefore,
Using (4.3), we obtain
Combining this with (5.6) and using the fact that \Delta x (-) ? \Delta z (-), we have
Q.E.D.
Lemma 5.3 Suppose ffi(X; Z) - 1=2. Then there holds
Proof. Notice that
and
Now using
we have, by pre- and post-multiplying the above two equations with -
D \Gamma1=2 and rearranging terms,
Together with Lemma 5.2, this implies -
The lemma is proved.
Q.E.D.
Notice that
Lemma 5.4 We have
Proof. We have
Now using Lemma 5.3 and (4.5), we see that
It can be shown in an analogous way that
Q.E.D.
Now we are ready to bound the difference between \Delta -
Lemma 5.5 Suppose ffi(X; Z) - 1=2. We have
Proof. By definition of the predictor directions, we have
and
Combining these two relations yields
Now using Lemma 5.4 and using the fact that
we obtain fl
Z p ), the lemma follows from the above relation, after
applying Lemma 5.4 once more. Q.E.D.
Combining (5.5), Lemma 5.1 and Lemma 5.5 we can now estimate the order of
and hence, using (5.4), we can estimate the predictor step length t k .
Lemma 5.6 We have
Proof. Combining Lemma 5.5 with Lemma 5.1, we have
X a
Z a
so that, using (4.5), fl fl
X a
Z a
Moreover,
Z a )
X a
Applying (5.5), (5.7), (5.8) and (4.5) to the above relation yields
Q.E.D.
Theorem 5.2 The iterates (X k ; Z k ) generated by Algorithm SDP converge to (X a ; Z a ) superlinearly
with The duality gap - k converges to zero at the same rate.
Proof. From (5.4) we see that for any t - 0 satisfying
there holds
This implies using (4.8) and Lemma 5.6 that
so that
This shows that the duality gap converges to zero superlinearly with order 2=(1 It remains
to prove that the iterates converge to the analytic center with the same order. Notice that
However, using the definition of F-norm and applying Lemma 5.3,
Recall that L - k
definition, so that using Lemma 3.1,
Combining (5.9) and (5.10) with Lemma 5.2, we have
Hence, we obtain from Theorem 3.1 that
Similarly, it can be shown that
This shows that the iterates converge to the analytic center R-superlinearly, with the same order
as - k converges to zero. Q.E.D.
6 Conclusions
We have shown the global and superlinear convergence of the predictor-corrector algorithm SDP,
assuming only the existence of a strictly complementary solution pair. The local convergence analysis
is based on Theorem 3.1, which states that O(-). By enforcing
the iterates "inherit" this property of the central path. For the generalization of
the Mizuno-Todd-Ye predictor-corrector algorithm in [13], we do not enforce ffi(X
hence we cannot conclude superlinear convergence for it yet. In this respect, it will be interesting to
study the asymptotic behavior of the corrector steps. Finally, it is likely that our line of argument
can be applied to the infeasible primal-dual path following algorithms of Kojima-Shindoh-Hara [5]
and Potra-Sheng [12].



--R

"Interior point methods in semidefinite programming with applications to combinatorial optimization problems,"
"An interior-point method for semidefinite programming,"
"On approximate solutions of systems of linear inequalities"
"Global and local convergence of predictor-correct infeasible-interior-point algorithm for semidefinite programming,"
"Interior-point methods for the monotone linear complementarity problem in symmetric matrices,"
"An infeasible start predictor corrector method for semi-definite linear programming,"
"Pathways to the optimal solution set in linear programming,"
"On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming,"
"Primal-dual path following algorithms for semidefinite programming,"
"Limiting behavior of the derivatives of certain trajectories associated with a monotone horizontal linear complementarity problem,"
"Primal-dual interior-point methods for self-scaled cones,"
"A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming,"
"Symmetric primal-dual path following algorithms for semidefinite programming,"
"A primal-dual potential reduction method for problems involving matrix inequalities,"
"Semidefinite programming,"
"On quadratic and O( p nL) convergence of a predictor-corrector algorithm for LCP,"
"On extending primal-dual interior-point algorithms from linear programming to semidefinite programming,"
--TR
path following;central path;superlinear convergence;semidefinite programming