Primal-Dual Affine-Scaling Algorithms Fail for Semidefinite Programming.
In this paper, we give an example of a semidefinite programming problem in which primal-dual affine-scaling algorithms using the HRVW/KSH/M, MT, and AHO directions fail. We prove that each of these algorithms can generate a sequence converging to a non-optimal solution and that, for the AHO direction, even its associated continuous trajectory can converge to a non-optimal point. In contra st with these directions, we show that the primal-dual affine-scaling algorithm using the NT direction for the same semidefinite programming problem always generates a sequence converging to the optimal solution. Both primal and dual problems have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and are nondegenerate everywhere.
INTRODUCTION
We consider the standard form semidefinite programming (SDP) problem:
minimize C . X
subject to A i .
and its dual:
subject to Z
where C, X, A i belong to the space S(n) of n - n real symmetric matrices, the operator
. denotes the standard inner product in S(n), i.e., C . X := tr(CX
means that X is positive semidefinite.
SDP bears a remarkable resemblance to LP. In fact, it is known that several interior-point
methods for LP and their polynomial convergence analysis can be naturally extended
to SDP (see Alizadeh [1], Jarre [15], Nesterov and Nemirovskii [28, 29], Vandenberghe
and Boyd [38]). However, in extending primal-dual interior-point methods from LP to
certain choices have to be made and the resulting search direction depends on these
Date. March 4, 1998.
1991 Mathematics Subject Classification. Primary 60E05, Secondary 60C05.
Key words and phrases. Semidefinite Programming, Primal-dual Interior-Point Method, Affine-Scaling Al-
gorithm, Global Convergence Analysis.
research partially supported by the NSF through grant CCR94-03789.
choices. As a result, there can be several search directions for SDP corresponding to a
single search direction for LP.
This paper deals with primal-dual interior-point algorithms for SDP based on the following
four search directions:
(i) HRVW/KSH/M direction,
(ii) MT direction,
(iii) AHO direction,
(iv) NT direction.
We study a specific simple SDP problem, and for this problem carefully investigate the behavior
of the sequence generated by the interior-point methods using these four directions
to show how the convergence property of the algorithm varies depending on the choice of
direction.
There are two popular classes of interior-point methods: affine-scaling algorithm and
path-followingalgorithm. Path-following algorithm is characterized by a parametric relaxation
of the following optimality conditions for SDP:
A i .
is a barrier parameter. In such algorithm, it is necessary to specify a specific
choice of - at any iteration. The particulars vary from paper to paper, and we therefore
omit them here. When - # 0 the corresponding method is called affine-scaling algorithm.
Most of the existing SDP literature considers path-following algorithm. In this paper, we
restrict our attention to affine-scaling algorithm.
The affine-scaling algorithm was originally proposed for LP by Dikin [8], and independently
rediscovered by Barnes [5], Vanderbei, Meketon and Freedman [39] and others,
after Karmarkar [16] proposed the first polynomial-time interior-point method. Though
polynomial-time complexity has not been proved yet for this algorithm, global convergence
using so-called long steps was proved by Tsuchiya and Muramatsu [37]. This algorithm
is often called the primal (or dual) affine-scaling algorithm because the algorithm is based
on the primal (or dual) problem only. There is also a notion of primal-dual affine-scaling
algorithm. In fact, for LP, there are two different types of primal-dual affine-scaling algorithm
proposed to date; one by Monteiro, Adler and Resende [23], and the other by Jansen,
Roos, and Terlaky [14]. The latter is sometimes called the Dikin-type primal-dual affine-
scaling algorithm. Both of these papers provide a proof of polynomial-time convergence
for the respective algorithm, though the complexity of the former algorithm is much worse
than the latter.
All of the affine-scaling algorithms just described can be naturally extended to SDP.
Faybusovich [9, 10] dealt with the SDP extension of the primal affine-scaling algorithm.
Global convergence of the associated continuous trajectory was proved by Goldfarb and
Scheinberg [12]. However, Muramatsu [27] gave an example for which the algorithm
fails to converge to an optimal solution for any step size, showing that the primal affine-
scaling algorithm for SDP does not have the same global convergence property that one
has for LP. For both primal-dual affine-scaling algorithms, de Klerk, Roos and
proved polynomial-time convergence. However, as was mentioned before, there exist
several different search directions in primal-dual interior-point methods for SDP, and each
of the primal-dual affine-scaling algorithms studied by de Klerk, Roos and Terlaky was
based on a certain specific choice of search direction. Below we discuss in detail how the
various search directions arise.
The primal-dual affine-scaling direction proposed by Monteiro, Adler and Resende [23]
is the Newton direction for the set of optimality conditions, i.e., primal feasibility, dual
feasibility and complementarity. For SDP, the optimality conditions are (3), (4) and
A direct application of Newton's method produces the following equations for #X , #u and
#Z (throughout this paper, we assume that the current point is primal and dual feasible):
A i .
However, due to (9), the solution of this system does not give a symmetric solution in
general (actually #Z must be symmetric by (8) but #X is generally not symmetric). To
date, several ways have been proposed to overcome this difficulty, each producing different
directions in general.
In this paper, we study a specific simple SDP problem, and for this problem carefully
investigate the behavior of the sequence generated by the primal-dual affine-scaling algorithms
using these four directions to show how the convergence property of the algorithm
varies depending on the choice of direction.
Now we describe the four directions we deal with in this paper. Note that the papers
mentioned below deal exclusively with path-following algorithms, for which the corresponding
affine-scaling algorithms can be derived by setting
1.1. The HRVW/KSH/M Direction. This direction is derived by using (7)-(9) as is, and
then taking the symmetric part of the resulting #X . This method to make a symmetric direction
was independently proposed by Helmberg, Rendl, Vanderbei and Wolkowicz [13],
Kojima, Shindoh and Hara [18], and Monteiro [21]. Polynomial-time convergence was
proved for the path-following algorithms using this direction. For related work, see also the
papers of Lin and Saigal [19], Potra and Sheng [32], and Zhang [40]. The HRVW/KSH/M
direction is currently very popular for practical implementation because of its computational
simplicity. Almost all SDP solvers have an option to use this direction, and some
serious solvers (for example, Borchers [6] and Fujisawa and Kojima [11]) use this direction
only.
1.2. The MT Direction. Monteiro and Tsuchiya [24] apply Newton's method to the system
obtained from (3)-(6) by replacing (6) with
The resulting direction is guaranteed to be symmetric. It is the solution of (7), (8) and
4 MASAKAZU MURAMATSU AND ROBERT J. VANDERBEI
is an auxiliary variable. They proved polynomial-time convergence of
the path-following algorithm using this direction. Recently, Monteiro and Zanjacomo [25]
discussed a computational aspects of this direction, and gave some numerical experiments.
1.3. The AHO Direction. Alizadeh, Haeberly, and Overton [2] proposed symmetrizing
equation (6) by rewriting it as
and then applying Newton's method to (3), (4) and (12). The resulting direction is a solution
of (7), (8) and
Several convergence properties including polynomial-time convergence are known for the
path-following algorithm using the AHO direction. See for example the work of Kojima,
Shida and Shindoh [17], Monteiro [22], and Tseng [36]. The AHO direction however, is
not necessarily well-defined on the feasible region as observed by Shida, Shindoh and Kojima
[33]; the linear system (7), (8), and (13) can be inconsistent for some problems.
In fact, a specific example was given by Todd, Toh and T-ut-unc-u [35]. On the other
hand, Alizadeh, Haeberly, and Overton [4] report that the path-following algorithm using
the AHO direction has empirically better convergence properties than the one using
the HRVW/KSH/M direction.
1.4. The NT Direction. Nesterov and Todd [30, 31] proposed primal-dual algorithms for
more general convex programming than SDP, which includes SDP as a special case. Their
search direction naturally produces a symmetric direction. The direction is the solution of
(7), (8) and
where D # S(n) is a unique solution of
Polynomial-time convergence of the corresponding path-following algorithm was proved
in their original paper [30]. Also, see the works of Monteiro and Zhang [26], Luo, Sturm
and Zhang [20], and Sturm and Zhang [34] for some convergence properties of the algorithms
using the NT direction. The primal-dual affine-scaling algorithm studied by de
Klerk, Roos and Terlaky [7] was based on this direction. As for numerical computation,
Todd, Toh and T-ut-unc-u [35] reported that the path-following algorithm using the NT direction
is more robust than algorithms based on the HRVW/KSH/M and AHO directions.
1.5. Notation and Organization. The rest of this paper is organized as follows. In Section
2, we introduce the specific SDP problem we wish to study.
Section 3, deals with the HRVW/KSH/M direction. We consider the long-step primal-dual
affine-scaling algorithm. One iteration of the long-step algorithm using search direction
(#X,#u,#Z ) is as follows:
#X,
# is defined by
where
#D := sup { # | Z
and # is a fixed constant less than 1. We prove that, for any fixed #, there exists a region
of initial points such that the long-step primal-dual affine-scaling algorithm using the
HRVW/KSH/M direction converges to a non-optimal point.
In Section 4, we prove the same statement as above for the MT direction by showing
that the MT direction is identical to the HRVW/KSH/M direction for our example.
In Section 5, we deal with the AHO direction. We consider the continuous trajectory
which is a solution of the following autonomous differential equation:
We prove that the continuous trajectory of the AHO direction can converge to a non-optimal
point.
In Section 6, we show that the long-step primal-dual affine-scaling algorithm using the
direction generates a sequence converging to the optimal solution for any choice of #.
Note that this result does not mean the global convergence property of the algorithm, but a
robust convergence property for the specific problem, for which the other three algorithms
can fail to get its optimal solution.
Section 7 provides some concluding remarks.
Note that each section is fairly independent of the others and we use the same symbol
(#X,#u,#Z ) for different directions; e.g., #X in Section 3 refers to the HRVW/KSH/M
direction, while in Section 5, it's the AHO direction.
2. THE SDP EXAMPLE
The primal-dual pair of SDP problem we deal with in this paper is as follows:
subject to  0 1
maximize 2u
subject to Z
where X, Z # S(2) and u # R. The equality condition of the primal (20) says that the
off-diagonal elements of X must be 1 for X to be feasible. Thus, putting
and noting that X # 0 # x # 0, y # 0, x y # 1, we see that problem (20) is equivalent to
subject to x # 0, y # 0, x y # 1, (23)
whose optimal solution is
6 MASAKAZU MURAMATSU AND ROBERT J. VANDERBEI
Similarly, from the equality condition of the dual (21), we see that Z can be written as
follows:
and that the dual is equivalent to the following linear program:
maximize 2u
subject to
whose optimal solution is obviously
Since we assume that the current point is primal and dual feasible in this paper, we see
from (22) and (24) that each of the search directions has the following form:
In the following, we put
F := { (x, y, u) | x y # 1, x > 0, y > 0,
We see that X and Z with (22) and (24) are feasible if and only if (x, y, u) # F , thus F is
called primal-dual feasible region. We also define the interior of the feasible region:
{ (x, y, u) | x y > 1, x > 0, y > 0,
Obviously, if (x, y, u) # F then the corresponding X and Z are feasible and positive
definite.
It is easy to see that
is the unique optimal solutions of (23) and (25), hence
is the unique optimal solutions of (20) and (21). It can also be easily seen that the optimal
values of (20) and (21) coincide, that the optimal solutions satisfy strict complementarity,
and that the problems are nondegenerate (see Muramatsu [27]; for degeneracy in SDP, see
Alizadeh, Haeberly, and Overton [3]). In fact, this example problem was first proposed in
Muramatsu [27] to prove that the primal affine-scaling algorithm fails.
3. THE HRVW/KSH/M DIRECTION
In this section, we consider the long-step primal-dual affine-scaling algorithm using the
HRVW/KSH/M direction. To calculate the HRVW/KSH/M direction (#X,#u,#Z ) at a
feasible point (X, u, Z ), we first solve the following system:
From (27) and (28), we see that
d
#X and #Z have the following form:
d
Note that since we apply the HRVW/KSH/M-type method, we do not assume that
d
#X is
symmetric here. Then we symmetrize
d
d
#x #w
#w #y
.
Therefore, #X is independent of #w.
The third equation, (29), can be written componentwise as:
y.
Solving these linear equalities, we have
There is also an equation for #w but we don't write it since it disappears after symmetrization

Figure

1 shows the vector field (#x, #y) on the primal feasible region with
In fact, since (#x, #y) is independent of u after normalization, u can be arbitrary. From
this figure, we can see that when x is tangential to the boundary of the
primal feasible region, and that its length is not 0 unless the current point is optimal. In the
following, we will see that the primal discrete sequence (x, y) can be trapped in the curved
while u remains negative.
Letting the step length -
#(x, y, u) absorb the common factor, we can write one iteration
of the primal-dual affine-scaling algorithm in terms of (x, y, u) as follows:
#(x, y, u)(2 - x y
#(x, y, u)(2 - x y
#(x, y, u)(1 -
where # is a fixed fraction less than 1 and -
#(x, y, u) is defined by (16). Here, we emphasize
the fact that -
#, which is originally a function of (X, u, Z ), can be regarded as a function
of (x, y, u) due to the correspondence (22) and (24). In fact, we identify (x, y, u) and
(X, u, Z ) in the following.
Now we consider the set
G := { (x, y, u) # F | u
and investigate the property of the iteration sequence starting in this region. In fact, our
aim in this section is to prove the following theorem:
8 MASAKAZU MURAMATSU AND ROBERT J. VANDERBEI
x
y


1. Vector Field of the HRVW/KSH/M method
Theorem 1. Let for any 2/3 # < 1,
{ (x, y, u) # G | x
If, for the HRVW/KSH/M primal-dual affine-scaling algorithm (34), (35) and (36), we
choose the initial point
then the limit point is contained in the closure of G # .
Since the closure of G # does not contain the optimal solution, this theorem implies that the
sequence converges to a non-optimal point.
Note also that the condition (38) can be satisfied for all # and #. In fact, fixing x 0 < 1-#
and u 0 < 0, we can reduce the left hand side arbitrarily by choosing y 0 close to 1/x 0 .
We first show that -
# P on G.
Lemma 2. If (x, y, u) # G, then -
#(x, y, u) is a positive solution of
where
on G.
Proof. Noting that 2(1 - on the interior feasible region, we have
on G.
For the primal problem (20), since x hold when x is the
solution of x namely,
Expanding this quadratic equation and dividing by x y - 1, we have
Now we have (40) as
on G. Since the coefficient of # 2
P and the constant of (41) have the opposite signs, this quadratic
equation has one positive solution and one negative, and # P is the positive solution.
From (41), it follows that
from which we have
Therefore, we have -
which is the solution of (41).
The following two lemmas are used to prove that the sum of -
# k is bounded, which is
essential for the proof of the theorem.
Lemma 3. We have
#(x, y, u) # 1/ p R(x, y)
on G.
Proof. It follows from Lemma 2 that
#(x, y, u) 2
#(x, y, u)
R(x, y) #R(x, y) .
Thus we have
#(x, y, u) # 1/ p R(x, y).
Lemma 4. Assume that we do one iteration of the primal-dual affine-scaling algorithm
and (36)) from (x, y, u) # G to get fraction #. Then we have
Proof. The lemma can be seen as follows:
#(x, y, u)(x
#(x, y, u) 2
#(x, y, u)(x
#(x, y, u)(x
#(x, y, u)(x
Lemma 5. Assume that the sequence { generated by (34),
(35) and (36) is contained in G. Then we have
Proof. We have
(by Lemma
Now we are ready to prove the theorem.
Proof of Theorem 1. We show that if (x l , y l , , from
which the theorem follows by induction. We have
l
l
(by Lemma 5)
which implies
Similarly, we have
l
l
(by Lemma 5)
which implies
From Lemma 4, x l+1 y l+1
# 3/2 follows. The relation x l+1 y l+1 > 1 is obvious
due to the choice of the step-size. Also x l+1
from which we have x l+1
+y l+1
# 3. Therefore,
the proof.
Remark: By replacing 3/2 with in the definition (37) of G, the
same analysis provides an initial point arbitrary close to the primal optimal solution but for
which convergence is to a non-optimal point.
4. THE MT DIRECTION
We will show in this section that the MT direction applied with the primal and dual
interchanged is identical to the HRVW/KSH/M direction for our primal-dual pair of SDP
problems (20) and (21). As is well-known, we can transform the standard form SDP problem
to the dual form and vice versa to get the following primal-dual pair # -
P# of SDP
problems:
subject to  1 0
maximize -x - y
subject to X - x  1 0
which is equivalent to #D# and #P#. In fact, the feasible solutions for # -
P# and # -
D# are
again given by (22) and (24) where (x, y, u) # F .
According to (7), (8), (10) and (11), the MT direction (#X,#x,#y,#Z ) for this
primal-dual pair at a feasible solution (X, x, y, Z ) is the solution of
equivalently, (26) and (47) and (48). The following lemma shows that
the MT direction is the same as the HRVW/KSH/M direction in our problem.
Lemma 6. For (X, Z ) satisfying (22) and (24) with (x, y, u) # F o , the system (47), (48)
and (26) has a unique solution (#X M , #Z M , VM ). Let (
d
be the
solution of (26), (29), and (30) for the same (X, Z ). Then we have #X
Proof. From (29) and (30), it is easy to see that #X H is a unique solution of
We prove the lemma by showing that (47) and (48) are equivalent to (49) in our case.
In view of (24), we can write
Z 1/2
sin # cos #
,
Putting
we have
.
Due to (48) and (26), the diagonal components of V Z 1/2 must be 0, i.e.,
Therefore, we have which implies that V Z 1/2 is symmetric.
Now we have
from which
Substituting these relations into (47), we have
Obviously, (#X M , #Z M ) is a solution of this system. Multiplying this equation by Z -1/2
from the right and left, we have (49). Since the solution of (26) and (49) is unique, the MT
direction is unique and identical to the HRVW/KSH/M direction.
The following theorem is immediate by Lemma 6.
Theorem 7. Let for any 2/3 # < 1,
{ (x, y, u) # G | x
For the long-step primal-dual affine-scaling algorithm using the MT direction, if, given a
step-size parameter #, we choose the initial point
then the limit point is contained in the closure of G # .
5. THE AHO DIRECTION
We deal with the continuous trajectories of the AHO directions on our problem in this
section. Let us denote the AHO direction by (#X,#u,#Z ). The system for the direction
is (27), (28), and (13), or equivalently, (26) and (13). The third equation, (13), can be
written componentwise as follows:
Solving these linear equalities, we have

Figure

2 shows the vector field (#x, #y) on the primal feasible region with
and In contrast with the HRVW/KSH/M direction case, the vector field drastically
changes depending on u. Namely, when is near the boundary of the
primal feasible region, the direction is not nearly tangential to the boundary, aiming at
somewhere outside of the feasible region. On the other hand when the direction
aims inside. The former observation leads to the convergence of the continuous trajectories
of the AHO direction to a non-optimal point (Theorem 9).
We deal with the trajectory (17), (18) and (19) in the space of (x, y, u) by using the one-
to-one correspondence (22) and (24). Furthermore, since the trajectory is not changed if we
multiply each right-hand side by a common positive factor, we can multiply by x
which is greater than 0, to get
The equation (55) can be easily solved as follows:
14 MASAKAZU MURAMATSU AND ROBERT J. VANDERBEI
x
y
x
y


2. Vector Fields of the AHO method
where u 0 is the initial value of u t .
The following properties of the vector field can easily be observed.
Lemma 8. We have
Proof. We omit subscript t in this proof for simplicity. The former equation can be seen
as:
The latter equation can be seen as:
Now we restrict our attention to the set
H := { (x, y, u) # F | u # -1/2, y # 16x } . (60)
We then introduce the following change of variables:
y, (61)
# =2 log y
x . (62)
The inverse mapping is:
re -# ,
re # .
Putting
#(x, y, u) := (r, #, u),
we can easily see that
Now consider the trajectory in the new coordinate system:
starting from (r 0 , # 0 ,
We use ( -
y, -
u), (-r , -
#, -
y, -
u), (-r , -
#, -
u) for
respectively, for notational simplicity.
We will prove the following theorem in this section:
Theorem 9. Let the initial point
denote the corresponding point in #(H). If
then
The following lemma elucidates the behavior of the continuous trajectories on #(H)
Lemma 10. For
t , we have
Proof. It follows from (61) and (62) that
. (67)
We have from (66) that
d
< -4 (Since y - x > 3 and u # 1/2 on H).
Therefore, we have
The second assertion of the lemma can be easily derived from (59) and (67), since x-y < 0
Now we prove the theorem.
Proof of Theorem 9. Obviously, if -
# > log 4, and -
then the solution
cannot be extended in the feasible region any more, i.e., -
t. Since -
follows from (65), we will show that -
in the following.
we have from (64) that t must satisfy
In other words, we have
log
. (68)
On the other hand, in view of (56), we have
log
Therefore, from (68), we have -
u < -1/2, and since (-r , -
u) is at the boundary of #(H),
we have r -
6. THE NT DIRECTION
In this section, we prove that the long-step primal-dual affine-scaling algorithm using
the NT direction generates a sequence converging to an optimal point for our SDP problem.
We denote the NT direction by (#X,#u, dZ ). To calculate the NT direction, we first
calculate the scaling matrix D. From (22), (24) and (15), we see that
where
# (x, y,
#(x, y,
Solving (7), (8) and (14) with (69), we have
where
#(x, y,
The figure 3 shows the vector fields (#x, #y) on the primal feasible region with
-0.5 and Note that the direction depends on u like the AHO direction does, but
the length of the direction differs from that of the AHO direction; the length of the direction
becomes small if (x, y) is close to the boundary, and in fact, it vanishes at the boundary.
Now imagine that a discrete sequence generated by the primal-dual affine-scaling algorithm
using the NT direction approaches the boundary { (x, y, u) # F | x
saying, the movement in the (x, y) space becomes small if x y is close to 1, and
instead u is improved so much that u converges to 1, which is the optimal solution. Then
the primal direction (#x, #y) aims inside the feasible region, and the stagnation ends.
The following is what we prove in this section.
Theorem 11. For any step-size parameter 0 < # < 1, and any initial point
the sequence generated by the long-step primal-dual affine-scaling algorithm for the primal-dual
pair of SDP problems (20) and (21) using the NT direction converges to the optimal
point.
x
y
x
y


3. Vector Fields of the NT method
First, we observe that the duality gap X . monotonically decreasing.
Lemma 12. We have
or equivalently,
This is a standard calculation, thus we omit the proof. Note that if the duality gap does
not converge to 0, then Q # k=1 (1 -
# 0. On the other hand, if
# 0, then, since the optimal solution is unique, the sequence
converges to the optimal solution (1, 1, 1). We use these relations in the following extensively

Next lemma shows that the sequence converges, and the search direction is
bounded along the sequence.
Lemma 13. We have
Proof. From (77), #u k > 0 follows. Since {u k
} is an increasing sequence and bounded by
1, the limit u # exists.
We have from Lemma 12 that
which implies that
By definition (78), we have
Therefore, since
for some positive constant M. We see in the same way that #y k is bounded, and, from
(79), that #u k is also bounded.
If x k
# 0, obviously the sequence converges to the optimal solution.
Therefore, we deal with the case that x k
that there exists some # > 0 such that
Y
Taking logarithm of the both sides, we have
log #
log(1 -
Using this inequality, we have
l
| #
l
| # -M log #
for all l, which implies that {x k
} is a Cauchy sequence. Thus {x k
} converges. The convergence
of {y k
} can be shown in the same way.
Using the lemma above, we prove that the dual iterates converges to its optimal.
Lemma 14. We have u k
# 1.
Proof. Let us assume that u # < 1. Since cannot be an interior point, we
have x k y k
# 1.
If -
occurs infinitely many times, then obviously u k
# 1, which contradicts the
assumption. Thus we can assume that # k
# k for sufficiently large k and that # k
On the other hand, we have
Therefore, # k
Since #u k is bounded, we have # k
# 0, which implies that the left hand side of (80)
converges to 1 - while the right hand side is 0. This is a contradiction, and we
have
Now we know that u k
# 1, and converging. We will prove
(1, 1) in the following. To show this, we first show that the limit point is on the boundary
of the primal feasible region.
Lemma 15. We have x # y
Proof. Assume that x # y 1. In this case, we have # k
# 2 from
definitions (71) and (78), and also -
# 0 from Lemma 12. Since
we see that # k
# k for sufficiently large k and that # k
For
P , we have
Therefore, -
However, since are bounded, the left hand side of (81) goes to
while the right hand side is 0. This is a contradiction, and we have
The following relation can be seen by a straightforward calculation.
Lemma 16. We have
#(x, y, u),
#(x, y, u) # 0 when x y # 1 and u # 1.
Proof. We have
Therefore, putting
#(x, y, u) := -4(1 -
we have the lemma.
Now we are ready to prove that the optimality of (x # , y # ). Obviously, this lemma
together with Lemma 17 proves Theorem 11.
Lemma 17. We have
Proof. It can be seen that
We claim that # k #x k #y k is bounded. Assume by contradiction, # k #x k #y k is not
bounded. Then we can take a diverging subsequence, i.e., there exists a subsequence L #
{0, 1, 2, . } such that lim k#L # k
| #. Since #x k and #y k are bounded, we
have lim k#L # k
#, and from the definition of # k , lim k#L # k
#, too. Therefore this
is a contradiction because, for k # L ,
(y k
22 MASAKAZU MURAMATSU AND ROBERT J. VANDERBEI
Assume that implies that -
14, 15, and 16, we have that
for sufficiently large k, while, since # k #x k #y k is bounded and -
Therefore,
holds for sufficiently large k. This and (82) imply that
is increasing for sufficiently large k. This contradicts the fact that x k y k
# 1.
Therefore, we have
7. CONCLUDING REMARKS
The practical success of interior-point methods for LP relies heavily on the ability to
take the long steps, i.e., stepping a fixed fraction of the way to the boundary for the next
iterate. Even when convergence has not been proved, it is necessary in practice to take
such a long step. For LP, these long steps are very successful, and every implementation
uses bold step-length parameters.
These bold choices of step-length parameters are supported by the robustness of the
primal-dual affine-scaling algorithm (not the Dikin-type variant). It is known that the continuous
trajectories associated with the primal-dual affine-scaling algorithm converge to
the optimal solution, and there is no evidence so far that the long-step primal-dual affine-
scaling algorithm fails to find the optimal solution.
However in SDP, the situation is different; even a continuous trajectory can converge
to a non-optimal point. The results of this paper suggest that, for finding the optimal
solution, such bold steps as are taken in the LP case should not be taken at least for the
HRVW/KSH/M, MT and AHO directions; otherwise, jamming may occur.
It seems that the algorithm corresponding to the NT direction is more robust than those
corresponding to the other directions. The same observation was reported by Todd, Toh
and T-ut-unc-u [35].

ACKNOWLEDGEMENTS

We thank Professor Michael Overton of New York University for showing us the bad
local behavior of the HRVW/KSH/M method, which motivated us to do this research. We
also thank Dr. Masayuki Shida of Kanagawa University for many stimulating discussions
which inspired us to develop the results for the AHO direction, and kindly pointing out that
the MT direction is identical to the HRVW/KSH/M direction in our example.



--R

Interior point methods in semidefinite programming with application to combinatorial opti- mization

Complementarity and nondegeneracy in semidefinite programming.

A variation on Karmarkar's algorithm for solving linear programming problems.
CSDP, a C library for semidefinite programming.
Polynomial primal-dual affine scaling algorithms in semidefinite programming
Iterative solution of problems of linear and quadratic programming.
Dikin's algorithm for matrix linear programming problems.
On a matrix generalization of affine-scaling vector fields

Interior point trajectories in semidefinite programming.
An interior point method for semidefinite pro- gramming
A polynomial primal-dual dikin-type algorithm for linear program- ming
An interior-point method for minimizing the maximum eigenvalue of a linear combination of ma- trices
A new polynomial time algorithm for linear programming.
A predictor-correctoe interior-point algorithm for the semidefinite linear complementarity problem using Alizadeh-Haeberly-Overtonsearch direction
Interior point methods for the monotone semidefinite linear complementarity problem in symmetric matrices.
A predictor-corrector method for semi-definite programming
Superlinear convergence of a symmetric primal-dual path-following algorithms for semidefinite programming

Polynomial convergence of primal-dual algorithms for semidefinite programming based on Monteriro and Zhang family of directions
A polynomial-time primal-dual affine scaling algorithm for linear and convexquadratic programming and its power series extension
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
Affine scaling algorithm fails for semidefinite programming.
Optimization over positive semidefinite matrices: Mathematical background and user's manual.
Interior Point Polynomial Methods in Convex Programming


A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming
Existence of search directions in interior-point algorithms for the sdp and the monotone SDLCP
Symmetric primal-dual path-following algorithms for semidefinite programming

Analysis of infeasible path-following methods using the Alizadeh-Haeberly-Overton direction for the monotone semidefinite lcp
Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems

A modification of Karmarkar's linear programming algorithm.
On extending primal-dual interior-point algorithms from linear programming to semidefinite pro- gramming
--TR
affine-scaling algorithm;global convergence;primal-dual interior-point method;semidefinite programming