On the Local Convergence of a Predictor-Corrector Method for Semidefinite Programming.
We study the local convergence of a predictor-corrector algorithm for semidefinite programming problems based on the Monteiro--Zhang unified direction whose polynomial convergence was recently established by Monteiro. Under strict complementarity and nondegeneracy assumptions superlinear convergence with Q-order 1.5 is proved if the scaling matrices in the corrector step have bounded condition number. A version of the predictor-corrector algorithm enjoys quadratic convergence if the scaling matrices in both predictor and corrector steps have bounded condition numbers. The latter results apply in particular to algorithms using the Alizadeh--Haeberly--Overton (AHO) direction since there the scaling matrix is the identity matrix.
Introduction
The study of superlinear convergence of interior-point methods for linear programming (LP)
was initiated in the early 90s in an effort to explain the fact that interior point methods
tend to perform significantly better in practice than indicated by the polynomial complexity
bounds. This discrepancy is due to the limitation of the worst case analysis used in deriving
polynomial complexity bounds and reflects the inherent conflict between the requirements
of global convergence and fast local convergence. Superlinear convergence is especially important
for semidefinite programming (SDP) since no finite termination schemes exist for
such problems. As predicted by theory and confirmed by numerical experiments the condition
number of the linear systems defining the search directions increases as 1=-, where
- is the normalized duality gap, so that the respective systems become very ill conditioned
as we approach the solution. Therefore an interior point method that is not superlinearly
convergent is unlikely to obtain high accuracy in practice in spite of its theoretical "polyno-
mial complexity". On the other hand a superlinearly convergent interior point method will
achieve good accuracy (e.g. 10 \Gamma10 or better) in substantially fewer iterations than indicated
by its worse case global linear convergence rate that is related to polynomial complexity.
The local convergence analysis for interior point algorithms for SDP is much more challenging
than those for LP as shown by a relatively smaller number of papers addressing
this subject. The first two papers investigating superlinear convergence of interior point
algorithms were written independently by Kojima, Shida and Shindoh [4] and by Potra and
Sheng [13]. The algorithm investigated in these papers is an extension of Mizuno-Todd-
Ye predictor-corrector algorithm for LP and uses the KSH/HRVW/M search direction (see
the next section for a definition of this search direction). Kojima, Shida and Shindoh [4]
established the superlinear convergence under the following three assumptions:
(A) SDP has a strictly complementary solution;
nondegenerate in the sense that the Jacobian matrix of its KKT system is
(C) the iterates converge tangentially to the central path in the sense that the size of the
neighborhood containing the iterates must approach zero, namely,
lim
Here k:k F denotes the Frobenius norm of a matrix and "ffl" denotes the corresponding
scalar product (see the next section for precise definitions). In [13] we have not used assumptions
(B) and (C). Instead we proposed a sufficient condition for superlinear convergence that
is implied by the above assumptions. In [14] we improved this result and obtained superlinear
convergence under assumption (A) and the following condition:
(D) lim
which is clearly weaker than (C). Of course both (C) and (D) can be enforced by the al-
gorithm, but the practical efficiency of such an approach is questionable. However, from
a theoretical point of view it is proved in [14] that the modified algorithm in [4] that uses
several corrector steps in order to enforce (C) has polynomial complexity and is superlinearly
convergent under assumption (A) only. It is well known that assumption (A) is necessary for
superlinear convergence of standard interior point methods even in the QP case (see [10]).
Kojima, Shida and Shindoh [4] also gave an example suggesting that interior point algorithms
for SDP based on the KSH/HRVW/M search direction are unlikely to be superlinearly
convergent without imposing a condition like (C). In [5] the same authors showed that
a predictor-corrector algorithm using the AHO direction is quadratically convergent under
assumptions (A) and (B) (see the next section for a definition of the AHO search direction).
They also proved that the algorithm is globally convergent but no polynomial complexity
bounds have been found for this algorithm. It is shown that condition (C) is automatically
satisfied by the iteration sequence generated by the algorithm. It appears that the use of
the AHO direction in the corrector step has a strong effect on centering. We exploited this
property in [15] where we showed that a direct extension of Mizuno-Todd-Ye algorithm,
based on the KSH/HRVW/M direction in the predictor step and the AHO direction in the
corrector step, has polynomial complexity and is superlinearly convergent with Q-order 1:5
under assumptions (A) and (B).
An interesting superlinearly convergent predictor-corrector algorithm based on the NT
search direction was proposed by Luo, Sturm and Zhang [7]. The algorithm depends on a
parameter ffl ? 0. It produces points (X
is defined in (2.7), ffl=4. The
algorithm starts from a feasible point (X and for any given ~ ffl - ffl=4
finds a feasible point (X in at most O(
iterations. However
this bound on the number of iterations is not proved to hold for hence the
algorithm is not polynomial in the usual sense. The algorithm is superlinearly convergent
under assumption (A). It turns out that (C) is enforced by the algorithm since it is proved
in [7] that for sufficiently large k
It is also proved that if one uses one predictor and r correctors per iteration, then - k converges
to zero with Q-order 2=(1
In this paper we investigate the local behavior of the predictor-corrector algorithm considered
by Monteiro [9] for SDP using the MZ-family of search directions. We show that
the sufficient condition of Potra and Sheng [13] for superlinear convergence applies for this
algorithm. The sufficient condition is independent of scaling matrices. In particular we show
that the algorithm is superlinearly convergent if (A) and (D) are satisfied. More specifically,
we show that under the assumptions (A) and (B), superlinear convergence with Q-order
1.5 is obtained if the scaling matrices in the corrector step have bounded condition num-
ber. Finally, we propose a new version of the predictor-corrector algorithm which enjoys
quadratic convergence if the scaling matrices in both predictor and corrector steps have
bounded condition numbers and (A) and (B) are satisfied.
The following notation and terminology are used throughout the paper:
the p-dimensional Euclidean space;
nonnegative orthant of IR
the positive orthant of IR
the set of all p \Theta q matrices with real entries;
the set of all p \Theta p symmetric matrices;
: the set of all p \Theta p symmetric positive semidefinite matrices;
: the set of all p \Theta p symmetric positive matrices;
the (i; j)-th entry of a matrix M;
Tr(M the trace of a p \Theta p matrix, equals
0: M is positive semidefinite;
0: M is positive definite;
n: the eigenvalues of M 2 S
the largest, smallest, eigenvalue of M 2 S
Euclidean norm of a vector and the corresponding norm of a matrix, i.e.,
Frobenius norm of a matrix;
k(G;
G;
2 The predictor-corrector algorithm for SDP
We consider the semidefinite programming (SDP) problem:
and its associated dual problem:
are given data, and
are the primal and dual variables, respectively. By G ffl H we
denote the trace of (G T H). Also, for simplicity we assume that A i are linearly
independent.
Throughout this paper we assume that both (2.1) and (2.2) have finite solutions and
their optimal values are equal. Under this assumption, X   and (y   ; S   ) are solutions of (2.1)
and (2.2) if and only if they are solutions of the following nonlinear system:
We denote the feasible set of the problem (2.3) by
and its solution set by F   , i.e.,
We consider the symmetrization operator [17]
Since, as observed by Zhang [17],
for any nonsingular matrix P , any matrix M with real spectrum, and any - 2 IR, it follows
that for any given nonsingular matrix P , (2.3) is equivalent to
A perturbed Newton method applied to the system (2.4) leads to the following linear system:
m \Theta S n is the unknown search direction, - 2 [0; 1] is the centering
parameter, and is the normalized duality gap corresponding to (X;
The search direction obtained through (2.5) is called the Monteiro-Zhang (MZ) unified
direction [17, 11]. The matrix P used in (2.5) is called the scaling matrix for the search
direction. It is well known that taking I results in the Alizadeh-Haeberly-Overton
(AHO) search direction [1], corresponds to the Kojima-Shindoh-Hara/Helmberg-
Rendl-Vanderbei-Wolkowicz/Monteiro (KSH/HRVW/M) search direction [6, 3, 8], and the
case of P T coincides with the Nesterov-Todd (NT) search
direction [12]. Monteiro and Zhang [11] established the polynomiality of a long-step path-following
method based on search directions defined by scaling matrices belonging to the
class
such that
Following [11], Sheng et al. [16] proved the polynomiality of a Mizuno-Todd-Ye type
predictor-corrector algorithm for SDP by imposing the scaling matrices to be chosen from
the class
n\Thetan is nonsingular and PXSP
Moreover, its superlinear convergence was proved under an addtional simple condition. The
primal-dual algorithms considered by Monteiro [9] are based on the centrality measure
\Theta S n
1), we denote by
N (fl) the following neighborhood of the central path:
Monteiro's generalized predictor-corrector algorithm for semidefinite programming based on
the MZ family of directions consists of a predictor step and a corrector step at each iteration.
Starting from a strictly feasible pair (X generates a sequence of iterates
in N (ff). An iteration of Monteiro's generalized predictor-corrector algorithm
can be described as follows.
Algorithm
Given choose nonsingular n \Theta n matrices P k and P k
ffl Predictor Step. Solve the system (2.5) with (X;
Denote the solution (U;
m \Theta S n , and set
Compute the step length
ffl Corrector Step. Solve the system (2.5) with (X;
and be the solution, and set
End of iteration.
Using an elegant analysis, Monteiro [9] proved that the predictor-corrector algorithm
defined above with properly chosen parameters ff and fi (0 well defined and
that it needs at most O(
iterations for producing a pair (X
is the initial gap. More precisely, Monteiro showed that
for all k - 0.
3 Technical results
In analyzing the local behavior of the predictor-corrector algorithm of Monteiro, we need
the following technical result proved in [8, Lemma 2.6] and [9, Lemma 2.1(b)].
Lemma 3.1 Suppose that M 2 IR p\Thetap is a nonsingular matrix and E 2 IR p\Thetap has at least
one real eigenvalue. Then,
The following lemma is part of Lemma 3.5 of Monteiro [9].
Lemma 3.2 Let W 2 IR
n\Thetan be such that GWG \Gamma1 is skew-symmetric for some nonsingular
n\Thetan . Then,
The following technical result will play an important role in our analysis.
Lemma 3.3 Let (X;
1). Suppose that (D x ; \Deltay; D s
n\Thetan \Theta IR m \Theta S n\Thetan is a solution of the linear system:
\Deltay
for some K 2 IR n\Thetan . Then we have
F ,
where
Proof. By denoting
we can write
and
It is easily seen that -
and
Using the notation
it follows that
Using (3.8) and Lemma 3.2 with
On the other hand, using (3.8) again, we obtain
\GammakX \Gamma1=2 D x X \Gamma1=2 (X 1=2 SX
s
s
s
which implies (i). Then (ii) follows from (i), (3.9), and the fact that
It is interesting to note that the inequalities in the above lemma are independent of the
scaling matrix P . In the next lemma we establish a lower bound for the stepsize ' k , which
together with Lemma 3.3 enables us to analyze the asymptotic behavior of the predictor-corrector
algorithm.
be generated by the predictor-corrector algorithm.
Then
where
Proof. For simplicity, let us omit the index k. By (2.8), we have
which together with the linearity of H P (\Delta), the fact that T r[H P (M
and (2.5a) with imply that
Using the fact that U ffl
Therefore,
and
Hence, we have X(') - 0 and S(') - 0 for all ' 2 [0; -
']. Otherwise, there exists a ' 0 2 [0; -
such that X(' 0 )S(' 0 ) is singular, which means
On the other hand, (3.2) with implies that
which contradicts (3.10). Using (3.4) with
Therefore,
'. The result follows from the definition of '.
4 A sufficient condition for superlinear convergence
In this section we will investigate the asymptotic behavior of the predictor-corrector algorithm
and obtain a sufficient condition for superlinear convergence.
Definition 4.1 A triple (X   ; y   is called a strictly complementary solution of
Throughout the paper we assume that the following condition holds.
Assumption 1. The SDP problem has a strictly complementary solution (X
be an orthogonal matrix such that q are eigenvectors of X
and S   , and define
It is easily seen that IB [ ng. For simplicity, let us assume that
where   B and   N are diagonal matrices. Here and in the sequel, if we write a matrix M in
the block form
then we assume that the dimensions of M 11 and M 22 are jIBj \Theta jIBj and jINj \Theta jINj, respectively.
In the next lemma we use the following notation:
Lemma 4.2 (Potra-Sheng [13, Lemma 4.4]) Under Assumption 1 we have
ks
ks
Using Lemma 4.3, we can write
O(
O(
O(
Using the same techniques, we obtain a similar result for the predicted pair (X k
Lemma 4.3 Let X Assumption 1 is satisfied, then we have
O(
O(
O(
As in [13], let us define a linear manifold:
It is easily seen that if (X
Lemma 4.4 (Potra-Sheng [13, Lemma 4.5]) Under Assumption 1, F   ae M.
Lemma 4.5 (Potra-Sheng [13, Lemma 4.6]) Under Assumption 1, every accumulation point
of strictly complementary solution of (2.3).
Let us define
is the solution of the following minimization problem:
and \Gamma is a constant such that k(X k ; S k )k F - \Gamma; 8k. Note that every accumulation point of
belongs to the feasible set of the above minimization problem and the feasible
set is bounded. Therefore ( -
exists for each k.
Theorem 4.6 Under Assumption 1, if then the predictor-corrector
algorithm is superlinearly convergent. Moreover, if there exists a constant oe ? 0 such that
then the convergence has Q-order at least 1+oe in the sense that -
Proof. For simplicity, let us omit the index k. It is easily seen that (U
Here we have used the relation -
clearly satisfies the equation
Denoting
and applying (i) of Lemma 3.3, we obtain
which implies
Similarly,
By Lemma 4.3 and the fact that ( -
In a similar manner we obtain
Let us observe that
Then from (4.6), (4.7), (4.8), (4.9) and (4.10), we get
Hence, Applying (ii) of Lemma 3.3, we obtain
Noting that
we deduce
Finally, if
k ) for some constant oe ? 0, then we have
k ). From Lemma 3.4, it follows that
Therefore,
Lemma 4.6 was originally obtained by Potra and Sheng [14]. Based on Lemma 4.6, we
establish the following generalization of the result of Potra and Sheng [14, Theorem 6.1].
Theorem 4.7 Under Assumption 1, if X k S
!1, then the predictor-corrector
algorithm is superlinearly convergent. Moreover, if X k S
constant oe ? 0, then the convergence has Q-order at least 1 0:5g.
5 Superlinear convergence under strict complementarity
and nondegeneracy
Throughout this section, we will assume that Assumption 1 (strict complementarity) holds.
Let (X   ; y   ; S   ) be a strictly complementary solution of (2.1) and (2.2). We will also assume
the following nondegeneracy condition introduced by Kojima, Shida and Shindoh [4, 5].
First, let us define an affine space G 0 by
Assumption 2. (Nondegeneracy) If X
As remarked in Section 5 of Kojima, Shida and Shindoh [5], under the strict complementarity
assumption, the above nondegeneracy condition is equivalent to the combination of
primal and dual nondegeneracy conditions given by Alizadeh, Haeberly and Overton [2].
Under Assumptions 1 and 2, the solution (X   ; S   ) is unique. Therefore the iteration
sequence
converges to (X   ; S   ) and so does the sequence of predicted pairs
Lemma 5.1 (Kojima-Shida-Shindoh [5], Lemma 5.3) Assume that
H I (US   +X   V
Let R be a nonsingular matrix and
~
(R
It is easily seen that the R-scaled SDP
~
~
also satisfies the strict complementarity and nondegeneracy conditions. Its unique solution
is (RX   R T (R
Using Lemma 5.1 and considering the new SDP (5.1), we can easily obtain the following
lemma.
Lemma 5.2 Assume that for some nonsingular matrix R,
In the next lemma cond F denotes the condition number of a matrix B.
Lemma 5.3 If cond F (P k
Proof. Let R
the corrector step of the algorithm, we have
U
it is easily seen that
Suppose (5.2) is not true, i.e., the sequence
is unbounded. Then we can
choose a subsequence such that
(R
and
Obviously, (U . The fact that the matrices A are linearly indepen-
dent, together with (U implies that (U Dividing both sides of (5.3) by
letting k !1 along a subsequence, we obtain
which contradicts Lemma 5.2.
Theorem 5.4 Under the strict complementarity and nondegeneracy assumptions, if cond F (P k
O(1), then the algorithm is superlinearly convergent with Q-order at least 1.5.
Proof. At the predictor step, we have
Thus,
Then, by Lemma 5.3, we obtain
Note that
F
F
Therefore,
which ends the proof by invoking Theorem 4.7.
The above result says that the superlinear convergence of the predictor-corrector algorithm
is independent of the choice of the scaling matrix P k in the predictor step of the
algorithm, while the scaling matrices used in the corrector step need to be "well-conditioned"
for superlinear convergence. Clearly, the family of scaling matrices admissible in the corrector
step for superlinear convergence includes the identity matrix defining the AHO as a
special case. By imposing the same assumption on the scaling matrices used in the predictor
step and a new strategy for the step size, we can improve the order of convergence stated in
Theorem 5.4.
In order to achieve quadratic convergence we need to slightly modify the choice of the
step size. Instead of ' k given by (2.9), we will use:
The predictor-corrector algorithm with this new strategy will be called the modified predictor-corrector
algorithm. It is easily seen that the modified predictor-corrector algorithm still has
polynomial complexity. In what follows we will show that it is also quadratically convergent.
Theorem 5.5 Under the hypothesis of Theorem 5.4, if cond F (P k then the modified
predictor-corrector algorithm is quadratically convergent.
Proof. From the proof of Theorem 5.4 (cf. (5.5)), we have
Using (5.7) and an argument similar to that employed in the proof of Lemma 5.3 we get
Then we can write
g. As in (5.4)-(5.5), we can prove that
Using (5.9) and the same argument as in Lemma 5.3, we get
Observing that
we have
where C 2 is a positive constant. Without loss of generality, we may assume
which, together with (5.6) and (5.13), implies that
and
Let
Evidently,
k ], we have
This means
Therefore
and -
6 Remarks
In this paper we only consider the feasible version of the predictor-corrector method to
keep the presentation simple. However, the analysis used here can be easily extended to the
infeasible predictor-corrector algorithms based on the unified direction proposed by Monteiro
and Zhang. Under the strict complementarity and nondegeneracy assumptions we have
established the superlinear convergence with Q-order 1.5 of the "pure" predictor-corrector
algorithm if the scaling matrices for the corrector step satisfy cond F (P k
superlinear convergence can be obtained under a weaker condition is an interesting topic
for future research. Finally, we mention that quadratic convergence is established for the
predictor-corrector algorithm with a slight modification of the step size selection. It would
be interesting to find out whether quadratic convergence can be proved for the "original"
predictor-corrector algorithm.



--R


Complementarity and nondegeneracy in semidefinite programming.
An interior-point method for semidefinite programming
Local convergence of predictor-corrector infeasiblee-interior-point algorithms for semidefinite programs
A predictor-corrector interior-point algorithm for the semidefinite linear complementarity problem using the Alizadeh-Haeberly-Overton search direction

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
Local convergence of interior-point algorithms for degenerate monotone LCP
A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming

A superlinearly convergent primal-dual infeasible-interior- point algorithm for semidefinite programming
Superlinear convergence of interior-point algorithms for semidefinite programming
Superlinear convergence of a predictor-corrector method for semidefinite programming without shrinking central path neighborhood
On a general class of interior-point algorithms for semidefinite programming with polynomial complexity and superlinear convergence
On extending primal-dual interior-point algorithms from linear programming to semidefinite programming
--TR

--CTR
Y. B. Zhao, Enlarging neighborhoods of interior-point algorithms for linear programming via least values of proximity measure functions, Applied Numerical Mathematics, v.57 n.9, p.1033-1049, September, 2007
interior point method;superlinear convergence;semidefinite programming