A Superlinearly Convergent Primal-Dual Infeasible-Interior-Point Algorithm for Semidefinite Programming.
A primal-dual infeasible-interior-point path-following algorithm is proposed for solving semidefinite programming (SDP) problems. If the problem has a solution, then the algorithm is globally convergent. If the starting point is feasible or close to being feasible, the algorithm finds an optimal solution in at most $O(\sqrt{n}L)$ iterations, where n is the size of the problem and L is the logarithm of the ratio of the initial error and the tolerance. If the starting point is large enough, then the algorithm terminates in at most O(nL) steps either by finding a solution or by determining that the primal-dual problem has no solution of norm less than a given number. Moreover, we propose a sufficient condition for the superlinear convergence of the algorithm. In addition, we give two special cases of SDP for which the algorithm is quadratically convergent.
Introduction
In this paper 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). Without loss of generality, we assume that the matrices C and
are symmetric (otherwise, replace C by (C+C T )=2 and A i by
Also, for simplicity we assume that A i are linearly independent.
Throughout this paper we assume that both (1.1) and (1.2) have finite solutions and
their optimal values are equal. Under this assumption, X   and (y   ; S   ) are solutions of (1.1)
and (1.2) if and only if they are solutions of the following nonlinear system:
Some primal-dual interior-point methods for linear programming have been successfully
extended to solve the SDP problems (1.3). For a survey of results obtained before 1993 in
this field see the paper of Alizadeh [1]. More recent results can be found in [4, 2, 3, 7, 9, 15].
Kojima, Shindoh and Hara [9], Nesterov and Todd [13], and Monteiro [12] extended some
interior-point methods for LP to SDP. In the latter paper Monteiro developed a new formulation
of the primal-dual search direction originally introduced in [9]. All above mentioned
methods, with the exception of the infeasible-interior-point potential-reduction method
of Kojima, Shindoh and Hara [9], require a strictly feasible starting point and therefore
are feasible-interior-point methods. More recently, Zhang [16], Kojima, Shida and Shindoh
[8] and the present authors (in the first version of the paper) independently proposed new
path-following algorithms for SDP. In this version, we have corrected
some flaws in the local convergence analysis contained in the first version. Our algorithm is
a predictor-corrector method generalizing the interior-point method for linear programming
proposed by Mizuno, Todd and Ye [11]. We note that the algorithm of [11] has been also
generalized for linear complementarity problems with feasible starting points in [6] and with
infeasible starting points in [10, 14]. We also mention that the Mizuno-Todd-Ye predictor-corrector
method has been extended to self-scaled cones, which includes SDP, by Nesterov
and Todd[13] under the assumption that the starting point is strictly feasible.
The algorithm to be presented in the present paper is globally convergent whenever the
problem (1.3) has a solution. The starting point does not have to be feasible. In particular
we can take as starting point any positive multiples of the identity matrix.
If the starting point is feasible or close to being feasible our algorithm finds a solution
in at most O(
iterations. If the starting point is large enough, then the algorithm
terminates in at most O(nL) steps either by finding a solution or by determining that
the primal-dual problem has no solution of norm less than a given number. Moreover, we
propose a sufficient condition for the superlinear convergence of the algorithm. The sufficient
condition is satisfied under conditions (A), (B) and (C) of Kojima, Shida and Shindoh
[8]. In addition, we give two special cases of SDP for which the algorithm is quadratically
convergent. Superlinearly convergent algorithms tend to perform in practice much better
than indicated by their iteration complexity which is based on global linear convergence
estimates. Indeed, superlinear convergence has been observed experimentally in efficient
practical algorithms.
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;
An infeasible-interior-point algorithm
We denote the feasible set of the problem (1.3) by
and its solution set by F   , i.e.,
The residues of (1.3a) and (1.3b) are denoted by:
For any given ffl ? 0 we define the set of ffl-approximate solutions of (1.3) as
In what follows we present an algorithm that finds a point in this set in a finite number of
steps (provided the problem has a solution). The algorithm will perform in a neighborhood
of the infeasible central
d g:
In our algorithm the positive parameter - will be driven to zero and therefore the residues
will also be driven to zero at the same rate as - . We use the following neighborhood of the
above central
++ \Theta IR m \Theta S n
where fl is a constant such that 1. Throughout the paper we also use the notation:
The algorithm depends on two positive parameters ff; fi satisfying the inequalities
For example, verify (2.3). At a typical step of our algorithm we are given
(X; and obtain a predictor direction (U; w; V ) 2 S n \Theta IR m \Theta S n by solving
the linear system
We will see later on that the above linear system has a unique solution, which we call the
affine scaling direction. If we take a steplength ' along this direction we obtain the points
Theoretically we would like to compute the step length
However this involves computing the root of a complicated nonlinear equation. In Lemma 2.5
we will show that
(2.
where
and
In what follows we assume that a steplength ' satisfying
is computed, and we consider the predicted points
In case of (which is very unlikely), it is easily seen that a solution (X;  is at
hand and the algorithm terminates. Now suppose that ' ! 1. Then X and S are symmetric
positive definite matrices since - i (X(')S(') -
Therefore we can define the corrector direction (U ; w; V ) as the solution of the following
linear system
We will prove later on that the above linear system has a unique solution. By taking a unit
steplength along the corrector direction we obtain a new point
Correspondingly, we define
Le us note that in setting up the linear systems (2.4) and (2.11) it is not necessary to compute
square roots of matrices. Indeed, as pointed out by Monteiro [12], it is easily seen that an
equation of the form
can be written equivalently under the form
Summarizing, we can formally define our algorithm as follows:
Algorithm 2.1 Choose (X
For do A1 through A5:
A3 Find the solution U; w; V of the linear system (2.4), define X; as in (2.10), and
set
terminate.
Find the solution U of the linear system (2.11) and define as in
(2.12) and (2.14).
In analysing our algorithm we need the following technical results.
Lemma 2.2 Suppose that M 2 IR p\Thetap is a nonsingular matrix and E 2 IR p\Thetap has at least
one real eigenvalue. Then,
Proof. See Lemma 2.6 of Monteiro [12].
Lemma 2.3 (Monteiro [12], Lemma 2.2) Let (X;
n\Thetan \Theta IR m \Theta IR n\Thetan is a solution of the linear system:
\Deltay
for some H 2 IR n\Thetan , and let
s
F
The following corollary is essentially Corollary 2.3 of Monteiro [12].
Corollary 2.4 Let (X;
the system of linear equations (2.18) has a unique solution (D
Therefore, both linear systems (2.4) and (2.11) have unique solutions.
Lemma 2.5 If (X;
defined by (2.5) satisfies (2.6) where b
' is
given by (2.7) and (2.8).
Proof. By definition, we have
If we set
then, in view of (2.19) and (2.4a), we obtain
Therefore,2
Hence, for any given parameter - 2 [0; 1) for all ' 2 [0; min( b
'; -)), we must have X(') -
-)). Otherwise, there must exist
such that X(' 0 )S(' 0 ) is singular, which means
However, using (2.16) with
(from (2:20))
which contradicts (2.21). Since X(') - 0, its square root X(') 1=2 exists and is uniquely
defined. Applying (2.17) of Lemma 2.2 with
noting that P
(from (2:20))
Therefore,
choose
which gives ' - b
'. Finally, if b
for all ' 2 [0; 1), which implies X(1) - 0;
'.
Before stating our main result let us note that the standard choice of starting points
is perfectly centered and satisfies (X required in the algorithm.
We will see that if the problem has a solution, then for any ffl ? 0 Algorithm 2.1 terminates
in a finite number (say K ffl ) of iterations. If then the algorithm is likely to generate an
infinite sequence. However it may happen that at a certain iteration (let us say at iteration
which implies that an exact solution is obtained, and therefore the
algorithm terminates at iteration K 0 . If this (unlikely) phenomenon does not happen we set
Theorem 2.6 For any integer 0 - k ! K 0 , Algorithm 2.1 defines a triple
and the corresponding residuals satisfy
where
and ' j is defined by (2.9).
Proof. The proof is by induction. For are clearly satisfied. Suppose
they are satisfied for some k - 0. As in Algorithm 2.1 we will omit the index k. Therefore
we can write
(X;
The fact that (2.23) and (2.24) hold for immediately from (2.13) and (2.14).
From (2.12) and (2.11a) we have
Then, recalling (2.26) and (2.11a), we obtain
Hence by applying Lemma 2.3 we
deduce
Using Lemma 2.3 again, we have
which implies that I
exists. Using (2.26), (2.27), applying Lemma 2.2 with
noting that
(from (2:27))
The above inequality implies that
Hence which gives S In view of (2.29), this shows that (2.22)
holds Finally, (2.25) is an immediate consequence of (2.22).
3 Global convergence and polynomial complexity
In this section we assume that F   is nonempty. Under this assumption we will prove that
Algorithm 2.1, with globally convergent in the sense that
lim
lim
In the sequel, we will frequently use the following inequality: for any M 1 ; M 2 2 IR n\Thetan ,
(see exercise 20 in section 5.6 of [5]).
Lemma 3.1 For any ( f
Proof. Let
From (2.1), (2.23), it is easily seen that (X
which implies X 0 ffl S
By expanding (3.2) we obtain the desired result.
Lemma 3.2 Assume that F   is nonempty. Then for any (X   ; y
N (ff; -) we have
where
Proof. The results follow by using Lemma 3.1 with ( f
Theorem 2.6
and the fact that S   ffl X
Lemma 3.2 shows that the pair (X k generated by Algorithm 2.1 is bounded. More
precisely, we have the following corollary, which can easily be deduced from Lemma 3.2 and
Theorem 2.6.
Corollary 3.3
(3.
Lemma 3.4 Suppose ( f
Then the quantity ffi defined by (2.8) satisfies the inequality:
!/
Proof. It is easily seen that (U
Hence, according to Lemma 2.3, we have
Therefore,
and the lemma follows by virtue of (2.8).
Lemma 3.5 Under the hypothesis of Lemma 3.4 we have
where
Proof. Using the notation of Lemma 3.4, and Lemma 3.3, we can write
Also,
and
Then (3.11) follows from Lemma 3.4.
According to Lemma 2.5 and Lemma 3.5, it follows that if F   is not empty, then the
step length ' k defined by (2.9) is bounded away from 0. This implies global convergence as
shown in the following theorem.
Theorem 3.6 If F   is not empty, then Algorithm 2.1 is globally convergent at a linear rate.
Moreover, the iteration sequence (X bounded and every accumulation point of
belongs to F   (i.e., is a primal dual optimal solution of the SDP problem).
Using Lemma 3.5, we can easily deduce the following result.
Theorem 3.7 Suppose that F   is nonempty and that the starting point is chosen such that
there is a constant - independent of n satisfying the inequality
Then Algorithm 2.1 terminates in at most O(
d k; jR 0
Theorem 3.8 Suppose constant such that kX   k -
. Then the step length ' k defined by (2.9) satisfies
the inequality
with
Proof. According to Lemma 3.2, we have
i.e.,
In the sequel we will frequently use the fact that ff ! 0:5. Since X   ffl S  we get the
relation
which implies
Applying (3.16), (3.17), Lemma 3.3, and Lemma 3.4 with ( f
F
F
In view of (3.18), (3.19) and Lemma 3.3, we obtain
F
F
Therefore,
!/
Consequently, ' ? 1=(!n).
In the following corollary we summarize the complexity results for standard starting point
of the form X
Corollary 3.9 Assume that in Algorithm 2.1 we choose a starting point of the form X
constant. Let ffl 0 be given by (3.12) and let ffl ? 0 be arbitrary.
Then the following statements hold:
(i) If F   6= ;, then the algorithm terminates with an ffl-approximate solution (X
F ffl in a finite number of steps
(iii) For any choice of ae ? 0 there is an index
such that either
or,
and in the latter case there is no solution (X kg.
4 Superlinear convergence
The next two lemmas are well known and can be easily proved.
Lemma 4.1 Let A 1
. Then A 1 ffl A
. Then, there exists an orthogonal matrix
such that Q T X   Q and Q T S   Q are diagonal matrices. In other words, q are eigen-vectors
of X   and S   .
Definition 4.3 A triple (X   ; y   is called a strictly complementary solution of
In this section we investigate the asymptotic behavior of Algorithm 2.1. We will propose a
sufficient condition for the superlinear convergence of Algorithm 2.1.
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 notations:
Lemma 4.4 Under Assumption 1,
ks
ks
Proof. Because the sequence f(X k ; S k )g is bounded, we have
ks
In view of (3.3b), we get
Tr(X
where
Tr(X
and q T
Similarly, ks
From
Theorem 2.6, we obtain
which implies
i.e.,
Therefore,
Hence, for any i 2 IB we can write
ks
Also, for any i 2 IN,
ks
Therefore, kb x
Similarly, by considering
we can show that kb s
Using Lemma 4.4, we can write
O(
-) O(
O(
O(
Let us define a linear manifold:
It is easily seen that if (X
Lemma 4.5 Under Assumption 1, F   ae M.
Proof. For any (X   ; y
Hence,
which implies
4.1, we have
which implies
i.e.,
If i or j 2 IB, then q T
is positive, which implies q T
according
to (4.4). Similarly, we can show that q T
Therefore,
which gives F   ae M.
Lemma 4.6 Under Assumption 1, every accumulation point of (X strictly
complementary solution of (1.3).
Proof. Suppose (X "; y"; S") 2 F   is an accumulation point. Let us assume, without loss
of generality, that (X k ; y k according to Lemma 4.5,
for some symmetric positive semidefinite matrices MB and MN . In order to show
0, it remains to prove that MB and MN are nonsingular and therefore positive definite. From
Lemma 4.4 or (4.1), we have
O(
it has an accumulation
point. Without loss of generality, we may assume
we obtain
which implies
Hence f
must be nonsingular. Obviously f
so that MB is nonsingular. Similarly,
we can show that MN is nonsingular.
In the next theorem, we propose a sufficient condition for the superlinear convergence of
Algorithm 2.1. 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.7 Under Assumption 1, if Algorithm 1.3 is superlinearly
convergent. Moreover, if there exists a constant oe ? 0 such that
k ), then the
convergence has Q-order at least 1 oe in the sense that -
Proof. By Lemma 2.5, it remains to prove that us
omit the index k. It is easily seen that (U
with
where
Here we have used the relation -
Denoting
and applying Lemma 2.3, we obtain
which implies
Similarly,
By Lemma 4.4 and the fact that ( -
Similarly,
Let us observe that
Then from (4.8), (4.9), (4.10), (4.11), (4.12) and Corollary 3.3, we have
Hence, Finally, if
k ) for some constant oe ? 0, then we have
Therefore,
Recalling (2.25), we obtain -
We mention that our sufficient condition in the above theorem is satisfied under conditions
(A), (B) and (C) of Kojima, Shida and Shindoh [8].
We end this paper by giving two special cases of SDP for which Algorithm 2.1 is quadratically
convergent.
Proposition 4.8 If ng or Algorithm 2.1 is quadratically
convergent.
Proof. Let
S) be the solution of the minimization problem:
min
We will show that
We will prove (4.14) only for ng and a similar proof applies to the case
ng. The manifold M reduces to
Assume by contradiction that (4.14) does not hold, i.e., there exists a subsequence such that
Let us define
It is easily seen that
(\Deltay k
\Deltay k depends linearly on \DeltaS k (cf. (4.18)), we deduce that
there exists a convergent subsequence of (\DeltaX k ; \Deltay k ; \DeltaS k ). Without loss of generality we
can write
Letting k !1 in (4.18), we obtain
(\Deltay 0
From Lemma 4.4, we have for each i 2
ks
which implies that \DeltaS
Since
is not the solution of the minimization problem (4.13) for sufficiently large k,
which is a contradiction.
It is easily seen from (4.14) that ( -
Hence we can choose \Gamma in (4.6) such
that
Therefore,
From Lemma 4.4 we deduce that if ng or
In view of (4.14), (4.20) and (4.21), we have and the result follows from Theorem
4.7.

Acknowledgment

The authors would like to thank Professor Masakazu Kojima, Masayuki Shida, and
Susumu Shindoh for sending us their paper and kindly pointing out some errors in the
first version of the present paper.



--R

Interior point methods in semidefinite programming with applications to combinatorial optimization.

Complexity and nondegeneracy in semidefinite programming.
An interior-point method for semidefinite programming
Matrix Analysis.
A predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence
Linear algebra for semidefinite programming.
Global and local convergence of predictor-corrector infeasible-interior-point algorithms for semidefinite programs

A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems
On adaptive-step primal-dual interior-point algorithms for linear programming


A modified O(nL) infeasible-interior-point algorithm for LCP with quadratic convergence
Positive definite programming.
On extending primal-dual interior-point algorithms from linear programming to semidefinite programming
--TR

--CTR
S. J. Li , S. Y. Wu , X. Q. Yang , K. L. Teo, A relaxed cutting plane method for semi-infinite semi-definite programming, Journal of Computational and Applied Mathematics, v.196 n.2, p.459-473, 15 November 2006
Zhensheng Yu, Solving semidefinite programming problems via alternating direction methods, Journal of Computational and Applied Mathematics, v.193 n.2, p.437-445, 1 September 2006
Stefania Bellavia , Sandra Pieraccini, Convergence Analysis of an Inexact Infeasible Interior Point Method for Semidefinite Programming, Computational Optimization and Applications, v.29 n.3, p.289-313, December 2004
path-following;superlinear convergence;infeasible-interior-point algorithm;polynomiality;semidefinite programming