Convex Analysis

We’ll assume throughout, without always saying so, that we’re in the finite-dimensional
Euclidean vector space Rn , although sometimes, for statements that hold in any vector space,
we’ll say explicitly that we’re in a vector space V .

Definition: A set S in a vector space V is convex if for any two points x and y in S, and
any λ in the unit interval [0, 1], the point (1 − λ)x + λy is in S.

Theorem: The intersection of any collection of convex sets is convex — i.e., if for each α
T
in some set A the set Sα is convex, then the set α∈A Sα is convex.

Theorem: The closure and the interior of a convex set in Rn are both convex.

Theorem: If X1 , X2 , . . . , Xm are convex sets, then m

P
1 Xi is convex.

Theorem: For any sets X1 , X2 , . . . , Xm in Rn , m

P Pm
i=1 cl Xi ⊆ cl i=1 Xm — i.e., the sum of
the sets’ closures is a subset of the closure of their sum.

Exercise: Provide proofs of the above theorems and a counterexample to show that the sum
of sets’ closures need not be equal to the closure of their sum.

Definition: Let p 6= 0 ∈ Rn and let b be a real number. The set of solutions of the linear
equation p1 x1 + · · · + pn xn = b is a hyperplane in Rn , and is denoted H(p, b) — i.e.,
H(p, b) = {x ∈ Rn | p · x = b}.

Remark: For any non-zero real number λ, we have H(λp, λb) = H(p, b). Therefore for
any norm k · k on Rn any hyperplane can be represented by a p for which kpk = 1: given
a hyperplane H(p, b) with kpk = 6 1, let λ = 1/kpk and let p0 = λp and b0 = λb; then
H(p0 , b0 ) = H(p, b) and kp0 k = 1.

Definition: A closed half-space is a set of the form {x ∈ Rn | p · x 5 b} for some

p 6= 0 ∈ Rn and b ∈ R. An open half-space is a set of the form {x ∈ Rn | p · x < b} for
some p 6= 0 ∈ Rn and b ∈ R.

Remark: A closed (resp. open) half-space is the set of all points on one side of a hyperplane,
including (resp. not including) the hyperplane itself.

If p = (p1 , . . . , pn ) is a list of prices of some items and x = (x1 , . . . , xn ) is a “bundle” of the

items, then p · x is the value of the bundle x. The hyperplane H(p, b) is the set of all bundles
that have value b, and the half-spaces on each side of the hyperplane H(p, b) are the bundles
whose value is greater than b and the bundles whose value is less than b.
 Separating and Supporting Hyperplanes

Definition: The hyperplane H(p, b) separates sets X and Y in Rn if for all x ∈ X and
y ∈ Y , we have p · x 5 b 5 p · y. We also say that a hyperplane separates a set X and a
point y if it separates the sets X and {y}. We say that H(p, b) strictly separates X and
Y , or strictly separates X and y, if the inequalities are both strict. See Figures 1 and 2.

Definition: A hyperplane H(p, b) is bounding for a set S, or bounds S, if S lies entirely

on one side of H — i.e., if either ∀x ∈ S : p · x = b or ∀x ∈ S : p · x 5 b .

Definition: A hyperplane H(p, b) is supporting for a set S, or supports S, if it is bounding

for S and also contains a boundary point of S. See Figures 3 and 4.

Remark: If H(p, b) is a supporting hyperplane for a set S, then either b = sup{p · x | x ∈ S}

(if p · x 5 b for all x ∈ S) or b = inf{p · x | x ∈ S} (if p · x = b for all x ∈ S). If S is closed,
then b = max{p · x | x ∈ S} or b = min{p · x | x ∈ S}.

The classical theorems of convex analysis are existence theorems, theorems that guarantee
the existence of a supporting hyperplane or a separating hyperplane H(p, b) — i.e., they’re
theorems that guarantee the existence of a price-list p for which all bundles in some convex
set (for example, a feasible set, or an upper-contour set) cost more or cost less than some
specified amount.

The following theorem is essential for establishing supporting and separating hyperplane
theorems. Let’s write d(x, y) for the Euclidean distance kx − yk in Rn .

Theorem: Let S be a nonempty closed set in Rn , and let x be a point which is not in S.
b ∈ S that is closest to x — i.e., such that d(b
Then there is a point x x, x) 5 d(x, x) for all
x ∈ S.
Proof: Let y ∈ S and let r = d(y, x). Note that y 6= x, and therefore r > 0. Define
B = clB(x, r), the closed ball of radius r about x. Note that y ∈ B and B is compact.
Therefore B ∩ S is nonempty (y ∈ B ∩ S) and compact (because S is closed). The function
d(·, x) is continuous, therefore it attains a minimum on the compact set B ∩ S, say at a (not
necessarily unique) point x b ∈ B ∩ S. Now suppose there is a point x e ∈ S that is closer to
x — i.e., d(e x, x) < d(b x, x) 5 r, so we have xe ∈ B as well, and therefore x
e ∈ B ∩ S and
d(e
x, x) < d(b b minimizes d(x, x) on B ∩ S. 
x, x), contradicting the fact that x

Now we can prove two theorems guaranteeing that a convex set S can be separated by a
hyperplane from any point that’s either not in S or is in the boundary of S. Then we’ll
use the theorems to establish the classical Minkowski Theorem, which guarantees that two
disjoint convex sets in Rn can be separated by a hyperplane.

2
Closed-set Supporting Hyperplane Theorem: Let S be a nonempty, closed, convex
set. For any point x which is not in S, there is a hyperplane H(p, b) that supports S and
separates x and S.
Proof: Let x ∈/ S and let x
b be a point in S that is closest to x, the existence of which is
b − x and let b = p · x
guaranteed by the preceding proposition. Let p = x b. We will show that
H(p, b) supports S and separates x and S.

We first show that p · x < b. We have p · x b − p · x = p · (b

x − x) = p · p. Since xb 6= x, we
b − p · x > 0 — i.e., p · x < p · x
have p 6= 0, and therefore p · p > 0, so we have p · x b = b.

In order to show that x ∈ S ⇒ p · x = b, let x ∈ S and assume, by way of contradiction,

that p · x < b. For each λ ∈ (0, 1) define xλ = (1 − λ)b x + λx. (See Figure 9.) Since S is
λ
convex and xb, x ∈ S, we have x ∈ S for all λ ∈ (0, 1). We will show that for small values of
λ we have d(x, xλ ) < d(x, x
b), which will provide our contradiction, since x
b minimizes d(x, x)
on S.

First note that we have

xλ − x = (1 − λ)b
x + λx − x
x − x) + λ(x − x
= (b b)
= p + λ(x − x
b).

We show that d(x, xλ ) < d(x, x

b), or equivalently, kx − xλ k2 < kx − x
bk2 :

kx − xλ k2 = (xλ − x) · (xλ − x)
   
= p + λ(x − x b) · p + λ(x − x
b)
b) + λ2 kx − x
= p · p + 2λp · (x − x b k2
x − xk2 + λg(λ),
= kb

where g(λ) := 2(p · x − p · xb) + λkx − xbk2 . Because, by assumption, p · x < p · x

b, we have
λ 2
limλ→0 g(λ) < 0, and therefore for small values of λ we have kx − x k < kx − x bk2 — i.e.,
d(x, xλ ) < d(x, x
b), the contradiction we wished to show, thereby establishing that p · x = b
for all x ∈ S. 

Corollary: Let S be a nonempty, closed, convex set. For any point x which is not in S,
there is a hyperplane H(p, c) containing x which separates x and S.
Proof: Let H(p, b) be a hyperplane for which p·x 5 b and x ∈ S ⇒ p·x = b, the existence
of which is guaranteed by the theorem, and let c = p · x. (See Figure 9.) 

Corollary: A closed convex set S is the intersection of the closed half-spaces that contain
S.

3
Boundary-point Supporting Hyperplane Theorem: If S is a nonempty convex set and
x is in the boundary of S, then there is a hyperplane that supports S and contains x.
Proof: Let S denote the closure of S; S is a nonempty closed convex set. Because x is a
boundary point of S, for every n ∈ N the open ball B(x, n1 ) contains a point xn ∈
/ S. Note
that lim xn = x. The previous theorem ensures that for each of these points xn there is a
pn 6= 0 ∈ Rn such that

∀x ∈ S : pn · x = pn · xn ; i.e., ∀x ∈ S : pn · (x − xn ) = 0,

and we may assume without loss of generality that kpn k = 1. The set of all p ∈ Rn such
that kpk = 1 is the unit sphere in Rn , a compact set, so the sequence {pn } has a convergent
subsequence. We restrict attention to this subsequence, which we also denote by {pn }, and
we denote its limit by p. Note that kpk = 1; in particular, p 6= 0. We also denote the
corresponding subsequence of {xn } by {xn }, and for each n ∈ N we now have {xn } → x,
{pn } → p, and
∀x ∈ S : pn · (x − xn ) = 0.
Therefore
∀x ∈ S : p · (x − x) = 0; i.e., ∀x ∈ S : p · x = p · x) = 0. 

Combining the two previous theorems gives us a theorem about any convex set and any point
not in the set.

Theorem: Let S be a nonempty convex set. For any point x which is not in S, there is a
hyperplane that supports S and separates S and x.
Proof: If x is a boundary point of S then the Boundary-point Supporting Hyperplane
Theorem yields the desired result. If x is not a boundary point of S, then x ∈
/ S, a nonempty,
closed, convex set, and the Closed-set Supporting Hyperplane Theorem yields the desired
result. 

Note that a separating or supporting hyperplane might be unique, as in Figures 2 and 3,

but these theorems don’t guarantee uniqueness, as shown in Figures 1 and 4. The theorems
require that the set(s) are convex and (in some cases) closed, but these are not necessary
conditions for the existence of a separating or supporting hyperplane: in Figure 1 the set X is
not convex and either set might not be closed, but there is still a separating hyperplane. On
the other hand, we can’t dispense with the condition that the set(s) are convex; otherwise,
as in Figures 5 and 6, there might not exist a separating or supporting hyperplane. Figure 1
also shows that sets need not be bounded.

4
Minkowski’s Theorem: Let S1 and S2 be nonempty disjoint convex sets. Then there exist
p 6= 0 ∈ Rn and b ∈ R such that ∀x1 ∈ S1 , x2 ∈ S2 : p · x2 5 b 5 p · x1 — i.e., there is a
hyperplane that separates the sets.
Proof: We first show that since S1 and S2 are disjoint, 0 ∈/ S1 − S2 = S1 + (−S2 ). Suppose
instead that 0 ∈ S1 − S2 . Then there exist x1 ∈ S1 and x2 ∈ S2 such that x1 − x2 = 0. But
then x2 = x1 , and we therefore have x1 ∈ S1 and x1 ∈ S2 , i.e., S1 and S2 are not disjoint,
a contradiction. Therefore 0 ∈ / S1 − S2 . Since S1 − S2 is nonempty and convex (as the sum
of convex sets), there is a hyperplane that separates the set S1 − S2 and the point 0, so we
have
∀z ∈ S1 − S2 : p · z = p · 0 = 0; i.e.,
∀x1 ∈ S1 , x2 ∈ S2 : p · (x1 − x2 ) = 0; i.e.,
∀x1 ∈ S1 , x2 ∈ S2 : p · x1 = p · x2 .
Clearly inf x1 ∈S1 p · x1 and supx2 ∈S2 p · x2 both exist and satisfy supx2 ∈S2 p · x2 5 inf x1 ∈S1 p · x1 .
Let b be any real number that satisfies
sup p · x2 5 b 5 inf p · x1 ,
x2 ∈S2 x1 ∈S1
and then we have

∀x1 ∈ S1 , x2 ∈ S2 : p · x2 5 sup p · x 5 b 5 inf p · x 5 p · x1 . 

x∈S2 x∈S1

5
 Convex Optimization

Here’s an example of the kind of theorem we can often obtain by using convex analysis in
place of differentiability.

Theorem: Let f : X → R be a continuous quasiconcave function on a convex domain

X ⊆ Rn ; and let S be a convex subset of X. Let x be an element of S at which f does not
attain a local maximum on X. Then x maximizes f on S if and only if there is a p 6= 0 ∈ Rn
such that
(a) x maximizes f (x) s.t. p · x 5 p · x and (b) x maximizes p · x s.t. x ∈ S.

Proof: It’s easy to see that (a) and (b) together imply that x maximizes f on S: if x ∈ S,
then p · x 5 p · x according to (b); and therefore f (x) 5 f (x) according to (a).

To prove the converse, we assume that x maximizes f on S, and we will show that there
is a p 6= 0 ∈ Rn that satisfies (a) and (b). Let U = {x ∈ X | f (x) > f (x)}, the strict
f -upper-contour set of x. U is nonempty and convex, and is disjoint from S; and since S is
also nonempty and convex, the Minkowski Theorem guarantees the existence of a p 6= 0 ∈ Rn
and a real number b > 0 such that the hyperplane H(p, b) separates the two sets — i.e.,

(∗) ∀x ∈ S : p · x 5 b and (∗∗) ∀x ∈ U : b 5 p · x.

We first show that b = p · x. Because x ∈ S, we have p · x 5 b, according to (∗). We show

that p · x = b as follows: for each n ∈ N let xn be such that xn ∈ B(x, n1 ) and f (xn ) > f (x)
— i.e., xn ∈ U for each n (these points xn exist because x is not a local maximum of f ).
Therefore (∗∗) implies that p·xn = b for each n. Since {xn } converges to x, we have p·x = b.
Therefore we have established that p · x = b.

Conclusion (b) of the theorem now follows immediately: we have x ∈ S, and according to
(∗) we have p · x 5 b = p · x for all x ∈ S.

In order to establish (a), suppose that (a) fails to hold — i.e., there is a point x
b that satisfies
both p · xb 5 p · x = b and f (b x) > f (x) — i.e., x b ∈ U . Since U is open (because f is
continuous) and nonempty, there is an open ball B(b x, ) ⊆ U ; and since p · x
b 5 p · x = b, the
open ball B(bx, ) contains points x that satisfy p · x < p · x 5 b, a violation of (∗∗). 

6
Here are several observations about the convex optimization theorem we’ve just proved:

(1) The theorem is an existence theorem: its conclusion (in one direction) says that there
exists a vector p that satisfies (a) and (b). And the p that exists is often interpretable as
a list (a vector) of prices, which should be clear in both (a) and (b) — which would then
say (a) that x maximizes f among all the alternatives x whose value (at prices p) does not
exceed the value of x; and (b) that x maximizes the value of x (for example, the profit it
yields) among all the “feasible” alternatives x ∈ S. Note that the theorem fits exactly our
Robinson Crusoe example, ensuring the existence of “decentralizing” or efficiency prices.

(2) No mention is made of differentiability of f or of differentiability of any functions that

might define the set S (see (4) below). So the theorem ensures the existence of a separating
p in a broad range of situations where differentiability is not present.

(3) The function f could be replaced with a quasiconcave, locally nonsatiated, continuous
preference relation %. In that case (a) would say that x is maximal in the set {x | p·x 5 p·x}.

(4) The constraint set S, or feasible set, is often defined by a set of inequality constraints,
such as
gi (x) 5 ci (i = 1, . . . , m)
where each function gi (·) is quasiconvex, as in Figure 7. In particular, the constraints could
be linear, as in Figure 8.

Our next theorem is the Second Welfare Theorem (more precisely, the Second Welfare The-
orem is the corollary of the next theorem).

7
Theorem: For each i ∈ N = {1, . . . , n}, let ui : X → R be a continuous quasiconcave
function on a convex set X ⊆ R` that is unbounded above. Assume that for at least one
i ∈ N , ui is strictly increasing (wlog, let this be u1 ). Let (b
xi )i∈N be a Pareto allocation for


the allocation problem (ui )i∈N ,x̊ , where x̊ ∈ R`+ . Then there is a price-list p ∈ R+ `
such
i i i i
that ∀i ∈ N : x b minimizes p · x on the upper-contour set Ui = {x ∈ X | u (x) = u (b x )}.

n
Corollary: If x̊i = x bi for each i ∈ N ; if the economy E = ui ,x̊i 1 satisfies the assumptions
of the theorem; and if, for each i ∈ N there is a bundle xi ∈ X that satisfies p · xi < p · x̊i ,


then p, (bxi )N is a Walrasian equilbrium of the economy E.

Proof of the Theorem: Because (b xi )N is Pareto and u1 is strictly increasing, we have

Pn i
b = x̊. Let U1◦ denote the strict upper-contour set {x ∈ X | u1 (x) > u1 (b
1 x x1 )}, and let U
and U ◦ denote the sets
Xn n
X
U= Ui and U ◦ = U1◦ + Ui .
i=1 i=2

/ U ◦.
xi )i∈N is Pareto, we also have x̊ ∈
Clearly x̊ ∈ U , and because (b

We first show that x̊ ∈ bdy U ◦ . Each ui is continuous, therefore each Ui is closed, and we
therefore have cl Ui = Ui . It’s easy to show that cl U1◦ = U1 . Since the sum of the closures of
sets is always a subset of the closure of the sum of the sets (by a theorem above), we have
n
X n
X n
X
cl U1◦ U1◦ Ui = cl U ◦ .


U= Ui = + cl Ui ⊆ cl +
i=1 i=2 i=2

Since x̊ ∈ U ⊆ cl U ◦ — i.e., x̊ ∈ cl U ◦ — and x̊ ∈

/ U ◦ , we have x̊ ∈ bdy U ◦ .

We next show that U ◦ is nonempty and convex. Each ui is quasiconcave, therefore each set
Ui is convex (and is obviously nonempty); U1◦ is also convex, and is nonempty because u1 is
strictly increasing and X has no upper bound. Therefore U ◦ is nonempty and convex, as the
sum of nonempty convex sets.

Since U ◦ is nonempty and convex and x̊ ∈ bdy U ◦ , the Supporting Hyperplane Theorem
ensures that there is a hyperplane that supports U ◦ and contains x̊ — i.e., there exists a
p 6= 0 ∈ R` such that p · x = p · x̊ for all x ∈ U ◦ . Since U is unbounded above, p ∈ R+
`
.

Now let x ∈ U ; we’ve just shown that U ⊆ cl U ◦ , so we have x ∈ cl U ◦ , and therefore there
is a sequence {x(k)} in U ◦ that converges to x. Since each term x(k) is in U ◦ , it satisfies
p · x(k) = p · x̊, and therefore the sequence’s limit, x, satisfies p · x = p · x̊. Thus, every
x ∈ U satisfies p · x = p · x̊ — i.e., x̊ minimizes p · x on U . The Sum-of-Sets Maximization
Theorem therefore guarantees that for every i ∈ N , x bi minimizes p · x on the set Ui . 

8
 Some Additional Theorems

Here are some additional definitions and theorems that are important and useful.

Definition: The convex hull of a set S, denoted convS, is the intersection of all convex
sets that contain S.

Remark: For any set S, convS is convex (as the intersection of a collection of convex sets)
and is therefore the smallest convex set containing S.

Definition: A convex combination of a finite set {x1 , . . . , xm } of points is a linear com-

bination of the points, with the restriction that the coefficients are non-negative and sum
to 1 — i.e., a point x of the form x = λ1 x1 + · · · + λm xm for some scalars λ1 , . . . , λm that
P
satisfy λi = 0 for all i and λi = 1. (Important note: As with linear combinations, convex
combinations are only defined for finite sets of vectors.)

Remark: The convex hull of a set S is the set of all convex combinations of points in S.

A point x ∈ convS is therefore a convex combination of a finite number of points in S;

but the required number of points for a particular x might be very large. The following
theorem ensures that any point in the convex hull of S can actually be expressed as a convex
combination of a small number of points in S.

Caratheodory’s Theorem: Any point in the convex hull of a set S j Rn is a convex

combination of at most n + 1 points in S.

This result is easy to see for any finite set S in R2 : if S has m elements, the convex hull of S
is a polygon with no more then m sides, and it’s easy to see that any point in the polygon can
be expressed as a convex combination of no more than three of the vertices of the polygon
— i.e., no more than three of the members of S.

Definition: An extreme point of a convex set S is a point in S that is not a convex

combination of any other points in S.

Examples: In R2 , if S is a polygon, then the extreme points of S are the vertices of S. In

Rn , if S is a closed ball (using the Euclidean norm!), then every point in S is an extreme
point; and if S is an open convex set, then S has no extreme points.

Krein-Milman Theorem: A compact convex set is the convex hull of its extreme points.

9
Figure 1 Figure 2

Figure 3 Figure 4

10
Figure 5 Figure 6

Figure 7 Figure 8

11
Figure 9

12