EE599 STOCHASTIC NETWORK OPTIMIZATION, MICHAEL J.

NEELY, FALL 2008 1

Some Background Math Notes on

Limsups, Sets, and Convexity
I. L IMITS
Let f (t) be a real valued function of time. Suppose f (t) converges to a limiting value f ∗ as t → ∞ (where
f∗ is either a finite value or equal to +∞ or −∞). It follows that f (t) also converges to the same limiting value
when it is sampled over any sequence of times {t1 , t2 , . . . , tk , . . .}, provided that this sequence of times grows to
infinity. Specifically, the following simple fact holds:
Fact 1: Suppose limt→∞ f (t) = f ∗ for some value f ∗ . Then for any sequence of times {tk }∞ k=1 that satsifies
limk→∞ tk = ∞, we have:
lim f (tk ) = f ∗ . 
k→∞
An example is the function f (t) = e−t cos(t). It is easy to see that: limt→∞ e−t cos(t) = 0. Hence, any samples
of this function must also converge to zero, provided the sample times grow to infinity. However, not all functions
f (t) have limiting values, and in particular some functions may have different limits when sampled over different
sequences of times. For example, the following functions do not have well defined limits:
• f1 (t) = cos(t)

•f2 (t) = t cos(t)

Specifically, if the function f1 (t) = cos(t) is sampled at times {0, 2π, 4π, 6π, . . .}, then it is always equal to 1 over
these samples. If it is sampled at times {π/2, 3π/2, 5π/2, 7π/2, . . .}, then it is always equal to 0. If the function
f2 (t) = t cos(t) is sampled over the times {0, 2π, 4π, 6π, . . .}, then the samples converge to infinity. If it is sampled
over the times {π/2, 3π/2, 5π/2, 7π/2, . . .}, then the samples are always zero (and hence “converge” to zero). If
it is sampled at other times, the limit may not converge to anything at all due to the oscillations of the cosine
function.
Here, we define notions of a lim sup and a lim inf that are always defined for any function f (t). This makes it
easier to talk about limits of general functions. Intuitively, the lim sup represents the largest limiting value of f (t)
over any infinitely growing sequence of times {tk }∞ k=1 for which the function values f (tk ) converge. Similarly, the
lim inf represents the smallest such limiting value. In particular, for the above functions, it holds that:
• lim supt→∞ cos(t) = 1 , lim inf t→∞ cos(t) = −1

lim supt→∞ t cos(t) = ∞

• , lim supt→∞ t cos(t) = −∞
Below we formally define the lim sup and lim inf , and describe their relation to regular limits. It is important to
note in advance that whenever the regular limit exists, both the lim sup and lim inf are equal to this limit. Hence,
the lim sup and lim inf can be viewed as regular limits, and have all of the same properties of regular limits,
whenever the regular limit exists. In particular, computing the lim sup (or lim inf ) is equivalent to computing the
regular limit, provided that the regular limit exists.

A. The sup and inf definitions

We first define the sup operator. Let f (t) be any real valued function of time, and let T be any set of times
(possibly an infinite set).
Definition 1: The supremum of f (t) over t ∈ T , denoted supt∈T f (t), is defined as the smallest value x such
that f (t) ≤ x for all t ∈ T . We say that supt∈T f (t) = ∞ if f (t) has arbitrarily large values over t ∈ T .
It follows that if supt∈T f (t) is equal to some value f ∗ , then f (t) ≤ f ∗ for all t ∈ T . Further, it must be possible
to choose times τ ∈ T for which f (τ ) is arbitrarily close to f ∗ . Some examples are below:
• supt∈[0,∞) cos(t) = 1

• supt∈[5,∞) cos(t) = 1
EE599 STOCHASTIC NETWORK OPTIMIZATION, MICHAEL J. NEELY, FALL 2008 2

• supt∈[7,∞) [1 − 1/(t + 1)] = 1

• supt∈[7,∞) t cos(t) = ∞

• supt∈[7,8] e−t = e−7

• supt∈[7.5,8] e−t = e−7.5

The infimum is defined similarly:
Definition 2: The infimum of f (t) over t ∈ T , denoted inf t∈T f (t), is defined as the largest value x such that
f (t) ≥ x for all t ∈ T . We say that inf t∈T f (t) = −∞ if f (t) has arbitrarily small (negative) values over t ∈ T .
Thus, if inf t∈T f (t) is equal to some value f ∗ , then f (t) ≥ f ∗ for all t ∈ T , and f (τ ) must come arbitrarily close
to f ∗ for some values τ ∈ T .
We note that supt∈T f (t) and inf t∈T f (t) are always defined (for any function f (t) and any set of times T ).
Further, we have the following simple fact, the proof of which is one line.
Fact 2: inf t∈T f (t) ≤ supt∈T f (t). 
Proof: We know that for any τ ∈ T , we have f (τ ) ≤ supt∈T and f (τ ) ≥ inf t∈T . Thus:
inf f (t) ≤ f (τ ) ≤ sup f (t)
t∈T t∈T

proving the result.

B. The lim sup and lim inf definitions

Consider any real valued function f (t).
Definition 3: The lim sup of f (t) as t → ∞ is defined:
 
M
lim sup f (t)= lim sup f (τ )
t→∞ t→∞ τ ≥t
M
Note that the expression supτ ≥t f (τ ) can be viewed as a function of t. Specifically, we can define g(t)= supτ ≥t f (τ ),
where g(t) represents the supremum of the f (·) function over all times that are larger than or equal to t. This
function g(t) must be a non-increasing function, because the supremum is taken over smaller and smaller intervals
as t increases. That is, the supremum over the interval [7, ∞) must be greater than or equal to the supremum over
the interval [7.5, ∞), because the interval [7.5, ∞) is a subset of the interval [7, ∞). Therefore, supτ ∈[7,∞) f (τ )
considers the supremum over all times in the larger interval [7, ∞), which of course includes times t ∈ [7.5, ∞).
Because supτ ≥t f (τ ) can be viewed as a non-increasing function of t, it must have a limit as t → ∞. This is
because all non-increasing functions have well defined limits (either being finite or equal to −∞). Therefore, the
limit in the above lim sup definition is always defined. Similarly, we have:
Definition 4: The lim inf of f (t) as t → ∞ is defined:
 
M
lim inf f (t)= lim inf f (τ )
t→∞ t→∞ τ ≥t
The function inf τ ≥t f (τ ) can be viewed as a non-decreasing function of t, and hence this lim inf is also always
defined.
The following lemma follows immediately from Fact 2:
Lemma 1: Let f (t) be any real valued function. Then:
lim inf f (t) ≤ lim sup f (t). 
t→∞ t→∞

C. Relation to the regular limit

Lemma 2: Consider any function f (t), and suppose lim supt→∞ f (t) = f ∗ (where f ∗ is possibly infinite). Then:
(i) There must exist a sequence of times {tk }∞
k=1 such that limk→∞ tk = ∞ and:

lim f (tk ) = f ∗
k→∞
EE599 STOCHASTIC NETWORK OPTIMIZATION, MICHAEL J. NEELY, FALL 2008 3

(ii) For any sequence of times {τk }∞ k=1 such that limk→∞ τk = ∞ and such that the regular limit limk→∞ f (τk )
exists, then:
lim f (τk ) ≤ f ∗ . 
k→∞
This lemma is the reason that the lim sup of a function f (t) can be viewed as the largest limiting value of the
function. Similarly, the lim inf of a function f (t) can be viewed as its smallest limiting value.
The next lemma demonstrates that the lim sup, lim inf , and the regular limit are all equivalent whenever the
regular limit exists.
Lemma 3: Consider any function f (t). Then limt→∞ f (t) = f ∗ (where f ∗ is possibly infinite) if and only if:
lim sup f (t) = lim inf f (t) = f ∗
t→∞ t→∞
That is, if the regular limit exists and is equal to a value f ∗ , then
both the lim sup and lim inf of the function are
∗
equal to f . Conversely, if lim inf t→∞ f (t) = lim supt→∞ f (t), then the regular limit also exists and is equal to
the same value as the lim inf and the lim sup. 
The above lemma is very important for practical understanding of the lim inf and lim sup. It says that these
limits are identical to the regular limit whenever the regular limit exists. Thus, whenever a lim sup or lim inf
appears in an equation, the reader can view it exactly as a regular limit under the additional assumption that the
regular limit exists. However, using lim sup and lim inf notation often makes things much easier, because there is
no need to prove these limits exist (since they always exist).

D. Further Properties of the lim inf and lim sup

Lemma 4: Consider any two functions f (t) and g(t), and suppose that:
f (t) ≤ g(t) for all t
Then:
lim sup f (t) ≤ lim sup g(t)
t→∞ t→∞
lim inf f (t) ≤ lim inf g(t). 
t→∞ t→∞
The lim sup has the following properties (where f (t) and g(t) are any functions and C is any constant).
• lim supt→∞ [C + f (t)] = C + lim supt→∞ f (t)

• lim supt→∞ Cf (t) = C lim supt→∞ f (t) (assuming C > 0)

• lim supt→∞ f (t) = − lim inf t→∞ [−f (t)]

• lim supt→∞ [f (t) + g(t)] ≤ lim supt→∞ f (t) + lim supt→∞ g(t) (whenever the right hand side does not yield
“∞ + −∞” or “−∞ + ∞”).
The final property above is the only one that is different from regular limits. A simple example of this is as
M M
follows; Define f (t)= cos(t) and g(t)= − cos(t). Then:
lim sup[f (t) + g(t)] = 0
t→∞
lim sup f (t) + lim sup g(t) = 2
t→∞ t→∞
Two other useful properties are given below:
Lemma 5: Let f (t) and g(t) be any functions. Then:
lim sup[f (t) + g(t)] ≥ lim sup f (t) + lim inf g(t) ≥ lim inf [f (t) + g(t)]
t→∞ t→∞ t→∞ t→∞

whenever “lim supt→∞ f (t) + lim inf t→∞ g(t)” does not yield “∞ + −∞” or “−∞ + ∞.” 
Lemma 6: Let f (t) be any function, and let h(t) be a function with a well defined and limit, so that limt→∞ h(t) =
h∗ for some (possibly infinite) value h∗ . Then:
lim sup[h(t) + f (t)] = h∗ + lim sup f (t)
t→∞ t→∞
whenever the right hand side does not yield “∞ + −∞” or “−∞ + ∞.” 
EE599 STOCHASTIC NETWORK OPTIMIZATION, MICHAEL J. NEELY, FALL 2008 4

E. Ungraded Exercises
Use only the basic properties described in Section I-D to prove the results in the following lemmas. (Hints:
For Lemma 7, use the fact that lim supt→∞ f (t) = − lim inf t→∞ [−f (t)]. For Lemma 8 use the fact that g(t) =
(g(t) − f (t)) + f (t)):
Lemma 7: For any functions f (t), g(t) and any constant C > 0, we have:
• lim inf t→∞ Cf (t) = C lim inf t→∞ f (t)

• lim inf t→∞ f (t) = − lim supt→∞ [−f (t)]

• lim inf t→∞ [f (t) + g(t)] ≥ lim inf t→∞ f (t) + lim inf t→∞ g(t) (whenever the right hand side does not yield
“∞ + −∞” or “−∞ + ∞”). 
Lemma 8: Consider any two functions f (t), g(t), and suppose that:
lim inf [g(t) − f (t)] ≥ 0
t→∞

Then the following two properties hold:

(i) lim supt→∞ f (t) ≤ lim supt→∞ g(t)

(ii) lim inf t→∞ f (t) ≤ lim inf t→∞ g(t). 

II. P OINTS AND S ETS

Here we state the basic definitions of closed sets, limit points, and bounded sets. We also present the multi-
dimensional Bolzano-Weirstrass Theorem, which ensures that every infinite sequence of points contained in a closed
and bounded set has a convergent subsequence that converges to a point in the set. Further discussion of points
and sets can be found in [1] [2].

A. Closed Sets
Let A represent a subset of N -dimensional Euclidean space (that is, A ⊂ RN ). Thus, A contains N -dimensional
vectors (possibly infinitely many), where each vector has the form x = (x1 , . . . , xN ). Such vectors are also called
points, as they represent a single point in Euclidean space.
Definition 5: A limit point of a set A is a point x∗ ∈ RN such that there exists an infinite sequence of points
{x(1), x(2), x(3), . . .} where x(k) ∈ A for all k ∈ {1, 2, . . .} (and where the x(k) values can possibly repeat the
same points in A), and such that:
lim x(k) = x∗
k→∞
The limit in the above equation represents a component-wise limit, so that each of the N components of the
{x(k)} sequence converges to the corresponding component of x∗ . The fact that we allow points of A to be
repeated when constructing the infinite sequence ensures that every point x that is already contained in A is also
a limit point of A. This can be seen by forming the trivial sequence {x(k)}∞ k=1 = {x, x, x, . . .}.
Definition 6: A set A is closed if it contains all its limit points.
Any set A that is not closed can be transformed into a closed set simply by adding all of its limits points:
Definition 7: For any set A, define the closure of A (denoted Cl{A}), to be the set of all limit points of A
(which also includes all original points of A).
It is easy to see that for any set A, the set Cl{A} is closed. For simple examples in one dimension, define:
M
• A1 =(0, 1] = {x ∈ R | 0 < x ≤ 1}

M
• A2 = [0, 1] = {x ∈ R | 0 ≤ x ≤ 1}

M
• A3 = [0, 5.5) ∪ (6.7, 9]

M
• A4 = {1, 9.7, 10}
EE599 STOCHASTIC NETWORK OPTIMIZATION, MICHAEL J. NEELY, FALL 2008 5

M
• A5 = {1, 1/2, 1/3, 1/4, . . .} = {1/n | n ∈ {1, 2, . . .}}
Then the only limit point of A1 that is not itself contained in A1 is the point 0. It follows that Cl{A1 } = [0, 1] = A2 .
Thus, A2 is closed. The only limit points of A3 that are not contained in A3 are 5.5 and 6.7. Thus, the set A3 is
not closed, but its closure is equal to [0, 5.5] ∪ [6.7, 9]. The set A4 is a finite set and hence is always closed (because
the only possible limit points are members of the finite set). The set A5 is an infinite set of discrete points. Note
that the sequence {1, 1/2, 1/3, . . .} converges to the point 0, but 0 ∈ / A5 , and hence A5 is not closed. This same
sequence {1, 1/2, 1/3, . . .} is contained in A1 , which formally shows that 0 is a limit point of A1 .

B. Bounded Sets
Consider a subset A of RN . Recall that each point of A is a vector with the form x = (x1 , . . . , xN ). Let |x − y|
denote the traditional Euclidean distance between two vectors x and y . Specifically:
qP
M N 2
|x − y|= i=1 (xi − yi )

Definition 8: A subset A is bounded if there exists a finite constant M such that |x − y| ≤ M for all vectors
x and y contained in A.
Definition 9: An N -dimensional closed hypercube centered at the origin is a subset of RN given by [−Z/2, Z/2]N
for some positive constant Z , where:
M
[−Z/2, Z/2]N = {(x1 , . . . , xN ) | − Z/2 ≤ xi ≤ Z/2 for all i ∈ {1, . . . , N }}
Such a hypercube has edge size Z and volume Z N . It is not difficult to show from the above definitions that if
a set A is bounded, then it can be contained in some hypercube.
Consider a bounded set A ⊂ RN and suppose we have an infinite sequence of points {x(k)}∞ k=1 , where x(k) ∈ A
for all k . This sequence possibly repeats some points of A many times, and might bounce around the set A, so that
limk→∞ x(k) may not exist. However, The next theorem proves that x(k) must have a convergent subsequence.
Definition 10: Let {x(k)}∞ ∞
k=1 be an infinite sequence of points. A subsequence of {x(k)}k=1 is an infinite
sequence {yn }∞ n=1 , where this sequence selects points from the original sequence (possibly skipping some points
of the original sequence, but preserving the same order). Formally, the subsequence {yn }∞ n=1 is defined by:
M
yn = x(kn )
where kn is a strictly increasing function that maps the positive numbers {1, 2, 3, . . .} into the positive numbers
{1, 2, 3, . . .} (so that kn < kn+1 for all n ∈ {1, 2, . . .}).
As an example of a subsequence, let the original sequence consist of all positive integers {1, 2, 3, 4, . . .}, so
that x(k) = k for k ∈ {1, 2, 3, . . .}. An example subsequence of this is the sequence of all even positive integers
{2, 4, 6, 8, . . .}, so that kn = 2n and yn = x(kn ) = 2n for n ∈ {1, 2, 3, . . .}.
Theorem 1: (Multi-Dimensional Bolzano-Weirstrass) Let A be a bounded subset of RN , and let {x(k)}∞ k=1
represent an infinite sequence of points in A (so that x(k) ∈ A for all k ). Then {x(k)} has a convergent subsequence,
i.e., a subsequence {x(kn )}∞ n=1 such that:
lim x(kn ) = x∗
n→∞

for some fixed vector x∗ ∈RN . 

Thus, any infinite sequence of points contained in a bounded set has a convergent subsequence that converges
to some point x∗ . Note that the vector x∗ is thus a limit point of A. Note that the point x∗ itself may or may not
be contained in the set A. However, if A is closed, then the vector x∗ would necessarily be contained in A. In
N -dimensional Euclidean space, a subset that is both closed and bounded is called a compact set.
For intuition about why the multi-dimensional Bolzano-Weirstrass Theorem is true, consider the simple 1-
dimensional case: Let the set A consist of a closed interval [a, b]. Suppose we have a sequence of real numbers
{x(k)}∞ k=1 contained in this interval. That is, a ≤ x(k) ≤ b for all x(k) values in the sequence. Consider now the
intervals [a, (a + b)/2] and [(a + b)/2, b] (i.e., the two intervals formed by chopping [a, b] into two equal length
sub-intervals). Because there are an infinite number of points x(k) in [a, b], there must be an infinite number of
these points in at least one of the two sub-intervals. Label the sub-interval with the infinite number of points
[α1 , β1 ] (if both sub-intervals contain an infinite number of points, arbitrarily choose one of them and rename it
EE599 STOCHASTIC NETWORK OPTIMIZATION, MICHAEL J. NEELY, FALL 2008 6

[α1 , β1 ]). Note that this new interval [α1 , β1 ] has size (b−a)/2. Again divide this new interval into two sub-intervals
[α1 , (α1 + β1 )/2] and [(α1 + β1 )/2, β1 ]. Because there are an infinite number of points x(k) in [α1 , β1 ], again we
see there must be an infinite number of points in one of the two new sub-intervals. Label this sub-interval [α2 , β2 ].
Proceeding this way, we see that we can find successive points of the {x(k)} sequence in smaller and smaller
sub-intervals, where the sub-interval size is halving every step. This is a nested set of closed intervals that shrink to
size 0 (where each interval has an infinite number of the points in the {x(k)} sequence) and hence these intervals
must converge about a single limit point x∗ .
The multi-dimensional case can be proven by iteratively applying the single dimensional result to each dimension,
or by repeating the above argument but using “hypercubes” and “sub-hypercubes” in replacement of “intervals” and
“sub-intervals.” Note that when a N -dimensional hypercube has each of its dimensions divided into two halves,
we are left with 2N hypercubes, each with edge size that is halved. For example, dividing a 2-dimensional square
by cutting each edge in half creates 22 = 4 sub-squares.

III. C ONVEXITY
Definition 11: A set A ⊂ RN is said to be convex if for any two points x and y contained in A, we have:
px + (1 − p)y ∈ A
for all values p such that 0 ≤ p ≤ 1.
Note that if p = 0, then px + (1 − p)y = y , while if p = 1 then px + (1 − p)y = x. Choosing intermediate
values of p yields points that are on the line segment with endpoints x and y . Thus, a set is convex if it contains
all line segments formed by any two points of the set. An example of a convex set is a sphere (with all the inside
points of the sphere included), because the line segment formed by any two points of the sphere is also inside the
sphere. An example of a set that is not convex is a donut (more mathematically called a torus), where the donut
hole is not included.
Exercise 1: (ungraded) Show that the set of all points x = (x1 , . . . , xN ) ∈ RN that satisfy the following
collection of K linear inequalities is a convex set:
PN (1)
i=1 αi xi ≤ b1
PN (2)
i=1 αi xi ≤ b2
...
PN (K)
i=1 αi xi ≤ bK
(j)
where {b1 , . . . , bK } and {αi } are arbitary constants in R.
The linear inequalities of the above exercise define a set that is called a polyhedral convex set.

A. Convex Combinations and Convex Hulls

Here we state the basic definitions of convex sets, and state two important results. A more detailed treatment of
convex sets can be found in [1] [3].
Let A be any set in RN , and let {x1 , x2 , . . . , xk } be any finite set of k points in A.
Definition 12: A convex combination of points in A is any point x of the form:
x = p1 x1 + p2 x2 + . . . + pk xk (1)
k
Pk {xi }i=1 is a finite collection of points in A, and where pi are values such that pi ≥ 0 for all i and
where
i=1 pi = 1.
The pi values in the above definition can be viewed as probabilities, and so the right hand side of (1) can be
treated as an expectation E {X}, where X is a random vector that is equal to xi with probability pi .
Fact 3: A set A is convex if and only if it contains all of its possible convex combinations. 
The above fact suggests a simple way to form a convex set out of any (potentially non-convex) set.
Definition 13: The convex hull of a set A, denoted Conv{A}, is defined as the set of all convex combinations
of A.
EE599 STOCHASTIC NETWORK OPTIMIZATION, MICHAEL J. NEELY, FALL 2008 7

Note that the convex hull of a set A includes all of the original points of the set, because one can always form
the trivial convex combination that weights a given point with weight p = 1. Thus, A ⊂ Conv{A}. Further, the
convex hull itself is always convex. The convex hull of a set that is already convex is the same as the original set.
Fact 4: The convex hull of a closed set is closed. 
An example of the last fact is as follows: Let A = {x1 , x2 , x3 } be a finite set in 2-dimensional space containing
three elements, where x1 = (0, 0), x2 = (2, 0), x3 = (1, 1). Then A is closed (because it is finite), and so Conv{A}
is closed. The set Conv{A} is given by the triangle (including the interior) with vertices at points x1 , x2 , and x3 .
Any point on the triangle can be written as a convex combination of the 3 points x1 , x2 , and x3 .
Theorem 2: (Caratheodory’s Theorem) Let A be any subset of RN . Let x be any convex combination of points
in A, so that x can be written as a convex combination using some finite number k of points in A (where k can
be arbitrarily large):
x = p1 x1 + p2 x2 + . . . + pk xk
where xk ∈ A for all i ∈ {1, . . . , k}. Then x can also be written as a convex combination that uses only N + 1
points of A:
x = p̃1 x̃1 + p̃2 x̃2 + . . . + p̃N +1 x̃N +1
for some probabilities {p̃1 , . . . , p̃N +1 } and some elements {x̃1 , . . . , x̃N +1 } of A. 
Thus, if we have a set A ∈ R2 that contains 10 elements: A = {x1 , . . . , x10 }, then any element of the convex
hull of A can be written as a convex combination that uses at most 3 of these elements.
The following is a useful result that relates to random vectors X .
Fact 5: (from [4]) Let X be a random vector that takes values in some set A ⊂ RN . Suppose that E {X} is
defined. Then:
E {X} ∈ Conv{A}
Further, if the set A is itself convex, then Conv{A} = A, and so E {X} ∈ A. 
If A is a finite set {x1 , . . . , xk }, then the above fact is easy to establish, as the expectation can then be written:
E {X} = p1 x1 + p2 x2 + . . . + pk xk
where pi = P r[X = xi ]. As this is a convex combination, it follows that X is contained in Conv{A}. It is tempting
to think that the general result of Fact 5 for arbitrary infinite sets A can be derived by writing the integral associated
with the expectation as a limit of a finite sum. However, this approach does not work because the set A is not neces-
sarily closed (and so the set Conv{A} is not necessarily closed). Hence, the resulting limit is not a-priori guaranteed
to be contained in Conv{A}. However, a simple proof of Fact 5 can be obtained using the hyperplane separation
theorem (see, for example, [1] for a description of hyperplane separation, and the notes “Multi-Dimensional
Integration Theorem” available on the link: http://www-rcf.usc.edu/∼mjneely/pdf papers/convex integration.pdf for
a proof of a statement similar to Fact 5).

B. Convex Functions and Jensen’s Inequality

Let x be a vector in RN . Let f (x) be a function that maps the vector x to a real number.
Definition 14: A function f (x) that maps x ∈ RN to R is convex if for all pairs of vectors x1 , x2 ∈ RN and
for all values θ1 , θ2 such that θ1 ≥ 0, θ2 ≥ 0, and θ1 + θ2 = 1, we have:
f (θ1 x1 + θ2 x2 ) ≤ θ1 f (x1 ) + θ2 f (x2 )
Note that the value θ1 x1 + θ2 x2 can be viewed as an average of the two vectors x1 and x2 (using probabilities
θ1 and θ2 ), while the value θ1 f (x1 ) + θ2 f (x2 ) can be viewed as the average value of the function applied at those
two respective vectors. Thus, a function is convex if and only if the function of the average is less than or equal to
the average of the function (where averages are taken over any two points x1 and x2 ). Jensen’s inequality below
shows that this 2-point averaging property implies a more general (possibly infinite point) averaging property.
A function f (x) that is defined only over a convex subset X ⊂ RN is said to be convex over X if the same
convexity property holds, but only for all x1 , x2 in the restricted set X (rather than for all x1 , x2 ∈ RN ). Note
that it is important for the set X to be convex in this case, as otherwise the vector θ1 x1 + θ2 x2 may not be in the
set X for all required θ1 , θ2 values, and so the value f (θ1 x1 + θ2 x2 ) may not be defined.
EE599 STOCHASTIC NETWORK OPTIMIZATION, MICHAEL J. NEELY, FALL 2008 8

Definition 15: A function f (x) that maps x ∈ RN to R is concave if −f (x) is convex. A function f (x) is
concave over X (where X is a convex subset of RN ) if −f (x) is convex over X .
Theorem 3: (Jensen’s Inequality) Let X be a random vector that takes values in some convex set X ⊂ RN .
(a) If f (x) is a convex function over x ∈ X , then:
f (E {X}) ≤ E {f (X)}
(b) If f (x) is a concave function over x ∈ X , then:
f (E {X}) ≥ E {f (X)}
Note from Fact 5 that E {X} ∈ Conv(X ) = X , and so the value f (E {X}) is well defined. Note also that part
(b) follows immediately from part (a) using Definition 15. Part (a) is proven as a simple consequence of Fact 5 in
the next subsection.
Corollary 1: Let X(t) be a random vector process indexed by time t ∈ {0, 1, 2, . . .} such that X(t) ∈ X for
all t (where X is a convex set). Let f (x) be a convex function over X . Then for all t we have:
t−1 t−1
!
1X 1X
f E {X(τ )} ≤ E {f (X(τ ))}
t t
τ =0 τ =0
Proof: Fix a time t, and let T be an integer random variable that is uniform over {0, 1, 2, . . . , t − 1} and that is
independent of the process X(τ ) (for τ ∈ {0, . . . , t − 1}). Define the random variable Y = X(T ). Apply Jensen’s
inequality to f (Y ).
We note that a linear function satisfies θ1 f (x1 ) + θ2 f (x2 ) = f (θ1 x1 + θ2 x2 ) for all x1 , x2 , θ1 , θ2 . Thus, a linear
function is both convex and concave. It follows by Jensen’s inequality that if f (x) is linear, then f (E {X}) =
E {f (X)}, and so the expectation passes through the linear function.

C. General Proof of Jensen’s Inequality

Here we provide a simple and general proof of Jensen’s inequality that uses only Fact 5. Suppose that X is a
convex subset of RN , and that f (x) is a convex function over X . We want to show that if X is a vector random
variable contained in X , then f (E {X}) ≤ E {f (X)}.
To show this, define the N + 1 dimensional set Z as follows:
M
Z= {(x, y) | x ∈ X , y ≥ f (x)}
The set Z is called the epigraph of the function f (x). Because X is a convex set and f (x) is a convex function,
it is not difficult to show that Z itself is a convex set. Now define the N + 1 dimensional vector random variable
Z as follows:
M
Z= (X, f (X))
It follows that Z ∈ Z , and hence (by Fact 5) we have that E {Z} ∈ Z . It follows by definition of the set Z that:
E {Z} = (x∗ , y ∗ )
for some vector x∗ ∈ X and some value y ∗ that satisfies:
y ∗ ≥ f (x∗ ) (2)
However, by definition of the random variable Z , we have:
E {Z} = (E {X} , E {f (X)})
Therefore, x∗ = E {X} and y ∗ = E {f (X)}. From (2) it follows that E {f (X)} ≥ f (E {X}), proving the result.
EE599 STOCHASTIC NETWORK OPTIMIZATION, MICHAEL J. NEELY, FALL 2008 9

D. Bounding Convex Functions by Linear Functions

Lemma 9: (from [1]) Let f (x) be a convex function over RN . Then for any point x̂ ∈ RN , there exists a vector
â ∈ RN such that:
f (x) ≥ f (x̂) + âT (x − x̂) for all x ∈ X
where âT represents the transpose of â and âT y represents the inner product between two N dimensional vectors
a and y , defined:
N
X
M
âT y = âi yi .
i=1
The above lemma says that for any convex function f (x) over RN and any point x̂ ∈ RN , the function f (x)
can be lower bounded by a linear function1 , where that linear function shares the same function value as f (x) at
the point x̂. The linear function is sometimes called a tangential hyperplane, and the associated vector â is called
a subgradient of the function f (x) at the point x̂. Lemma 9 can be proven using hyperplane separation theory [1].
For a simple example, consider the special case when f (x) is a twice differentiable function of one real variable
x (so that N = 1). Convexity in this case is equivalent to the property that f 00 (x) ≥ 0 for all x ∈ R. By Taylor’s
theorem, for any x and x̂, we have:
1
f (x) = f (x̂) + f 0 (x̂)(x − x̂) + f 00 (x̃) ≥ f (x̂) + f 0 (x̂)(x − x̂)
2
where x̃ is a value in the closed interval between x and x̂. The linear function that bounds f (x) in this case is the
tangent of the function f (x) at the point x̂, and has slope given by f 0 (x̂).
Below we use Lemma 9 to obtain an alternative proof of Jensen’s inequality for the special case X = RN . This
alternative proof may provide some further insight.
Proof: (Alternate proof of Jensen’s inequality for the special case X = RN ) Suppose f (x) is convex over RN ,
M
and X is a random vector that takes values in RN . Define x̂= E {X}. Then by Lemma 9 there exists a vector â
such that:
f (x) ≥ f (x̂) + âT (x − x̂) for all x ∈ RN
Therefore, for any instantiation of the random variable X , we have:
f (X) ≥ f (x̂) + âT (X − x̂)
Taking expectations over both sides of the above inequality yields:
E {f (X)} ≥ f (x̂) + aT (E {X} − x̂) = f (E {X})
where the final equality follows from the definition of x̂.

R EFERENCES
[1] D. P. Bertsekas, A. Nedic, and A. E. Ozdaglar. Convex Analysis and Optimization. Boston: Athena Scientific, 2003.
[2] J. R. Munkres. Topology. NJ: Prentice Hall, Inc., 2000.
[3] D. P. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, MA, 1995.
[4] L. Georgiadis, M. J. Neely, and L. Tassiulas. Resource allocation and cross-layer control in wireless networks. Foundations and Trends
in Networking, vol. 1, no. 1, pp. 1-149, 2006.

1
Strictly speaking, the function on the right hand side of the inequality in Lemma 9 is called an affine function of x (not a linear function
of x), as it is linear plus a constant.