The Volumetric Barrier for Semidefinite Programming.
We consider the volumetric barrier for semidefinite programming, or "generalized" volumetric barrier, as introduced by Nesterov and Nemirovskii. We extend several fundamental properties of the volumetric barrier for a polyhedral set to the semidefinite case. Our analysis facilitates a simplified proof of self-concordance for the semidefinite volumetric barrier, as well as for the combined volumetric-logarithmic barrier for semidefinite programming. For both of these barriers we obtain self-concordance parameters equal to those previously shown to hold in the polyhedral case.
Introduction
This paper concerns the volumetric barrier for semidefinite programming. The volumetric
barrier for a polyhedral set A is an m \Theta n matrix, was introduced
by Vaidya (1996). Vaidya used the volumetric barrier in the construction of a cutting plane
algorithm for convex programming; see also Anstreicher (1997b, 1999a, 1999b). Subsequently
Vaidya and Atkinson (1993) (see also Anstreicher (1997a)) used a hybrid combination of the
volumetric and logarithmic barriers for P to construct an O(m 1=4 n 1=4 L)-iteration algorithm for
a linear programming problem defined over P, with integer data of total bit size L. For m AE n
this complexity compares favorably with O(
mL), the best known iteration complexity for
methods based on the logarithmic barrier.
Nesterov and Nemirovskii (1994, Section 5.5) proved self-concordance results for the volu-
metric, and combined volumetric-logarithmic, barriers that are consistent with the algorithm
complexities obtained in Vaidya and Atkinson (1993). In fact Nesterov and Nemirovskii (1994)
obtain results for extensions of the volumetric and combined barriers to a set of the form
and C are m \Theta m symmetric matrices, and -
denotes the semidefinite ordering. The set S is a strict generalization of P, since P can be represented
by using diagonal matrices in the definition of S. Optimization over a set of the form
S is now usually referred to as semidefinite programming; see for example Alizadeh (1995) or
Vandenberghe and Boyd (1996). It is well-known (see Nesterov and Nemirovskii (1994)) that
an extension of the logarithmic barrier to S obtains an m-self-concordant barrier. In Nesterov
and Nemirovskii (1994) it is also shown that semidefinite extensions of the volumetric, and
combined volumetric-logarithmic barrier are O(
mn), and O(
mn), self-concordant barriers
for S, respectively.
The self-concordance proofs in Nesterov and Nemirovskii (1994, Section 5.5) are extremely
technical, and do not obtain the constants that would be needed to actually implement algorithms
using the barriers. Simplified proofs of self-concordance for the volumetric and combined
barriers for P are obtained in Anstreicher (1997a). In particular, it is shown these barriers
are 225
mn, and 450
mn self-concordant barriers for P, respectively. The proofs of these
self-concordance results use a number of fundamental properties of the volumetric barrier established
in Anstreicher (1996, 1997a). Unfortunately, however, the analysis of Anstreicher
(1997a) does not apply to the more general semidefinite constraint defining S, as considered
in Nesterov and Nemirovskii (1994). With the current activity in semidefinite programming
the extension of results for the volumetric and combined barriers to S is of some interest. For
example, in Nesterov and Nemirovskii (1994, p.204) it is argued that with a large number
of low-rank quadratic constraints, the combined volumetric-logarithmic barrier applied to a
semidefinite formulation obtains a lower complexity than the usual approach of applying the
logarithmic barrier directly to the quadratic constraints.
The purpose of this paper is to extend the analysis of the volumetric and combined barriers
in Anstreicher (1996, 1997a) to the semidefinite case. This analysis is by necessity somewhat
complex, but in the end we obtain semidefinite generalizations for virtually all of the fundamental
results in Anstreicher (1996, 1997a). These include:
ffl The semidefinite generalization of the matrix Q(x) having
where V (\Delta) is the volumetric barrier.
ffl The semidefinite generalization of the matrix \Sigma, which in the polyhedral case is the
diagonal matrix Representations of rV (x) and Q(x) in terms of \Sigma clearly
show the relationship with the polyhedral case (see Table 1, at the end of Section 3).
ffl Semidefinite generalizations of fundamental inequalities between Q(x) and the Hessian
of the logarithmic barrier (see Theorems 4.2 and 4.3).
ffl Self-concordance results for the volumetric, and combined, barriers identical to those
obtained for the polyhedral case. In particular, we prove that these barriers are 225
mn,
and 450
mn self-concordant barriers for S, respectively.
The fact that we obtain self-concordance results identical to those previously shown to
hold in the polyhedral case is somewhat surprising, because one important element in the
analysis here is significantly different than in Anstreicher (1997a). In Anstreicher (1997a), self-
concordance is established by proving a relative Lipschitz condition on the Hessian r 2 V (\Delta).
This proof is based on Shur product inequalities, and an application of the Gershgorin circle
theorem. The use of the Lipschitz condition is attractive because it eliminates the need to
explicitly consider the third directional derivatives of the volumetric barrier. We have been
unable to extend this proof technique to the semidefinite case, however, and consequently here
we explicitly consider the third directional derivatives of V (\Delta). The proof of the main result
concerning these third derivatives (Theorem 5.1) is based on properties of Kronecker products.
Despite the fact that on this point the analytical techniques used here and in Anstreicher
(1997a) are quite different, the final self-concordance results are identical.
An outline of the paper follows. In the next section we briefly consider some mathematical
preliminaries. The most significant of these are well-known properties of the Kronecker prod-
uct, which we use extensively throughout the paper. In Section 3 we define the logarithmic,
volumetric, and combined barriers for S, and state the main self-concordance theorems. The
proofs of these results are deferred until Section 5. Section 4 considers a detailed analysis of the
volumetric barrier for S. We first obtain Kronecker product representations for the gradient
and Hessian of V (\Delta), which are then used to prove a variety of results generalizing those in
Anstreicher (1996, 1997a). Later in the section the matrix \Sigma is defined, and alternative representations
of rV (x) and Q(x) in terms of \Sigma are obtained (see Table 1). Section 5 considers
the proofs of self-concordance for the volumetric and combined barriers. The main work here
is to obtain Kronecker product representations for the third directional derivatives of V (\Delta), and
then prove a result (Theorem 5.1) relating the third derivatives to Q(x).
Preliminaries
In this section we briefly consider several points of linear algebra and matrix calculus that will
be required in the sequel. To begin, let A and B be m \Theta m matrices. We use tr(A) to denote
the trace of A, and A ffl B to denote the matrix inner product
Let oe A denote the vector of singular values of A, that is, the positive square roots of the
eigenvalues of A T A. The Frobenius norm of A is then and the
spectral norm is We say that a matrix A is positive semidefinite (psd) if A is
symmetric, and has all non-negative eigenvalues. We use - to denote the semidefinite ordering
for symmetric matrices: A - B if A \Gamma B is psd. For a vector is the n \Theta n
diagonal matrix with Diag(v) for each i. We will make frequent use of the following
elementary properties of tr(\Delta). Parts (1) and (3) of the following proposition are well-known,
and parts (2) and (4) follow easily from (1) and (3), respectively.
Proposition 2.1 Let A and B be m \Theta m matrices. Then
1.
2. If A is symmetric, then
3. If A and B are psd, then A ffl B - 0, and A ffl
4. If A - 0 and
Let A and B be m \Theta n, and k \Theta l, matrices, respectively. The Kronecker product of A
and B, denoted
A\Omega B, is the mk \Theta nl block matrix whose block is a ij B,
n. For our purposes it is also very convenient to define a "symmetrized" Kronecker
product:
For an m \Theta n matrix A, mn is the vector formed by "stacking" the columns of
A one atop another, in the natural order. The following properties of the Kronecker product
are all well known, see for example Horn and Johnson (1991), except for (2), which follows
immediately from (1) and the definition
of\Omega S .
Proposition 2.2 Let A, B, C, and D be conforming matrices. Then
1.
(A\Omega B)(C\Omega
AC\Omega BD;
2.
3.
4. If A and B are nonsingular, then
A\Omega B is nonsingular, and
5.
6. If A and B are psd, then
A\Omega B is psd.
Lastly we consider two simple matrix calculus results. Let X be a nonsingular matrix with
(see for example Graham (1981, p.75)),
@
and also (see for example Graham (1981, p.64)),
@
where e i denotes the ith elementary vector.
3 Main Results
Let G be a closed convex subset of ! n , and let F (\Delta) be a C 3 , convex mapping from Int(G) to
!, where Int(\Delta) denotes interior. Then (Nesterov and Nemirovskii (1994)) F (\Delta) is called a #-
self-concordant barrier for G if F (\Delta) tends to infinity for any sequence approaching a boundary
point of G,
for every x 2
sup
As shown by Nesterov and Nemirovskii (1994, Theorem 3.2.1), the existence of a #-self-
concordant barrier for G implies that a linear, or convex quadratic, objective can be minimized
on G to within a tolerance ffl of optimality using O(
iterations of Newton's method.
Consider a set S ae ! n of the form
where A i , and C are m \Theta m symmetric matrices. We assume throughout that the
matrices fA i g are linearly independent, and that a point x with S(x) - 0 exists. It is then
easy to show that 0g. The logarithmic barrier for S is the function
defined on the interior of S. As shown by Nesterov and Nemirovskii (1994, Proposition 5.4.5),
f(\Delta) is an m-self-concordant barrier for S, implying the existence of polynomial-time interior-point
algorithms for linear, and convex quadratic, semidefinite programming.
The volumetric barrier V (\Delta) for S, as defined in Nesterov and Nemirovskii (1994, Section
5.5), is the function
The first main result of the paper is the following improved characterization of the self-
concordance of V (\Delta).
Theorem 3.1
each A i , and C,
are m \Theta m symmetric matrices. Then 225 m 1=2 V (\Delta) is a #-self-concordant barrier for S, for
Theorem 3.1 generalizes a result for the polyhedral volumetric barrier (Anstreicher (1997a,
Theorem 5.1)), and provides an alternative to the semidefinite self-concordance result of Nesterov
and Nemirovskii (1994, Theorem 5.5.1). It is worthwhile to note that in fact the analysis
in Nesterov and Nemirovskii (1994, Section 5.5) does not apply directly to the barrier V (\Delta) for
S as given here, because Nesterov and Nemirovskii assume that the "right-hand side" matrix
C is zero. In practice, this assumption can be satisfied by extending S to the cone
and then intersecting K with the linear constraint x recover S. The analysis in
Nesterov and Nemirovskii (1994) would then be applied to the volumetric barrier -
V (\Delta) for K.
The advantage of working with K is that some general results of Nesterov and Nemirovskii
can then be applied, because -
V (\Delta) is (n 1)-logarithmically homogenous; see Nesterov and
Nemirovskii (1994, Section 2.3.3). (For example Theorem 4.4, required in the analysis of
Section 5, could be replaced by the fact that r -
and Nemirovskii (1994, Proposition 2.3.4).) Our analysis shows, however, that the homogeneity
assumption used in Nesterov and Nemirovskii (1994) is not needed to prove self-concordance
for the semidefinite volumetric barrier.
The combined volumetric-logarithmic barrier for S is the function
where V (\Delta) is the volumetric barrier, f(\Delta) is the logarithmic barrier, and ae is a positive scalar.
The combined barrier was introduced for polyhedral sets in Vaidya and Atkinson (1993), and
extended to semidefinite constraints in Nesterov and Nemirovskii (1994). Our main result on
the self-concordance of V ae (\Delta) is the following.
Theorem 3.2 Let
each A i , and C,
are m \Theta m symmetric matrices. Assume that n ! m, and let
ae (\Delta) is a #-self-concordant barrier for S, for
Theorems 3.1 and 3.2 imply that if m AE n, then the self-concordance parameter # for
the volumetric or combined barrier for S (particularly the latter) can be lower than m, the
parameter for the logarithmic barrier. It follows that for m AE n the complexity of interior-point
algorithms for the minimization of a linear, or convex quadratic, function over S may be
improved by utilizing V (\Delta) or V ae (\Delta) in place of f(\Delta).
4 The Volumetric Barrier
Let f(\Delta) be the logarithmic barrier for S, as defined in the previous section. It is well known
(see for example Vandenberghe and Boyd (1996)) that the first and second partial derivatives
of f(\Delta) at an interior point of S are given by:
where throughout we use possible to reduce notation. Let A be the m 2 \Theta n
matrix whose ith column is
where the second equality uses Proposition 2.2 (5), the Hessian matrix
can be represented in the form (see Alizadeh (1995))
Note that positive definite under the assumptions that and that
the matrices fA i g are linearly independent.
Our first goal in this section is to obtain Kronecker product representations for the gradient
and Hessian of V (\Delta). To start, it is helpful to compute
where the second equality uses (2). In addition, using (4) and the definitions
of\Omega and\Omega S , it
is easy to see that
@
\Gamma1\Omega
Now applying the chain rule, (1), and (5), we find that
'-
A
\Gamma1\Omega
A
\Gamma1\Omega
\Gamma1=2\Omega S I
where the last equality uses Proposition 2.2 (1), S \Gamma1=2 is the unique positive definite matrix
having (S \Gamma1=2
\Gamma1=2\Omega S \Gamma1=2 ]A
A T [S
A T [S
is the orthogonal projection onto the range of [S
\Gamma1=2\Omega S \Gamma1=2 ]A. Note that the jth column of
[S
\Gamma1=2\Omega S \Gamma1=2 ]A is exactly
[S
using Proposition 2.2 (5). It follows that P is a representation, as an m 2 \Theta m 2 matrix, of the
projection onto the subspace of R m\Thetam spanned by fS \Gamma1=2 A j S \Gamma1=2 ng.
We will next compute the second partial derivatives of V (\Delta). To start, using (2) and (5),
we obtain
\Gamma1\Omega
\Gamma1\Omega
Also, using (4) and the definition
@
\Gamma1\Omega
'\Omega
\Gamma1\Omega
j\Omega
\Gamma1\Omega
Combining (6), (9), and (10), and using Proposition 2.1 (2), we obtain
are the n \Theta n matrices having
\Gamma1\Omega
\Gamma1\Omega
\Gamma1\Omega
\Gamma1\Omega
Theorem 4.1 For any x having
\Gamma1\Omega
2\Omega
I
\Gamma1\Omega
\Gamma1\Omega
Note that from Proposition 2.1 (3) and Proposition 2.2 (6) we immediately have - T Q- 0
are all psd. Since - is arbitrary, it follows that Q - 0, T - 0.
In addition, the fact that P is a projection implies that
2\Omega
where the last equality uses Proposition 2.2 (2). Applying Proposition 2.1 (4), we conclude
that
2\Omega
which is exactly is arbitrary, we have shown that T -
(1=2)(Q +R), which together with (11), Q - 0, and T - 0 implies that
To complete the proof we must show that R(x) - Q(x). Let - i ,
eigenvectors of -
B, with corresponding eigenvalues - i , m. Then (see Horn and
Johnson (1991, Theorem 4.4.5)) -
2\Omega
S I has orthonormal eigenvectors -
with corresponding eigenvalues (1=2)(- 2
Johnson (1991, Theorem
B has the same eigenvectors -
corresponding eigenvalues - i - j . It then
follows from (-
2\Omega
and Proposition 2.1 (4) then implies that P ffl ( -
2\Omega
B), which is exactly
is arbitrary we have shown that Q - R, as required. 2
Theorem 4.1 generalizes a similar result (Anstreicher (1996, Theorem A.4)) for the polyhedral
volumetric barrier. It follows from Theorem 4.1 that V (\Delta) is convex on the interior of
S. In the next theorem we demonstrate that in fact V (\Delta) is strictly convex. Theorem 4.2 is
also a direct extension of a result for the polyhedral volumetric barrier; see Anstreicher (1996,
Theorem A.5).
Theorem 4.2 Let x have S(x) - 0. Then Q(x) - (1=m)H(x).
are the eigenvalues of -
B, with corresponding orthonormal eigenvectors
As described in the proof of Theorem 4.1, -
2\Omega
I then has a full set of
orthonormal eigenvectors -
corresponding eigenvalues (1=2)(- 2
It follows from (13) that
On the other hand, P
B) implies that
together imply that - T Q-
k-k, from which it follows that - T Q- (1=m)k-k
For a given -
the conclusion of Theorem 4.2 is that
A strengthening of (23), using j -
Bj in place of k -
Bk, is a key element in our analysis of the
self-concordance of V (\Delta), in the next section. The next theorem gives a remarkably direct generalization
of a result for the polyhedral volumetric barrier; see Anstreicher (1996, Proposition
2.3).
Theorem 4.3 Let x have
be orthonormal eigenvectors of -
B, with corresponding eigenvalues
B) can be written P
j we have
loss of generality (scaling - as needed, and re-ordering
indeces) we may assume that 1. Then (24) implies that
i , from (21), we are naturally led to consider the optimization problem
e:
For fixed the constraint in (25) implies that
so the objective value in (25) can be no lower than
A straightforward differentiation shows that the minimal value for (26) occurs when v 2
1=
m, and the value is
We have thus shown that if j -
Next we will obtain alternative representations of rV (x) and Q(x) that emphasize the
connection between the semidefinite volumetric barrier and the volumetric barrier for a polyhedral
set. For fixed x with
the linear span of fU ng is equal to the span of f -
ng. (Such fU i g may
be obtained by applying a Gram-Schmidt procedure to f -
U be the m 2 \Theta n matrix
whose ith column is vec(U i ), and let
k . Then from (8), can be written
in the form It follows, from (7), that
A
A
A
A
Similarly, from (12) we have
A
A
A
The characterizations of rV (x) and Q(x) given in (27) and (28) are very convenient for
the proof of the following theorem, which will be required in the analysis of self-concordance
in the next section.
Theorem 4.4 Let x have
Proof: From (28) we have
using Proposition 2.2 (5). Letting -
A be the m 2 \Theta n matrix whose ith column is vec( -
can then write
A T
In addition, it follows from (27) that
A T vec(\Sigma): (30)
Combining (29) and (30), we obtain
A
A T
A
A T vec(\Sigma)
A
A T
A
A T
because
k , and tr(U 2
each k, by construction. 2
One final point concerning the matrix \Sigma is the issue of uniqueness, for a given
Since \Sigma is defined above in terms of fU i g, and the fU i g are not unique, it is not at all obvious
that \Sigma is unique. We will now show that \Sigma is invariant to the choice of fU i g, and is therefore
unique. To see this, note that by definition
denotes the ith column of U k (recall that each U k is symmetric by construction).
denote the ith elementary vector, and let I be an m \Theta m identity matrix. By
inspection [e
i\Omega I] T U is then the m \Theta n matrix whose kth column is (U k ) i . It follows from (31)
that
j\Omega I][e
where P is the projection from (8). Since P is uniquely determined by fA i g and
is also unique, as claimed.
In the following table we give a summary of first and second order information for the logarithmic
and volumetric barriers, for polyhedral and semidefinite constraints. For the polyhedral
case we have A is an m \Theta n matrix whose ith column is a i . Given
x with
be the vector whose components are those of the diagonal of P , and
the volumetric barrier, in both the polyhedral and semidefinite cases, the matrix Q satisfies
3Q(x). Note that, as should be the case, all formulas for the semidefinite
case also apply to the polyhedral case, with -

Table

1: Comparison of Logarithmic and Volumetric Barriers
Polyhedral Semidefinite
Logarithmic
Volumetric
5 Self-concordance
In this section we obtain proofs for the self-concordance results in Theorems 3.1 and 3.2. We
begin with an analysis of the third directional derivatives of V (\Delta). Let x have S(x) - 0, and
Using (4), (9), and (13), we immediately obtain
@
\Gamma1\Omega
\Gamma1\Omega
[S
\Gamma1\Omega
. Moreover, from (4) it is immediate that
@
[S
\Gamma1\Omega
j\Omega
\GammaS
\Gamma1\Omega
Combining (32) and (33), and using Proposition 2.1 (2), we conclude that the first directional
derivative of - T Q(x)-, in the direction -, is given by
@
\Gamma1\Omega
\Gamma1\Omega
\Gamma3AH
\Gamma1\Omega
\GammaAH
\Gamma1\Omega
2\Omega
3\Omega
2\Omega
and P is defined as in (8). Very similar computations, using (14)
and (15), result in
2\Omega
2\Omega
Combining (11) with (34), (35), and (36), we obtain the third directional derivative of V (\Delta):
Theorem 5.1 Let x have
Proof: Using the fact that
2\Omega
3\Omega
2\Omega
from Proposition 2.2 (2), (37) can be re-written as
2\Omega
2\Omega
We will analyze the two terms in (38) separately. First, from (17) we have
2\Omega
2\Omega
B]:
Using (18), and the similar relationship [ -
2\Omega
S I], it follows that
2\Omega
2\Omega
2\Omega
be the eigenvalues of -
B. Then (see Horn and Johnson (1991, Theorem
4.4.5)) the eigenvalues of [ -
are of the form (1=2)(-
Bj I
Using (39), (40), the fact that [ -
2\Omega
Proposition 2.1 (4), we then obtain
2\Omega
2\Omega
In addition, the fact that [ -
2\Omega
have the same eigenvectors implies that
2\Omega
2\Omega
2\Omega
and therefore fi fi fi fi
2\Omega
2\Omega
The proof is completed by combining (38), (41), (42), and (13). 2
Using Theorem 5.1 we can now proof the first main result of the paper, characterizing the
self-concordance of V (\Delta).
Proof of Theorem 3.1: The fact that V (x) !1 as x approaches the boundary of S follows
from (3), and the fact that S(x) is singular on the boundary of S. Combining the results of
Theorems 4.3 and 5.1, we obtain
using the fact that - T Q(x)- T r 2 V (x)[-], from Theorem 4.1. In addition,
(see Horn and Johnson (1985, Corollary
7.7.4)), so Theorem 4.4 implies that
The proof is completed by noting the effect on (43) and (44) when V (\Delta) is multiplied by the
Next we consider the self-concordance of the combined volumetric-logarithmic barrier V ae (\Delta),
as defined in Section 3. We begin with some well-known properties of the logarithmic barrier
f(\Delta).
Lemma 5.2 Let x have
Proof: From (3) and (5) we obtain
\Gamma1\Omega
\Gamma1=2\Omega
A
for each i. It follows easily from (45) that
A
and therefore
It is then immediate from the fact that j -
Bj (see the proof of Theorem 5.1) that
where the final equality uses (19). 2
It follows from Lemma 5.2, the fact that j -
Bk, and
that f(\Delta) is an m-self-concordant barrier for S, as shown by Nesterov and Nemirovskii (1994).
Using Lemma 5.2 we immediately obtain the following generalization of Theorem 5.1.
Corollary 5.3 Let x have
Proof: Combining Theorem 5.1 and Lemma 5.2, we obtain
Next we require a generalization of Theorem 4.3 that applies with Q(x)+aeH(x) in place of
Q(x). The following theorem obtains a direct extension of a result for the polyhedral combined
barrier (Anstreicher (1996, Theorem 3.3)) to the semidefinite case. To prove the theorem we
will utilize the matrices fU k g, as defined in Section 4, to reduce the theorem to a problem
already analyzed in the proof of Anstreicher (1996, Theorem 3.3).
Theorem 5.4 Let x have
be orthonormal eigenvectors of -
B, with corresponding eigenvalues
. By the definition of fU k g, there is a vector -
so that
and therefore k -
-k. It follows from (46) that for each
and therefore
-, where W is the m \Theta n matrix with
Let U be the m 2 \Theta n matrix whose kth column is vec(U k ), and let V be the m 2 \Theta m matrix
whose ith column is -
From (47) we then can then write
the ith row of W . Then
where P is the projection matrix from (8). Using (19), (21), and (48) we then have
(w T
Moreover it is clear that
(w T
-k1 . We are
now exactly in the structure of the proof of Anstreicher (1996, Theorem 3.3), with U of that
proof replaced by the matrix W . In that proof it is shown that the solution objective value of
the problem
min
(w T
(w T
can be no lower thanq
It follows that - T (Q(x)
The final ingredient needed to prove the self-concordance of V ae (\Delta) is the following simple
generalization of Theorem 4.4.
Theorem 5.5 Let x have
Proof: From the representations in Table 1 we easily obtain
A:
Let It follows that
ae
ae
A
A[I\Omega
A
A T
[I\Omega \Sigma 1=2
ae
ae
ae
Using the above results we can now prove the second main result of the paper, characterizing
the self-concordance of the combined volumetric-logarithmic barrier for S.
Proof of Theorem 3.2: Combining the results of Corollary 5.3 and Theorem 5.4, with
mp
(D
using the fact that - T Q(x)- T r 2 V (x)[-], from Theorem 4.1. In addition,
(1985, Corollary 7.7.4)), so Theorem 5.5 implies that
The proof is completed by noting the effect on (49) and (50) when V ae (\Delta) is multiplied by the



--R

Interior point methods in semidefinite programming with applications to combinatorial optimization.
Large step volumetric potential reduction algorithms for linear pro- gramming
Volumetric path following algorithms for linear programming.
On Vaidya's volumetric cutting plane method for convex program- ming
Towards a practical volumetric cutting plane method for convex programming.
Ellipsoidal approximations of convex sets based on the volumetric barrier.
Kronecker Products and Matrix Calculus: with Applications
Matrix Analysis
Topics in Matrix Analysis

A new algorithm for minimizing convex functions over convex sets.
A technique for bounding the number of iterations in path following algorithms.
programming.
--TR
self-concordance;volumetric barrier;semidefinite programming