Full text of DOI:10.1007/s101070100240

Math. Program., Ser. A 91: 1–10 (2001)
Digital Object Identifier (DOI) 10.1007/s101070100240
Adrian S. Lewis · Hristo S. Sendov
Self-concordant barriers for hyperbolic means
Received: December 2, 1999 / Accepted: February 2001
Published online September 3, 2001 –  Springer-Verlag 2001
1/m
Abstract. The geometric mean and the function (det(·))
(on the m-by-m positive definite matrices) are
1/m
examples of “hyperbolic means”: functions of the form p
, where p is a hyperbolic polynomial of degree m.
(A homogeneous polynomial p is “hyperbolic” with respect to a vector d if the polynomial t → p(x +td) has
only real roots for every vector x.) Any hyperbolic mean is positively homogeneous and concave (on a suitable
2
domain): we present a self-concordant barrier for its hypograph, with barrier parameter O(m ). Our approach
2
is direct, and shows, for example, that the function −m log(det(·) − 1) is an m -self-concordant barrier
on a natural domain. Such barriers suggest novel interior point approaches to convex programs involving
hyperbolic means.
1. Introduction
1. Self-concordant barriers. In 1988, Nesterov and Nemirovskii developed a gen-
eral, polynomial time framework for convex programming problems, presented in their
extensive monograph [8]. This framework for interior point methods relies on the no-
tion of self-concordant barrier functions. These functions are special, convex penalty
functions which intricately regulate their own behaviour and growth.
We begin by giving the definition of a self-concordant barrier function. Let E
be a finite-dimensional real vector space and Q be an open nonempty convex subset
of E. A function F : Q → R is called a self-concordant barrier if it is three times
differentiable, convex and satisfies the conditions
|D3 F(x)[h, h, h]| ≤ 2 (D2F(x)[h, h])3/2
,
(1)
(2)
(3)
F(xr) → ∞ for any sequence xr → x ∈ ∂Q, and
√
|DF(x)[h]| ≤ ϑ (D2 F(x)[h, h])1/2
,
for all h ∈ E, x ∈ Q. Here ϑ ≥ 1 is a fixed constant depending on the function F only,
ꢀ
ꢀ
ꢀ
dk
and Dk F(x)[h, ..., h] =
F(x + th)
is the k-th directional derivative at x along
dtk
t=0
the direction h. The constant ϑ is called the parameter of the barrier function: smaller
parameters ensure that the interior point method using F runs faster. For short we call
F a ϑ-self-concordant barrier.
A.S. Lewis, Hr.S. Sendov: Department of Combinatorics & Optimization, University of Waterloo, Waterloo,
Ontario N2L 3G1, Canada
e-mail: aslewis@math.uwaterloo.ca; hssendov@barrow.uwaterloo.ca
Research supported by NSERC

2
Adrian S. Lewis, Hristo S. Sendov
If in addition cl Q is a cone and instead of conditions (1), (2), and (3) the function F
satisfies conditions (1), (2), and
F(tx) = F(x) − ϑ log(t), for all x ∈ Q, t > 0,
(4)
we say F is a ϑ-normal barrier. In fact condition (4) implies condition (3), see [8,
Corollary 2.3.2].
Note 1. Observe that if F is ϑ-self-concordant then kF is kϑ-self-concordant for any
constant k ≥ 1.
One of the most important results in Nesterov and Nemirovskii [8] is that a self-
concordant barrier function exists for every open convex set Q. They construct such
a function, called the universal barrier. The parameter ϑ in their construction has
magnitude O(dim E). Because ϑ plays an important role for the convergence speed of
the underlying interior point method the question of finding computable barrier functions
with small parameters is of fundamental interest.
A crucial example in contemporary optimization is the function − log det (·), which
is an n-normal barrier for the cone of n × n symmetric positive definite matrices,
a set of dimension n(n + 1)/2 (see [8]). In this work we show, for example, that
−n log(det (·) − 1) is a ‘shifted’ n2-self-concordant barrier on a corresponding subset
of the positive definite cone.
2. Hyperbolic polynomials. Hyperbolic polynomials originate in the theory of partial
differentialequations and are connectedwith the well-posedness of the Cauchyproblem.
For more details about this theory we refer the reader to [4], [6, §12.3–12.6], or for
those only interested in a succinct exposition of the main ideas, see [5]. There is recent
interest within the optimization community in hyperbolic polynomials because their
roots exhibit some nice convexity properties [3], and the polynomials themselves can
be used to construct self-concordant barriers with small parameters [5]. We now give
the necessary definitions for these polynomials.
A polynomial p on a finite-dimensional real vector space E is homogeneous of
degree m, if p(tx) = tm p(x), for all t ∈ R and every x ∈ E. For such a polynomial p
and a direction d ∈ E with p(d) = 0, we say that p is hyperbolic with respect to d if
the polynomial t → p(x + td) (where t is a scalar) has only real zeros for every x ∈ E.
In this case for every x ∈ E, we can write
m
ꢁ
p(x + td) = p(d) (t + ti(x, d)),
i=1
where ti(x, d) = ti(x) are minus the roots of the polynomial t → p(x + td). Here are
a few examples of hyperbolic polynomials.
(a) E = Rn. The polynomial
n
ꢁ
p(x) =
xi
i=1
is hyperbolic with respect to the direction d = (1, ..., 1).

Self-concordant barriers for hyperbolic means
3
(b) E = Rn. The polynomial
n
ꢂ
p(x) = x12 −
xi2
i=2
is hyperbolic with respect to the direction d = (1, 0, ..., 0).
(c) E = Sn (the set of n × n symmetric matrices). The polynomial
p(X) = det X
is hyperbolic with respect to the direction d = I.
(d) E = Mp,q × R (where Mp,q is the space of p × q real matrices, and we assume
q ≤ p). The polynomial
ꢃ
ꢄ
p(X,r) = det XT X − r2 Iq
(X ∈ Mp,q, r ∈ R)
is hyperbolic with respect to the direction d = (0, 1).
We can construct many new hyperbolic polynomials from oldones (see [5], forexample).
For example if p is hyperbolic of degree m with respect to d and we write it as
m
ꢂ
p(x + td) =
pi(x)ti,
i=0
then each pi(x) is hyperbolic of degree m −i with respect to d, see [2, p. 130]. Applying
this to example (a) gives us that all elementary symmetric polynomials
ꢂ
ek(x) :=
xi xi ...xi
1 2 k
1≤i1<i2<···<ik ≤n
are hyperbolic of degree k (k ≤ n) with respect to d = (1, ..., 1).
3. Hyperbolicity cone. With every hyperbolic polynomial there is an associated open
convex cone. Let p be a hyperbolic polynomial of degree m with respect to the di-
rection d. The hyperbolicity cone of p with respect to d, written C(p, d), is the set
{x ∈ E : p(x + td) = 0, ∀t ≥ 0}. In other words
C(p, d) = {x ∈ E : ti(x) > 0, 1 ≤ i ≤ m}.
Since ti(rx) = rti(x) for all real r > 0, it is easy to see that C(p, d) is indeed an open
cone (that is, closed under positive scalar multiplication) with closure
cl C(p, d) = {x ∈ E : ti(x) ≥ 0, 1 ≤ i ≤ m}.
The fact that it is also convex is deeper and we refer the reader to [4, Sect. 2] or to the
more recent paper [5, Theorem 3.1]. Another important fact that can be found there is that
if c ∈ C(p, d) then p is also hyperbolic with respect to c and C(p, d) = C(p, c). From
now on the hyperbolicity cone will be denoted C(p). We now return to the examples in
the previous subsection and identify the hyperbolicity cone in each case.

4
Adrian S. Lewis, Hristo S. Sendov
(a) The hyperbolicity cone is the interior of the positive orthant:
ꢅ
ꢆ
x ∈ Rn : xi > 0, 1 ≤ i ≤ n .
(b) The hyperbolicity cone is the Lorenz cone:
ꢇ
ꢈ
x ∈ Rn : x22 + · · · xn2 < x1
(c) The hyperbolicity cone is the cone, S+n +, of n × n symmetric positive definite
matrices.
(d) The hyperbolicity cone is the interior of the operator norm epigraph
{(X,r) ∈ Mp,q × R : |σi(X)| < r, 1 ≤ i ≤ q},
where σ1(X), ..., σq(X) are the singular values of the matrix X [3, Sect. 7.3].
2. Main result
In this section we prove our main result, first derived in [7]1. We begin with a lemma.
Lemma 1. For any real numbers t1, ..., tm, the following inequality holds:
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
ꢉ
ꢊ
3/2
m
m
ꢂ
ꢂ
ti3
≤
ti2
.
ꢀ
ꢀ
ꢀ
ꢀ
i=1
i=1
The next theorem is our key result.
Theorem 1. Let p be a hyperbolic polynomial (homogeneous of degree m) with hyper-
bolicity cone C(p). Let a ≥ 0 be a real number and
C
>a(p) = {x ∈ C(p) : p(x) > a}.
Then the function
f(x) = −m log(p(x) − a)
is an m2−self-concordant barrier on the set C>a(p).
Proof. The case a = 0 was proved in [5].
Step 0. For x ∈ C>a(p) and h ∈ Rn, we can write, using the definition of ti(h, x),
ꢋ
ꢌ
ꢋ
ꢌ
m
m
ꢁ
ꢁ
1
1
p(x + th) = tm p h +
x
= tm p(x)
+ ti(h, x) = p(x) (1 + tti).
t
t
i=1
i=1
What is important is that the roots ti = ti(h, x) don’t depend on the variable t. Differen-
tiating both sides of the above representation we get the directional derivative of p(x)
in the direction of h, which is used below repeatedly:
m
ꢂ
d
ti
p(x + th) = p(x + th)
.
dt
1 + tti
i=1
1
A. Nemirovski has pointed out that analogous results can be derived using the general theory developed
in [8, Sect. 5.1].

Self-concordant barriers for hyperbolic means
5
Step 1. Observe that in the case a = 0 we only need to prove self-concordance for
a = 1, because we can make the linear substitution x = a1/m y to obtain
f(a1/m y) = −m log(p(y) − 1) − m log(a).
(See for example [8, p. 148].)
We now compute the directional derivatives of f along the direction h, using the
representation from above
ꢉ
ꢊ
m
ꢁ
f(x + th) = −m log p(x) (1 + tti) − 1 .
i=1
For short we introduce the notation
m
m
m
ꢂ
ꢂ
ꢂ
α = p(x) − 1, C1 =
ti, C2 =
ti2, C3 =
ti3,
(5)
i=1
i=1
i=1
and observe that in our situation α > 0. Elementary calculation shows
m(α + 1)
D f(x)[h] = −
C1,
α
m(α + 1)
m(α + 1)
D2 f(x)[h, h] =
C12 +
C2, and
α2
α
m(α + 1)(α + 2)
3m(α + 1)
2m(α + 1)
D3 f(x)[h, h, h] = −
C13 −
C1C2 −
C3.
α3
α2
α
We want to prove that inequalities (1) and (3) hold for every h ∈ Rn and x ∈ C>1(p).
Step 2. We start with inequality (3), which in the new notation is
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
ꢋ
ꢌ1/2
ꢀ
m(α + 1)
m(α + 1)
m(α + 1)
C12 +
C2
.
ꢀ
C1 ≤ m
ꢀ
α
α2
α
Notice that we can assume α+1 ≥ m: the other case is trivial. After squaring both sides
m2(α+1)
and dividing by
we get
α
(α + 1)
m
C12 ≤ C12 + mC2,
α
α
so we want to show
α + 1 − m
C12 ≤ mC2.
α
The Cauchy-Schwarz inequality gives us C12 ≤ mC2 so since m ≥ 1 we obtain
α + 1 − m
α + 1 − m
C12 ≤ m
C2 ≤ mC2,
α
α
as required.

6
Adrian S. Lewis, Hristo S. Sendov
Step 3. Now we turn our attention to inequality (1). With the new notation, this is
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
(α + 1)(α + 2)C3
3(α + 1)C1C2
2(α + 1)C3 ꢀ
1
m
+
+
ꢀ
ꢀ
ꢀ
ꢀ
α3
α2
α
ꢋ
ꢌ
3/2
m(α + 1)
m(α + 1)
≤ 2
C12 +
C2
.
α2
α
α3
We multiply both sides by
to get
m(α+1)
ꢀ
ꢀ
ꢎ
ꢏ3/2
ꢍ
ꢀ
ꢀ
(α + 2)C3 + 3αC C + 2α2C ≤ 2 m(α + 1) C2 + αC
.
ꢀ
3ꢀ
1
2
2
1
1
Since this inequality is homogeneous in the vector (t1, t2, ..., tm), we may assume
without loss of generality that C1 = 1. Furthermore, by multiplying this vector by −1
if necessary, we can suppose C1 = +1, so the inequality becomes
ꢀ
ꢀ
ꢀ
ꢀ
√
ꢀ
2 + α + 3αC + 2α2C ≤ 2 mα + m (1 + αC )3/2
.
3ꢀ
2
2
We now square both sides and expand:
4 + α2 + 9α2C22 + 4α4C32 + 4α + 12αC2 + 8α2C3 + 6α2C2 + 4α3C3 +
12α3C2C3 ≤ 4mα + 12mα2C2 + 12mα3C22 + 4mα4C23 + 4m + 12mαC2
+ 12mα2C22 + 4mα3C23.
Regrouping gives
ꢃ
ꢃ
ꢄ
ꢃ
ꢄ
0 ≤ 4mC23 − 4C32 α4 + 4mC23 + 12mC22 − 4C3 − 12C2C3 α3
ꢃ
ꢄ
+ 12mC22 + 12mC2 − 6C2 − 8C3 − 9C22 − 1 α2
(6)
ꢄ
+ 12mC2 + 4m − 12C2 − 4 α + (4m − 4).
We show now that all the coefficients are positive. Using Lemma 1 and the fact m ≥ 1,
1
m
C2 ≥ this becomes clear for the coefficients of α4, α and the constant term. Further,
for the coefficient of α3 using Lemma 1 we have
4mC3 + 12mC2 − 4C3 − 12C2C3 ≥ 4mC3 + 12mC2 − 4C3/2 − 12C25/2
2
2
2
2
2
ꢃ
ꢄ
= C23/2 4mC23/2 + 12mC21/2 − 4 − 12C2 .
Consider the polynomial q(s) := 4ms3 − 12s2 + 12ms − 4. Its derivative qꢂ(s) =
1
m
2
√
12(ms − 2s + m) is nonnegative, so q is increasing. Using the fact that
≤ C21/2 we
get
√
√
ꢋ
ꢌ
1
4 m
12 12m
m
4m
q(C21/2) ≥ q
√
=
−
√
+
−
m
m
m
m
m
√
√
4( m − 1) + 8(m m − 1) + 4m( m − 1)
=
≥ 0,
m

Self-concordant barriers for hyperbolic means
7
which shows that the coefficient of α3 is positive. For the coefficient of α2, using
Lemma 1, we have
12mC22 + 12mC2 − 6C2 − 8C3 − 9C22 − 1
≥ 12mC22 + 12mC2 − 6C2 − 8C3/2 − 9C22 − 1
2
ꢃ
ꢄ
= 9(m − 1)C22 + 6(m − 1)C2 + (mC2 − 1) + C2 3mC2 − 8C1/2 + 5m .
2
The quadratic polynomial 3ms2 − 8s + 5m is strictly positive in the case when m ≥ 2,
1
m
and using the fact that C2 ≥ this implies that the coefficient is positive. In the case
when m = 1 we have C2 = 1 and one immediately sees that the coefficient of α2 is
actually zero. The fact that all coefficients of the quadric polynomial on the right hand
side of inequality (6) are positive implies that the inequality holds for all α ≥ 0, which
is what we wanted to prove.
ꢃꢄ
3. Examples and applications
3.1. Examples
Following our examples from Sect. 1, we obtain the following applications of the main
result.
(a) For any natural number m the function
ꢉ
ꢊ
m
ꢁ
f(x1, ..., xm) = −m log
xi − 1
i=1
is an m2-self-concordant barrier on the set
ꢐ
ꢑ
m
ꢁ
x ∈ Rm
:
xi > 1, xi > 0, 1 ≤ i ≤ m
.
i=1
In particular when m = 2 this result follows from Proposition 5.3.2 in [8].
(b) The function
2
f(x, y) = −2 log(y2 − ꢅxꢅ − 1)
is a 4-self-concordant barrier on the set
ꢇ
ꢈ
(y, x) ∈ R × Rn−1 : y ≥ ꢅxꢅ + 1 .
2
This result can also be found in [8]. (See the paragraph following the proof of
Proposition 5.4.3 and make the linear substitution t → z − 1, y → z + 1 in the
function ꢀ.)

8
Adrian S. Lewis, Hristo S. Sendov
(c) A more interesting example is the function
f(X) = −m log(det X − 1),
which is an m2-self-concordant barrier on the set
{X ∈ S+m+ : det X > 1}.
(d) The function
ꢃ
ꢃ
ꢄ
ꢄ
f(X,r) = −2q log det XT X − r2 Iq − 1
is a (2q)2-self-concordant barrier on the set
ꢅ
ꢃ
ꢄ
ꢆ
(X,r) ∈ Mp,q × R : det XT X − r2 Iq > 1 .
3.2. Application: hyperbolic means
A hyperbolic mean is a functionof the form p(x)1/m, where p is a hyperbolicpolynomial
of degree m, and the domain is the hyperbolicity cone C(p). Hyperbolic means are
positively homogeneous and concave [5, Lemma 3.1]. Examples include the geometric
ꢒ
m
mean ( i=1 xi)1/m, and the function
X ∈ S+m+ → (det X)1/m
.
A natural approach to applying interior point methods to convex programs involving
hyperbolic means is to use a self-concordant barrier for the hypograph of the mean, the
convex cone
H(p) = {(x, t) ∈ Rn × R : x ∈ C(p), 0 < tm < p(x)}.
The following result provides such a barrier.
Theorem 2. For a suitable positive real µ (for example µ = 400), if p is a hyperbolic
polynomial of degree m then
ꢋ
ꢋ
ꢌ
ꢌ
p(x)
tm
(x, t) → −µm log
− 1 + 2m logt
is a 2µm2-normal barrier for the hypograph, H(p), of the hyperbolic mean.
Proof. Apply Proposition 5.1.4 in [8] to Theorem 1.
ꢃꢄ
As a simple-minded illustration, suppose we want to solve the problem
1
sup p(x)m + ꢆc, xꢇ
s.t.
Ax = b
x ∈ C(p),

Self-concordant barriers for hyperbolic means
9
for some linear map A and given b and c. Rewrite this problem in the equivalent form
sup t + ꢆc, xꢇ
1
s.t. t < p(x)m
Ax = b
x ∈ C(p),
and finally into the form
max ꢆc˜, x˜ꢇ
˜
s.t.
Ax˜ = b
x˜ ∈ H(p),
˜
where c˜ := (c, 1), x˜ := (x, t), A(x, t) := Ax. We have an easily computable self-
concordant (logarithmically homogeneous) barrier for the cone H(p), so we can design
an interior point algorithm to solve this hyperbolic mean maximization problem. Using
this result we can as well easily model convex programs with constraints involving
hyperbolic means, since x ∈ C(p) satisfies an inequality of the form
ꢆc, xꢇ − p(x)1/m < b
if and only if there exists positive real t satisfying
ꢆc, xꢇ − t < b, tm < p(x).
In [8, p. 239], Nesterov and Nemirovskii show how to model convex programs involving
the geometric mean or (det (·))1/m by semidefinite programming. It is interesting to
compare their approach to this idea. Their approach involves additional variables (O(m2)
variables to model det (·)1/m, for example), whereas this idea is direct and applies to any
hyperbolic mean. On the other hand, extremely efficient algorithms are now available
for semidefinite programming (see for example [1], [9]).
4. Relationship with Güler’s result
As we mentioned above, in [5] Güler proved that − log(q(x)) is an n-self-concordant
barrier on C(q) for any hyperbolic polynomial q of degree n. (Güler attributes the
observation to Renegar.) In this concluding section we want to show that our result
cannot be deduced as an “elementary” consequence of this fact, by which we mean
that we cannot take a self-concordant barrier of the above type, restrict it to an affine
subspace and obtain the self-concordance of −m log(p(x) − 1).
Consider the following special case of Theorem 1:
−3 log(x3 − 1) is self-concordant on (1, +∞).
To deduce this from [5] we would need a hyperbolic polynomial q with respect to d
with hyperbolicity cone C(q) and vectors a and b such that
(x3 − 1)3 = q(a + xb), for all x ∈ R, and
1 < x ∈ R ⇔ a + xb ∈ C(q).

10
Adrian S. Lewis, Hristo S. Sendov: Self-concordant barriers for hyperbolic means
When x = 0 we immediately get q(a) = −1. We can also conclude that b ∈ cl C(q)
- a closed convex cone. Since d ∈ C(q), an open convex cone, we have for all small
enough real ꢁ > 0, that b+ꢁd ∈ C(q), so the polynomial q is hyperbolic with respect to
b+ꢁd as well. That is, for all small enough ꢁ > 0 the polynomial (in x) q(a+x(b+ꢁd))
has only real, nonzero roots. Clearly if q(a + xb) = (x3 − 1)3 then n ≥ 9. We divide
both sides of this equality by xn, and setting t := 1/x obtain
q(at + b) = tn−9 − 3tn−6 + 3tn−3 − tn = tn−9(1 − t3)3.
Using the fact that q(a+x(b+ꢁd)) has nonzero roots and applying the same substitution
as above we get that the polynomial (in t) t → q(at + b + ꢁd) has only real roots. Now,
for ꢁ close to zero, the degree of the polynomial q(at + b + ꢁd) is constant, and so its
roots approach the roots of q(at + b) as ꢁ approaches zero. This is a contradiction with
the fact that q(at + b) has a complex root.
Acknowledgements. The authors thank two anonymous referees for several very helpful suggestions.
References
1. Alizadeh, F., Haeberly, J.-P.A., Overton, M.L. (1998): Primal-dual interior-point methods for semidefinite
programming: Convergence rates, stability and numerical results. SIAM J. Optim. 8(3), 746–768
2. Atiyah, M.F., Bott, R., Ga˚rding, L. (1970): Lacunas for hyperbolic differential operators with constant
coefficients. Acta Math. 124, 109–189
3. Bauschke, H.H., Güler, O., Lewis, A.S., Sendov, Hr.S. (2001): Hyperbolic polynomials and convex
analysis. Canadian J. Math. 53, 470–488
4. Ga˚rding, L. (1959): An inequality for hyperbolic polynomials. J. Math. Mech. 8(6), 957–965
5. Güler, O. (1997): Hyperbolic polynomials and interior point methods for convex programming. Math.
Oper. Res. 22(2), 350–377
6. Hörmander, L. (1984): Analysis of linear partial differential operators II. Springer, New-York, Berlin
7. Lewis, A.S., Sendov, Hr.S. (1999): Self-concordant barriers for hyperbolic means. Technical Report CORR
99-31, University of Waterloo, August 1999
8. Nesterov, Y.E., Nemirovskii, A.S. (1994): Interior-Point Polynomial Algorithms in Convex Programming.
Vol. 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics,
Philadelphia
9. Todd, M.J., Toh, K.C., Tütüncü, R.H. (1998):On theNesterov-Todd directionin semidefinite programming.
SIAM J. Optim. 8(3), 769–796