A Multiple-Cut Analytic Center Cutting Plane Method for Semidefinite Feasibility Problems.
We consider the problem of  finding a point in a nonempty bounded convex body $\Gamma$ in the cone of symmetric positive semidefinite matrices ${\cal S}^m_+$. Assume that $\Gamma$ is defined by a separating oracle, which, for any given $m\ti m$ symmetric matrix $\hat{Y}$, either confirms that $\hat Y \in \Gamma$ or returns several selected cuts, i.e., a number of symmetric matrices Ai, i=1,. . .,p,  p\le p_{\max}$, such that $\Gamma$ is in the polyhedron $ \{ Y \in {\cal S}^m_+ \mid A_i \bullet Y \le A_i \bullet \hat{Y}, i=1,\ldots,p \}.$ We present a multiple-cut analytic center cutting plane algorithm. Starting from a trivial initial point, the algorithm generates a sequence of  positive definite matrices which are approximate analytic centers of a shrinking polytope in ${\cal S}^m_+$. The algorithm terminates with a point in $\Gamma$ within $O(m^3p_{\max}/\epsilon^2)$ Newton steps (to leading order), where $\epsilon$ is the maximum radius of a ball contained in $\Gamma$.
Introduction
be the set of mm symmetric matrices and let S m
be its subset of symmetric positive
semidenite matrices. We consider the problem of nding a point in a convex subset of
We assume that contains a full-dimensional closed ball with radius  > 0: The set
is implicitly dened by a separating oracle, which, for any given mm symmetric matrix ^
Y ,
either conrms that ^
Y 2 or returns several cuts, i.e., a number of symmetric matrices A
such that is in the polyhedron fY
Here p max is the maximum number of cuts admitted in each iteration.
In a recent paper [8], we presented an analytic center cutting plane method for the case p
1, in which a single cut is added in each iteration. The method was shown to have a worst-case
complexity of O(m leading order). However, to make a cutting plane algorithm
practically e-cient, adding multiple cuts is often necessary. The purpose of this paper is to
propose and analyze an analytic cutting plane method that uses multiple cuts for solving the
convex semidenite feasibility problem mentioned above. In admitting multiple cuts in an
analytic center cutting plane method, we face some new theoretical problems that are dierent
from the single-cut situation, these include (a) the problem of nding a feasible starting point
for the Newton iteration after several new cuts have been added; (b) the estimation of the
number of Newton steps needed to obtain a new approximate center through estimating the
changes in the primal-dual potential function.
Our paper extends the multiple-cut schemes of Go-n and Vial, Luo, and Ye [2, 5, 10] from
Such extensions not only broaden the applications of cutting plane methods, but
also extend several classical theoretical results for non-negative vectors to positive semidenite
matrices. We note that for our multiple-cut analytic center cutting plane algorithm, the
complexity analysis on the number of Newton iterations per oracle call follows the approach
in [3].For the complexity analysis on the number of oracle calls, we follow the approach in [10],
but we simplify the proofs of some results analogous to those in [10] by considering all the
added cuts simultaneously instead of inductively.
In this paper we will show that, starting from a trivial initial point, the multiple-cut algorithm
generates a sequence of positive denite matrices which are approximate analytic centers of a
shrinking polytope in S m
. The algorithm will stop with a solution in at most O(m 3
(to leading order) Newton steps. Our analysis show that when the the problem is specialized
to the space of positive semidenite diagonal matrices (which is equivalent to the non-negative
the complexity bound is reduced to O(m 2 p This complexity bound is
lower than the existing bound of O(m
obtained in [2] and [10], where the same cuts
are considered. Our bound appears to be better than that obtained in [5]. (Note that the
proof for the bound appeared in [5] is incomplete, and to our best knowledge, a provable
bound should be O(m
Furthermore, the analysis in [5] is carried out only for the
so-called shallow cuts that are placed at some distances away from the current testing point
and hence may not be as e-cient as our proposed algorithm where the cuts pass through the
testing point.
We are able to obtain better complexity results than existing ones even when the problem is
specialized to IR m
because in each oracle call, we only admit cuts that are su-ciently good.
We shall not give the precise denition of \goodness" here but refer the reader to section 4.
Roughly speaking, base on our criteria, the admitted cuts A in each oracle call are
eective in reducing the size of polytope in the sense that each should be able to delete a sizable
portion of the current polytope that can not be otherwise deleted by the other admitted cuts.
One obvious advantage of having such a selection criterion is that the number of cuts added
in each iteration will be reduced since only eective cuts are admitted, and this translates into
saving in the computational cost in each Newton step.
We will now introduce some notations. For matrices
A  Y := tr(AY
We write Y  0 and Y  0 if Y is positive denite and positive semidenite, respectively. For
Y  0, we denote its symmetric square root by Y 1=2 . The 2-norm of a vector x is denoted by
kxk, and the matrix 2-norm of a matrix A is denoted by kAk. For A
are the eigenvalues of A. Note that
k(A)k1 . We will use these facts in the paper without explicitly mentioning them. For a
positive vector x 2 IR n , we write
Generally, we use capital letters for matrices, lower case ones for vectors, and Greek letters for
scalars. For convenience, we let
Let svec be an isometry identifying S m with IR
m so that K
smat be the inverse of svec. Given any G 2 S m , we let G
m to be the unique
symmetric matrix such that
It is easy to see that if G is positive denite, then G
G is positive denite, and (G
G 1=2
G 1=2 . If G is nonsingular, then (G
Throughout, we make the following assumptions:
A1. is a convex subset of S m
.
A2.
where
A3. contains a full dimensional ball of radius  > 0. That is, there exists Y c
that fY
Note that Assumption A2 is made for convenience. It can be satised by scaling if the original
set ^ is bounded. That is, suppose there exists a constant
> 0 such that for all
. Then the scaled set = fY=
2 A multiple-cut analytic center cutting plane method
We rst dene the analytic center and then propose a multiple-cut analytic center cutting
plane method at the end of this section.
, be all the cuts dening the kth working
set
k . Dene
Then the
set
k can be represented
as
We dene the following potential function on the
set
and denote
The unique minimizer of  k (Y )
over
k is known as the analytic center
of
k .
It is easy to see that the analytic center of the initial working
set
0 is I=2; where I is the
identity matrix. As a matter of fact,
Y
Y
The minimum of  0 (Y ) must satisfy  1 (Y
It is known [7, Proposition 5.4.5] that  k is a strongly 1-self-concordant function
on
and
diag (s), and should be the
mm matrix within the round brackets. However, we have identied that mm matrix with
a vector in IR
m through the linear isometry svec.
The optimality conditions for minimizing  k are:
denotes the vector of ones)
I  Y  0; Z; V  0; s; x > 0:
With a slight abuse of language, we also call the solution (
V ) of (2.1) the analytic
center
of
k .
Denition 2.1 Given a point (Y; s;
We call (Y; s; x; Z; V ) an -approximate (analytic) center
of
all the
linear equalities in (2.1) are satised, and x; s > 0, Z; V  0. Obviously, a 0-approximate
center is exactly the analytic center
of
.
Denition 2.2 Given Y
It was shown [8] that the following lemma holds.
Lemma 2.3 Given Y We have
Remark. Given Y
the minimizer For such a Y , we
will call Y an -approximate center
of
k in the sense that the point (Y; s; x Y is an
-approximate center.
We will now describe our algorithm.
A multiple-cut analytic center cutting plane algorithm.
3=2), and pick  - 2 (; 1). Set
Let
0 be the initial working
set and let Y be the initial point.
Step 1. At the k-th iteration, call the oracle to either conrm that Y k is a feasible point of
or return p k matrices A n k
Otherwise, construct the new working
set
Step 2. Find a point ~
Y in the interior
of
(discussed in section 3).
Step 3. (Recentering) Starting with the point
Y in Step 2, perform the dual Newton
method:
3.1. If - k+1 (Y ) < , set Y to Step 1.
3.2. Otherwise, Set
smat
where
is determined as follows: if - k+1 (Y )
-,
. Go to Step 3.1.
3 Restoration of centrality
In our cutting plane algorithm, approximate analytic centers are found by using the dual
Newton method. Our aim in this section is to estimate the number of Newton steps required
to nd an approximate analytic center for a newly constructed working set. We do so by
estimating the amount of potential value we should reduce for the new set. The mechanics
are as follows. Since the potential function is 1-self-concordant, each Newton step can reduce
the potential function by a constant amount. Thus to estimate the number of Newton steps
needed to nd an approximate analytic center for a new working set, all we need is to estimate
the amount of potential value we should reduce for the new set.
To nd an approximate analytic center for a new working set, ideally, we would want the
Newton method to start with the preceding approximate analytic center Y k . However, Y k is
not in the interior of the new working
set
k+1 since the new cuts pass through this point.
Thus our immediate task is to nd an interior point
in
k+1 , and then use this point as the
starting point for the Newton method.
Let n k be the number of cuts dening the
set
k . Suppose that p k new cuts are added to form
the new
set
. Recall that
Then the
sets
and
k+1 can be written as
Suppose is an -approximate center with  < 1
3=2. (Note that by lemma
We will now construct a point ( ~
s; ~
that is in
the interior
of
. To this end, consider the following convex minimization problem:
Evidently, the above problem has a unique solution that is also the unique solution to the
KKT-conditions:
Let (~!; ~
) be an approximate solution of the above KKT conditions where (3.1a) is satised
exactly and maxfj2p k ~
~
1=2. Note that in this case,
~
Note that to nd such a pair (~!; ~
), we can apply Newton method to (3.1a) and (3.1b), where
the computational work for each Newton iteration is O(p 3
In general, this constitutes only a
very small fraction of the total computational work involved in nding an approximate analytic
center
for
k+1 . In order not to lengthen the paper unnecessarily, we shall not establish the
complexity of the Newton method for nding (~!; ~
) in this paper. Interested reader can refer
to [3] for such results.
~

~
~

~
We refer the reader to [3] for an illuminating discussion on the motivation for considering the
optimization problem (3.1a){(3.1b) in constructing the strictly interior point
of
above.
It is readily shown that the following result holds:
F
Lemma 3.1 For any vector the following inequality holds:
Proof. Refer to [11].
Lemma 3.2 Suppose (Y is an -approximate center with  < 1. Then the
following inequalities hold:
Proof. We shall omit the proof of the rst equality as it is easy. Now we proceed with the
proof of the second one. We have
where we have used a theorem of Ostrowski [4, p. 225] in the second equality above, and  i 's
are scalars such that
min (Z 1=2
Noting that  max (Z 1=2
proved the required inequality. The last
inequality in the lemma can be proven similarly.
Theorem 3.3 The point ( ~
s; ~
constructed in (3.3){(3.4) satises the last three conditions
in (2.1).
Proof. First, we show that ~
Y  I. We have
since k(S k
3=2 < 1 from (3.7). On the other hand, we also have
~
since kY 1=2
3=2 < 1. The fact that ~
Y  I can be shown similarly. Furthermore
where we used the fact that from (3.1a), B T
.
Next we show that ~ x > 0 and ~
We have
~
since by lemma 3.2,
Furthermore,
Up to this point, we have succeeded in nding an interior point
of
k+1 that is derived from
Y k . Our next task is to estimate the potential value of the new point
in
.
Lemma 3.4 Suppose - k (Y k )  . Then the potential value  k+1 ( ~
Y ) satises the following
inequality
Proof. Let ~
Y and U We have
Note that we used the fact that d B T
. Now
e (U 1=2
where
Note that e T
By applying lemma 3.1 to (3.10), we have
~
Note that in the last second inequality above, we used the Cauchy inequality to derive the
~
!.
Substituting the result in (3.12) into (3.9), we prove the lemma.
>From lemma 3.4, we see that the upper bound for the dual potential value  k+1 ( ~
the term ln ~
. If we were to consider the dual potential value alone, then nding an upper
bound for ln ~
is necessary. But we have found that nding a tight upper bound for this
term is di-cult. As a result, we have decided to consider the primal-dual potential value for
which nding an upper bound for ln ~
is not necessary. To this end, let us dene the primal
potential function associated
with
k . For any k (x; Z; V
++ that satises
the primal potential of (x; Z; V ) is dened by
The primal-dual potential function associated
with
k is
We should emphasis that the primal-dual potential function is introduced solely for the purpose
of estimating the potential value of ( ~
V ). It is not needed in our cutting plane
algorithm described in section 2.
Now we shall proceed to establish an analog of lemma 3.4 for the primal potential function.
Before doing that, we need the following lemma.
Lemma 3.5 For the directions (x; Z;V ) given in (3.4), the following inequality holds:
Proof. Noting that
!, we have
d T ~
Thus
(Y 1=2
(I U 1=2
F
F
Note that in the last inequality above, we used (3.7) and the fact that
Lemma 3.6 For the point (~x; ~
constructed in (3.6), the following inequality holds:
Proof. We have
where
Note that e T
by lemma 3.2,
F
F
By lemma 3.1 and (3.17), we get from (3.16),
By applying lemma 3.5 and (3.7), we prove the lemma.
The next lemma is an analog of lemma 3.4 for the primal-dual potential function.
Lemma is an -approximate center with  < 1
3=2. Then
where
Proof. Combining the results in lemmas 3.4 and 3.6, we have
Note that
~
~
~
~
By substituting (3.20) into (3.19), the lemma is proven.
With lemma 3.7, we can nally establish an explicitly known upper bounded for the primal-dual
potential value  k+1 ( ~
Theorem 3.8 Suppose (Y is an -approximate center with  < 1
3=2.
Then
where () is the constant given in (3.18).
Proof. We have
It is readily shown that
Next we need to get an upper bound for the term  k (Y k
(3.22). By following the proof of lemma 2.1 in [1] and using the quadratic convergence result
in [8], it is readily shown that
Similarly, it can be shown that
Combining (3.24) and (3.25), we get
By putting the results in lemma 3.7, (3.23) and (3.26) into (3.22), the theorem is proven.
With the estimate of  k+1 ( ~
theorem 3.8, we are now ready to estimate the number
of dual Newton steps required to nd an approximate analytic center
for
k+1 by using the
point ~
Y as the initial point.
Theorem 3.9 Given an -approximate center Y k
of
k with  < 1
3=2. The total number
of dual Newton steps required to nd an -approximate center Y k+1
of
k+1 is
O (p k
where the constant O(1) is independent of k.
Proof. By theorem 2.2.3 in [7], each dual Newton step reduces  k+1 by a positive constant
long as a point ^
Y with -
not yet found, while keeping
the primal iterate xed. Now, starting at ( ~
V ), the total value of  k+1 needed to be
reduced is not more than  k+1 ( ~
theorem 3.8 implies that
at most"
Newton steps are required to reach a point ^
Y with -
Y onwards, by Lemma
4.3 in [8], quadratic convergence can be achieved, so it needs at most ln(ln(
additional
full Newton steps to nd a point Y k+1 satisfying - k+1 (Y k+1 )  . (We can choose for example,
4 Potential changes and Complexity
Recall
that
is an -approximate analytic center
of
k with  < 1
3=2. Let
Then
Let
Y k and
Y k+1 be the analytic centers
of
and
where
In this section, we estimate the amount that the dual potential will increase when the working
set change
from
to
. To this end, we rst establish a lemma that is an extension of a
result in [10].
Lemma 4.1 Suppose n; p are positive integers, and  is a positive n-vector with e T
Then for any positive constant , the following inequality holds:
Y
where  is a positive constant no greater than 1:3
Proof. We need only to consider the case where n  2 as the inequality holds trivially when
1. Consider the maximization problem:
Y
It is shown in [10] that the maximizer  has the form
and
p=2
Thus
Y
Y
1=p
Y
1=p
Y
1=p
where
1+1=p e 1=(p+1)
e
Lemma 4.2 Suppose Y k is an approximate analytic center
of
3=2.
Then
where  is a constant depending only on .
Proof. For simplicity, we will drop the subscripts k and k our notations in this proof,
and denote for
example,
and
by
and
Let
Y ,
Y+ , and
Y
Let
U 1=2
U 1=2 ];
Note that
G
G T .
First, we establish an upper bound for ln
We have
G
Thus
By part (iii) of theorem 2.2.2 in [7], we have
[1 3-(Y )] 1=3
3:
Thus
Hence
Y
pln
and the desired upper bound is established.
Now observe that
Y
Y
det
det
Y
det
det
U
Using the bound in (4.3), we have
Y
det
det
Y
det
det
U
The inequality (4.2) follows once we have shown that
Y
det
det
Y
det
det
U
Note that
A
U
U
e
U 1=2
U 1=2 )C A
and by using (2.1), we have
U 1=2
Z
Z
U
Z
U
By Lemma 4.1, (4.5) is proved.
The complexity analysis is based on the following idea. For the sequence of working
set
k , we
can establish upper and lower bounds on
). The upper bound is approximately n k
which is a consequence of the assumption that contains a ball of radius  and the fact that
k is dened by n k cuts. The lower bound is obtained by estimating
which is
a consequence of Lemma 4.2. A sophisticated estimation of  r k gives rise to a lower bound that
is proportional to n k ln(n k =m 3 ). The algorithm must terminate before the lower and upper
bounds con
ict each other.
We rst establish an upper bound for
Lemma 4.3
Let
k  be dened by n k linear inequalities and the positive semidenite
constraint. Suppose Assumptions A1-A3 hold. Then
Proof. Assumptions A1-A3 imply that there exists a point Y c 2 , such that
(i) All eigenvalues of Y c and I Y c are greater than or equal to ;
(ii) For any A 2 S m with
We will brie
y describe how to prove (Y c )  e before continuing with the proof of the lemma.
Suppose  j is an eigenvalue of Y c and v j is a corresponding unit eigenvector. Consider the
. Since this matrix has a zero eigenvalue, it lies on the boundary of
0 and by Assumption A3, we have
The fact that (Y c )  (1 )e can be proven similarly.
Now we continue with the proof of the lemma. Since
Noting that
Y
Y
we have the desired inequality.
Now we turn to nding a lower bound for
r i2
Obviously, we need to estimate  r i for each i. We rst seek to bound
i by D 1
dened as follows. Let I is the identity matrix of order
m. For
let
Lemma 4.4 Let A n i +j (with be the cuts generated from the
approximate analytic center Y ii ,
k. For any point Yk , let
Then
In particular,
Proof. We rst estimate s n i +j . We have
The last inequality holds because by Assumption A2,
I
implying that e  (Y
Next, let
Note that in deriving (4.8), we used the fact that S i
for each i, and that
In our complexity analysis, we will make the following assumptions.
Assumption A4. p max  m, where p
Assumption A5. Let
There exists a xed constant   1 such that for each
Assumption A4 is made for technical reason. It is used in proof of lemma 4.5. Such an
assumption also appeared in the papers [3] and [10]. Note that Assumption A4 can be relaxed
to p max  O(m). But for simplicity, we xed the constant at 1.
Note that Assumption A5 holds trivially with . For the special case where a single
cut is used in each iteration, it holds with 1. Thus by xing  at an intermediate value
between 1 and p max , we admit only cuts that are su-ciently good in the sense that the matrix
have too many small eigenvalues. Of course, one may not want to x  at the
extreme value 1 since then the criterion is likely to reject most of the cuts unless there are
many mutually orthogonal (with respect to
The main advantage of having Assumption A5 is that in each oracle call, we have an objective
criterion to select only cuts that are useful among possibly a large number of ineective cuts.
In this way, the number of cuts added in each iteration will not be unnecessarily large, and
hence the computational time in each iteration will not grow as rapidly compared to the case
where the cuts are admitted unchecked. The choice of  in practice would depend on the
problem at hand. It should dynamically be adjusted as information on the quality of the cuts
are obtained as the cutting algorithm progresses. If the choice of  is too stringent and many
good cuts are rejected, then we can progressively increase its value so that more good cuts are
selected.
However, without a priori information on the quality of the cuts, we propose to choose  to be
a small constant, say 5, based on the following empirical observation we made from numerical
experiments. We conducted numerical experiments on random matrices of the form V T V
mp , for 260. The elements of V are drawn
independently from the standard normal distribution. We computed the ratio between the
largest eigenvalue of V T V and Tr(V T V )=p for each V , and found that these ratios are less
than 2 for all the 3510 cases we tested.
Now let us continue with our complexity analysis. Let
Since
we have
Next, we establish an upper bound for the right hand side of the above inequality. Its proof is
modeled after that of [10, lemma 3.5]. However, we simplied the proof by considering all the
cuts simultaneously instead of handling them one by one as in [10].
Lemma 4.5
9m
8m
Proof. From the equation
Y
we have
9m
where we used the fact that  max (B T
and the
inequality ln(1 +x)  8x=9 for 0  x  1=8. We also made use of Assumption A4 that p i  m.
>From (4.10), it follows immediately that
But
m+m
implying that
8m
Combining (4.11) and (4.12), the lemma is proved.
With the above lemma, we can now formally state a lower bound for
Lemma 4.6 Suppose Assumptions A1{A5 hold. Then
8m
where  is the constant appeared in (4.2).
Proof. The proof is similar to that of theorem 10 in [10] by making use of (4.9) and Lemma
4.5.
We will next estimate the number oracle calls required to nd a feasible point of .
Lemma 4.7 Suppose the Assumptions A1{A4 hold, and p max  m. Then the analytic center
cutting plane method stops with a feasible before k violates the following inequality
8m
exp

Proof. From Lemmas 4.3 and 4.6, we have
8m
Thus, the algorithm must terminate before k violates the above inequality, i.e., the algorithm
must terminate before k violates the following inequality:
8m
Since
the algorithm must terminate before k
violates the inequality in the lemma.
Theorem 4.8 Suppose the Assumptions A1-A4 hold, and p max  m. Then the analytic center
cutting plane method terminates in at most O  (m 3  p max steps, where the
notation O  means that lower order terms are ignored. The total number of cuts added is not
more than O  (m 3
Proof. Ignoring lower order terms (assuming k  m) and by the assumption that  is a
constant independent of p max , the above lemma implies that the algorithm stops as soon as k

For large k, ln n k is negligible compared to n k , hence the algorithm requires at most

cuts. By Theorem 3.9, the total number of Newton steps is
O

The theorem is proved.
For feasibility problems in IR m
m should be replaced by m in Lemma 4.7. Thus the complexity
bound is O(m 2  p max for the number of required Newton steps. This bound is better
than the bounds obtained in [2], [5], and [10].

Acknowledgement

We thank the referees for their constructive comments that greatly help to improve the paper.



--R

Complexity analysis of an interior cutting plane method for convex feasibility problems
Multiple cuts in the analytic center cutting plane method
Convex nondi
Matrix Analysis
Analysis of a cutting plane method that uses weighted analytic center and multiple cuts
Cutting plane algorithms from analytic centers: e-ciency estimates

An analytic center cutting plane method for semide
A potential reduction algorithm allowing column generation
Complexity analysis of the analytic center cutting plane method that uses multiple cuts
Interior Point Algorithms: Theory and Analysis
--TR
multiple cuts;analytic center;cutting plane methods;semidefinite programming