LECTURES ON CONVEX SETS

Niels Lauritzen

N IELS L AURITZEN
D EPARTMENT OF M ATHEMATICAL S CIENCES
U NIVERSITY OF A ARHUS
D ENMARK
E MAIL : niels@imf.au.dk
URL: http://home.imf.au.dk/niels/
March 2009

Contents
Preface

Notation
1

Introduction
1.1 Linear inequalities .
1.1.1 Two variables
1.2 Polyhedra . . . . . .
1.3 Exercises . . . . . . .

vii

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

Basics
2.1 Convex subsets of R n . . . . . . . . . . .
2.2 The convex hull . . . . . . . . . . . . . .
2.2.1 Intersections of convex subsets .
2.3 Extremal points . . . . . . . . . . . . . .
2.4 The characteristic cone for a convex set
2.5 Convex cones . . . . . . . . . . . . . . .
2.6 Affine independence . . . . . . . . . . .
2.7 Caratheodorys theorem . . . . . . . . .
2.8 The dual cone . . . . . . . . . . . . . . .
2.9 Exercises . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

Separation
3.1 Separation of a point from a closed convex set
3.2 Supporting hyperplanes . . . . . . . . . . . . .
3.3 Separation of disjoint convex sets . . . . . . . .
3.4 An application . . . . . . . . . . . . . . . . . . .
3.5 Farkas lemma . . . . . . . . . . . . . . . . . . .
3.6 Exercises . . . . . . . . . . . . . . . . . . . . . .
Polyhedra

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

1
2
2
4
6

.
.
.
.
.
.
.
.
.
.

9
9
11
14
15
16
16
18
20
21
24

.
.
.
.
.
.

27
29
31
33
33
34
37
39

iii

Contents

iv
4.1

.
.
.
.
.
.
.
.

40
41
43
46
48
49
50
54

A Linear (in)dependence
A.1 Linear dependence and linear equations . . . . . . . . . . . . .
A.2 The rank of a matrix . . . . . . . . . . . . . . . . . . . . . . . .
A.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57
57
59
61

B Analysis
B.1 Measuring distances . . . . . . . .
B.2 Sequences . . . . . . . . . . . . . .
B.2.1 Supremum and infimum . .
B.3 Bounded sequences . . . . . . . . .
B.4 Closed subsets . . . . . . . . . . . .
B.5 The interior and boundary of a set
B.6 Continuous functions . . . . . . . .
B.7 The main theorem . . . . . . . . . .
B.8 Exercises . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

63
63
65
68
68
69
70
71
72
74

C Polyhedra in standard form

C.1 Extremal points . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.2 Extremal directions . . . . . . . . . . . . . . . . . . . . . . . . .
C.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75
75
77
79

Bibliography

81

Index

83

4.2
4.3
4.4
4.5
4.6
4.7

The double description method . . . . . . .

4.1.1 The key lemma . . . . . . . . . . . .
Extremal and adjacent rays . . . . . . . . .
Farkas: from generators to half spaces . . .
Polyhedra: general linear inequalities . . .
The decomposition theorem for polyhedra
Extremal points in polyhedra . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

Preface
The theory of convex sets is a vibrant and classical field of modern mathematics with rich applications in economics and optimization.
The material in these notes is introductory starting with a small chapter
on linear inequalities and Fourier-Motzkin elimination. The aim is to show
that linear inequalities can be solved and handled with very modest means.
At the same time you get a real feeling for what is going on, instead of plowing through tons of formal definitions before encountering a triangle.
The more geometric aspects of convex sets are developed introducing notions such as extremal points and directions, convex cones and their duals,
polyhedra and separation of convex sets by hyperplanes.
The emphasis is primarily on polyhedra. In a beginning course this seems
to make a lot of sense: examples are readily available and concrete computations are feasible with the double description method ([7], [3]).
The main theoretical result is the theorem of Minkowski and Weyl on
the structure of polyhedra. We stop short of introducing general faces of
polyhedra.
I am grateful to Markus Kiderlen and Jesper Funch Thomsen for very
useful comments on these notes.

Notation
Z denotes the set of integers . . . , 2, 1, 0, 1, 2, . . . and R the set of real
numbers.
R n denotes the set of all n-tuples (or vectors) {( x1 , . . . , xn ) | x1 , . . . , xn
R } of real numbers. This is a vector space over R you can add vectors and multiply them by a real number. The zero vector (0, . . . , 0)
R n will be denoted 0.
Let u, v R n . The inequality u v means that holds for every
coordinate. For example (1, 2, 3) (1, 3, 4), since 1 1, 2 3 and
3 4. But (1, 2, 3) (1, 2, 2) is not true, since 3  2.
When x R n , b R m and A is an m n matrix, the m inequalities,
Ax b, are called a system of linear inequalities. If b = 0 this system is
called homogeneous.
Let u, v R n . Viewing u and v as n 1 matrices, the matrix product
ut v is nothing but the usual inner product of u and v. In this setting,
ut u = |u|2 , where |u| is the usual length of u.

vii

Chapter 1

Introduction
You probably agree that it is quite easy to solve the equation
2x = 4.

(1.1)

This is an example of a linear equation in one variable having the unique

solution x = 2. Perhaps you will be surprised to learn that there is essentially no difference between solving a simple equation like (1.1) and the more
complicated system
2x + y + z = 7
x + 2y + z = 8

(1.2)

x + y + 2z = 9
of linear equations in x, y and z. Using the first equation 2x + y + z = 7 we
solve for x and get
x = (7 y z)/2.
(1.3)
This may be substituted into the remaining two equations in (1.2) and we get
the simpler system
3y + z = 9
y + 3z = 11
of linear equations in y and z. Again using the first equation in this system
we get
y = (9 z)/3
(1.4)
to end up with the simple equation
8z = 24.

Chapter 1. Introduction

This is a simple equation of the type in (1.1) giving z = 3. Now z = 3 gives

y = 2 using (1.4). Finally y = 2 and z = 3 gives x = 1 using (1.3). So solving a
seemingly complicated system of linear equations like (1.2) is really no more
difficult than solving the simple equation (1.1).
We wish to invent a similar method for solving systems of linear inequalities like
x
0
x + 2y 6
(1.5)
x + y 2
x

y 3
y 0

1.1 Linear inequalities

Let us start out again with the simplest case: linear inequalities in just one
variable. Take as an example the system
2x + 1 7
3x 2 4
x + 2 3
x
0

(1.6)

This can be rewritten to

x 3
x 2
1 x
0 x
This system of linear inequalities can be reduced to just two linear inequalities:
x min(2, 3) = 2
max(1, 0) = 0 x

or simply 0 x 2. Here you see the real difference between linear equations and linear inequalities. When you reverse = you get =, but when you
reverse after multiplying by 1, you get . This is why solving linear
inequalities is more involved than solving linear equations.

1.1.1 Two variables

Let us move on to the more difficult system of linear inequalities given in
(1.5). We get inspiration from the solution of the system (1.2) of linear equations and try to isolate or eliminate x. How should we do this? We rewrite

1.1. Linear inequalities

(1.5) to
0 x
x 6 2y
2y x
x 3+y

along with the inequality 0 y which does not involve x. Again, just like in
one variable, this system can be reduced just two inequalities
x min(6 2y, 3 + y)
max(0, 2 y) x

(1.7)

max(0, 2 y) min(6 2y, 3 + y).

(1.8)

carrying the inequality 0 y along. Here is the trick. We can eliminate x

from the two inequalities in (1.7) to get the system

You can solve (1.7) in x and y if and only if you can solve (1.8) in y. If
you think about it for a while you will realize that (1.8) is equivalent to the
following four inequalities
0
0
2 y
2 y

6
3
6
3

2y
+ y
2y
+ y

These inequalities can be solved just like we solved (1.6). We get

y 3
3 y
y 4
1
2 y
0 y

where the inequality y 0 from before is attached. This system can be reduced to
0 y 3
Through a lot of labor we have proved that two numbers x and y solve the
system (1.5) if and only if
0 y 3
max(0, 2 y) x min(6 2y, 3 + y)
If you phrase things a bit more geometrically, we have proved that the projection of the solutions to (1.5) on the y-axis is the interval [0, 3]. In other words,
if x, y solve (1.5), then y [0, 3] and if y [0, 3], there exists x R such that
x, y form a solution to (1.5). This is the context for the next section.

Chapter 1. Introduction

1.2 Polyhedra
Let us introduce precise definitions. A linear inequality in n variables x1 , . . . , xn
is an inequality of the form
a1 x1 + + an xn b,
where a1 , . . . , an , b R.
DEFINITION 1.2.1
The set of solutions

P=

to a system




( x1 , . . . , x n ) R n 


a11 x1 + +

a1n xn
..
.

b1 )

am1 x1 + + amn xn bm

a11 x1 + +

a1n xn
..
.

b1

am1 x1 + + amn xn bm
of finitely many linear inequalities (here aij and bi are real numbers) is called a polyhedron. A bounded polyhedron is called a polytope.
A polyhedron is an extremely important special case of a convex subset
of R n . We will return to the definition of a convex subset in the next chapter.
The proof of the following important theorem may look intimidating at
first. If this is so, then take a look at 1.1.1 once again. Do not get fooled by the
slick presentation here. In its purest form the result goes back to a paper by
Fourier1 from 1826 (see [2]). It is also known as Fourier-Motzkin elimination,
simply because you are eliminating the variable x1 and because Motzkin2
rediscovered it in his dissertation Beitrage zur Theorie der linearen Ungleichungen with Ostrowski3 in Basel, 1933 (not knowing the classical paper
by Fourier). The main result in the dissertation of Motzkin was published
much later in [6].
THEOREM 1.2.2
Consider the projection : R n R n1 given by
( x1 , . . . , x n ) = ( x2 , . . . , x n ) .
If P R n is a polyhedron, then ( P) R n1 is a polyhedron.
1 Jean

Baptiste Joseph Fourier (1768 1830), French mathematician.

Motzkin (1908 1970), American mathematician.
3 Alexander Markowich Ostrowski (1893 1986), Russian mathematician

2 Theodore Samuel

1.2. Polyhedra

Proof. Suppose that P is the set of solutions to

a11 x1 + +

a1n xn
..
.

b1

am1 x1 + + amn xn bm
We divide the m inequalities into
G = {i | ai1 > 0}
Z = {i | ai1 = 0}
L = {i | ai1 < 0}

Inequality number i reduces to

x1 ai2 x2 + + ain xn + bi ,
if i G and to

aj2 x2 + + ajn xn + bj x1 ,

if j L, where aik = aik /ai1 and bi = bi /ai1 for k = 2, . . . , n. So the inequalities in L and G are equivalent to the two inequalities




max ai2 x2 + + ain xn + bi  i L x1




min aj2 x2 + + ajn xn + bj  j G .
Now ( x2 , . . . , xn ) ( P) if and only if there exists x1 such that ( x1 , . . . , xn )
P. This happens if and only if ( x2 , . . . , xn ) satisfies the inequalities in Z and








max ai2 x2 + + ain xn + bi  i L min aj2 x2 + + ajn xn + bj  j G

This inequality expands to the system of | L| |G | inequalities in x2 , . . . , xn consisting of

ai2 x2 + + ain xn + bi aj2 x2 + + ajn xn + bj
or rather

( ai2 aj2 ) x2 + + ( ain ajn ) xn bj bi

where i L and j G. Adding the inequalities in Z (where x1 is not present)
we see that ( P) is the set of solutions to a system of | L| |G | + |Z | linear
inequalities i.e. ( P) is a polyhedron.
To get a feeling for Fourier-Motzkin elimination you should immediately
immerse yourself in the exercises. Perhaps you will be surprised to see that
Fourier-Motzkin elimination can be applied to optimize the production of
vitamin pills.

Chapter 1. Introduction

1.3 Exercises
(1) Let

P=

 x

3  3x
( x, y, z) R 
 x
x

y z
y z
+ 3y z
y + 3z

0 )
1
2
3

and : R3 R2 be given by ( x, y, z) = (y, z).

(i) Compute ( P) as a polyhedron i.e. as the solutions to a set of linear
inequalities in y and z.
(ii) Compute ( P), where : R3 R is given by ( x, y, z) = x.
(iii) How many integral points4 does P contain?
(2) Find all solutions x, y, z Z to the linear inequalities

x + y
y +

z
z
z
z

0
0
0
1
1
1

by using Fourier-Motzkin elimination.

(3) Let P R n be a polyhedron and c R n . Define the polyhedron P
R n+1 by
!
m
P = {
| ct x = m, x P, m R },
x
where ct x is the (usual inner product) matrix product of c transposed (a
1 n matrix) with x (an n 1 matrix) giving a 1 1 matrix (also known
as a real number!).
(i) Show how projection onto the m-coordinate (and Fourier-Motzkin
elimination) in P can be used to solve the (linear programming)
problem of finding x P, such that ct x is minimal (or proving that
such an x does not exist).
4 An

integral point is simply a vector ( x, y, z) with x, y, z Z

1.3. Exercises

(ii) Let P denote the polyhedron from Exercise 1. You can see that
1 1
(0, 0, 0), (1, , ) P
2 2
have values 0 and 1 on their first coordinates, but what is the minimal first coordinate of a point in P.
(4) A vitamin pill P is produced using two ingredients M1 and M2 . The pill
needs to satisfy two requirements for the vital vitamins V1 and V2 . It
must contain at least 6 mg and at most 15 mg of V1 and at least 5 mg and
at most 12 mg of V2 . The ingredient M1 contains 3 mg of V1 and 2 mg of
V2 per gram. The ingredient M2 contains 2 mg of V1 and 3 mg of V2 per
gram.
We want a vitamin pill of minimal weight satisfying the requirements.
How many grams of M1 and M2 should we mix?

Chapter 2

Basics
The definition of a convex subset is quite elementary and profoundly important. It is surprising that such a simple definition can be so far reaching.

2.1 Convex subsets of R n

Consider two vectors u, v R n . The line through u and v is given parametrically as
f () = u + (v u) = (1 )u + v,
where R. Notice that f (0) = u and f (1) = v. Let

[u, v] = { f () | [0, 1]} = {(1 )u + v | [0, 1]}

denote the line segment between u and v.
DEFINITION 2.1.1
A subset S R n is called convex if

[u, v] S
for every u, v S.
EXAMPLE 2.1.2
Two subsets S1 , S2 R2 are sketched below. Here S2 is convex, but S1 is not.
9

Chapter 2. Basics

10

S1

S2

The triangle S2 in Example 2.1.2 above is a prominent member of the special

class of polyhedral convex sets. Polyhedral means cut out by finitely many
half-spaces. A non-polyhedral convex set is for example a disc in the plane:

These non-polyhedral convex sets are usually much more complicated than
their polyhedral cousins especially when you want to count the number of
integral points1 inside them. Counting the number N (r) of integral points
inside a circle of radius r is a classical and very difficult problem going back
to Gauss2 . Gauss studied the error term E(r) = | N (r) r2 | and proved that

E(r) 2 2r.
Counting integral points in polyhedral convex sets is difficult but theoretically much better understood. For example if P is a convex polygon in
the plane with integral vertices, then the number of integral points inside P
is given by the formula of Pick3 from 1899:

| P Z2 | = Area( P) +

1
B( P) + 1,
2

where B( P) is the number of integral points on the boundary of P. You can

easily check this with a few examples. Consider for example the convex poly1 Point

with coordinates in Z.
Friedrich Gauss (17771855), German mathematician. Probably the greatest mathematician that ever lived.
3 Georg Alexander Pick (18591942), Austrian mathematician.
2 Carl

2.2. The convex hull

11

gon P:

By subdivision into triangles it follows that Area( P) = 55

2 . Also, by an easy
count we get B( P) = 7. Therefore the formula of Pick shows that

| P Z2 | =

55 1
+ 7 + 1 = 32.
2
2

The polygon contains 32 integral points. You should inspect the drawing to
check that this is true!

2.2 The convex hull

Take a look at the traingle T below.
v2

v1

v
v3

Chapter 2. Basics

12

We have marked the vertices v1 , v2 and v3 . Notice that T coincides with the
points on line segments from v2 to v, where v is a point on [v1 , v3 ] i.e.
T = {(1 )v2 + ((1 )v1 + v3 ) | [0, 1], [0, 1]}

= {(1 )v2 + (1 )v1 + v3 | [0, 1], [0, 1]}

Clearly (1 ) 0, (1 ) 0, 0 and

(1 ) + (1 ) + = 1.
It is not too hard to check that (see Exercise 2)
T = {1 v1 + 2 v2 + 3 v3 | 1 , 2 , 3 0, 1 + 2 + 3 = 1}.
With this example in mind we define the convex hull of a finite set of vectors.
DEFINITION 2.2.1
Let v1 , . . . , vm R n . Then we let
conv({v1 , . . . , vm }) := {1 v1 + + m vm | 1 , . . . , m 0, 1 + + m = 1}.
We will occasionally use the notation
conv(v1 , . . . , vm )
for conv({v1 , . . . , vm }).
EXAMPLE 2.2.2
To get a feeling for convex hulls, it is important to play around with (lots of)
examples in the plane. Below you see a finite subset of points in the plane.
To the right you have its convex hull.

2.2. The convex hull

13

Let us prove that conv(v1 , . . . , vm ) is a convex subset. Suppose that u, v

conv(v1 , . . . , vm ) i.e.
u = 1 v1 + + m v m

v = 1 v1 + + m v m ,

where 1 , . . . , m , 1 , . . . , m 0 and
1 + + m = 1 + + m = 1.
Then (for 0 1)
u + (1 )v = (1 + (1 )1 )v1 + + (m + (1 )m )vm
where

(1 + (1 )1 ) + + (m + (1 )m ) =

(1 + + m ) + (1 )(1 + + m ) = + (1 ) = 1.

This proves that conv(v1 , . . . , vm ) is a convex subset. It now makes sense to

introduce the following general definition for the convex hull of an arbitrary
subset X R n .

DEFINITION 2.2.3
If X R n , then

conv( X ) =

conv(v1 , . . . , vm ).

m 1

v1 ,...,vm X

The convex hull conv( X ) of an arbitrary subset is born as a convex subset

containing X: consider u, v conv( X ). By definition of conv( X ),
u conv(u1 , . . . , ur )
v conv(v1 , . . . , vs )

for u1 , . . . , ur , v1 , . . . , vs X. Therefore u and v both belong to the convex

subset conv(u1 , . . . , ur , v1 , . . . , vs ) and
u + (1 )v conv(u1 , . . . , ur , v1 , . . . , vs ) conv( X )
where 0 1, proving that conv( X ) is a convex subset.
What does it mean for a subset S to be the smallest convex subset containing a subset X? A very natural condition is that if C is a convex subset
with C X, then C S. The smallest convex subset containing X is a subset
of every convex subset containing X!

Chapter 2. Basics

14

THEOREM 2.2.4
Let X R n . Then conv( X ) is the smallest convex subset containing X.
The theorem follows from the following proposition (see Exercise 4).
PROPOSITION 2.2.5
If S R n is a convex subset and v1 , . . . , vm S, then
conv(v1 , . . . , vm ) S.
Proof. We must show that
1 v1 + + m1 vm1 + m vm S,
where v1 , . . . , vm S, 1 , . . . , m 0 and
1 + + m1 + m = 1.
For m = 2 this is the definition of convexity. The general case is proved using
induction on m. For this we may assume that m 6= 1. Then the identity
1 v1 + + m 1 v m 1 + m v m =
1
m 1
( 1 + + m 1 )
v1 + +
v
( 1 + + m 1 )
( 1 + + m 1 ) m 1

+ m vm
and the convexity of S proves the induction step. Notice that the induction
step is the assumption that we already know conv(v1 , . . . , vm1 ) S for m
1 vectors v1 , . . . , vm1 S.

2.2.1 Intersections of convex subsets

The smallest convex subset containing X R n is the intersection of the convex subsets containing X. What do we mean by an aritrary intersection of
subsets of R n ?
The intersection of finitely many subsets X1 , . . . , Xm of R n is
X1 Xm = { x R n | x Xi , for every i = 1, . . . , m}
the subset of elements common to every X1 , . . . , Xm . This concept makes
perfectly sense for subsets Xi indexed by an arbitrary, not necessarily finite
set I. The definition is practically the same:
\

i I

Xi = { x R n | x Xi , for every i I }.

2.3. Extremal points

15

Here ( Xi )i I is called a family of subsets. In the above finite case,

{ X1 , . . . , X m } = ( X i ) i I
with I = {1, . . . , m}. With this out of the way we can state the following.
PROPOSITION 2.2.6
The intersection of a family of convex subsets of R n is a convex subset.
The proof of this proposition is left to the reader as an exercise in the definition of the intersection of subsets. This leads us to the following modern
formulation of conv( X ):
PROPOSITION 2.2.7
The convex hull conv( X ) of a subset X R n equals the convex subset
\

C,

C IX

where IX = {C R n | C convex subset and X C }.

Clearly this intersection is the smallest convex subset containing X.

2.3 Extremal points

DEFINITION 2.3.1
A point z in a convex subset C R n is called extreme or an extremal point if
z [ x, y] = z = x

or

z=y

for every x, y C. The set of extremal points in C is denoted ext(C ).

So an extremal point in a convex subset C is a point, which is not located
in the interior of a line segment in C. This is the crystal clear mathematical
definition of the intuitive notion of a vertex or a corner of set.
Perhaps the formal aspects are better illustrated in getting rid of superfluous vectors in a convex hull
X = conv(v1 , . . . , v N )
of finitely many vectors v1 , . . . , v N R n . Here a vector v j fails to be extremal
if and only if it is contained in the convex hull of the other vectors (it is superfluous). It is quite instructive to carry out this proof (see Exercise 9).
Notice that only one of the points in triangle to the right in Example 2.2.2
fails to be extremal. Here the extremal points consists of the three corners
(vertices) of the triangle.

Chapter 2. Basics

16

2.4 The characteristic cone for a convex set

To every convex subset of R n we have associated its characteristic cone4 of
(infinite) directions:
DEFINITION 2.4.1
A vector d R n is called an (infinite) direction for a convex set C R n if
x+d C
for every x C and every 0. The set of (infinite) directions for C is called the
characteristic cone for C and is denoted ccone(C ).
Just as we have extremal points we have the analogous notion of extremal
directions. An infinite direction d is extremal if d = d1 + d2 implies that d =
d1 or d = d2 for some > 0.
Why do we use the term cone for the set of infinite directions? You can
check that d1 + d2 ccone(C ) if d1 , d2 ccone(C ) and d ccone(C ) if
0 and d ccone(C ).
This leads to the next section, where we define this extremely important
class of convex sets.

2.5 Convex cones

A mathematical theory is rarely interesting if it does not provide tools or algorithms to compute with the examples motivating it. A very basic question is:
how do we decide if a vector v is in the convex hull of given vectors v1 , . . . , vm .
We would like to use linear algebra i.e. the theory of solving systems of linear equations to answer this question.To do this we need to introduce convex
cones.
DEFINITION 2.5.1
A (convex) cone in R n is a subset C R n with x + y C and x C for every
x, y C and 0.
It is easy to prove that a cone is a convex subset. Notice that any d C
is an infinite direction for C and ccone(C ) = C. An extremal ray of a convex
cone C is just another term for an extremal direction of C.
In analogy with the convex hull of finitely many points, we define the
cone generated by v1 , . . . , vm R n as
4 Some

people use the term recession cone instead of characteristic cone.

2.5. Convex cones

17

DEFINITION 2.5.2
cone(v1 , . . . , vm ) := {1 v1 + + m vm | 1 , . . . , m 0}.
Clearly cone(v1 , . . . , vm ) is a cone. Such a cone is called finitely generated.
There is an intimate relation between finitely generated cones and convex
hulls. This is the content of the following lemma.
LEMMA 2.5.3

v conv(v1 , . . . , vm )

v
1

cone

v1
1

vm
,...,
1

Proof. In Exercise 14 you are asked to prove this.

EXAMPLE 2.5.4
A triangle T is the convex hull of 3 non-collinear points

( x1 , y1 ) , ( x2 , y2 ) , ( x3 , y3 )
in the plane. Lemma 2.5.3 says that a given point ( x, y) T if and only if

x

y cone
1

x3 !
x2
x1

y1 , y2 , y3
1
1
1

(2.1)

You can solve this problem using linear algebra! Testing (2.1) amounts to
solving the system

1
x1 x2 x3
x

y1 y2 y3 2 = y
1 1 1
3
1

(2.2)

of linear equations. So ( x, y) T if and only if the unique solution to (2.2)

has 1 0, 2 0 and 3 0.
Why does (2.2) have a unique solution? This question leads to the concept
of affine independence. How do we express precisely that three points in the
plane are non-collinear?

Chapter 2. Basics

18

2.6 Affine independence

DEFINITION 2.6.1
A set {v1 , . . . , vm } R n is called affinely independent if
n

v1
1

vm
,...,
1

R n +1

is linearly independent.
As a first basic example notice that 1, 1 R are affinely independent (but
certainly not linearly independent).
LEMMA 2.6.2
Let v1 , . . . , vm R n . Then the following conditions are equivalent.
(i) v1 , . . . , vm are affinely independent.
(ii) If
1 v1 + + m v m = 0
and 1 + + m = 0, then 1 = = m = 0.
(iii)
v2 v1 , . . . , v m v1
are linearly independent in R n .
Proof. Proving (i ) = (ii ) is the definition of affine independence. For
(ii) = (iii), assume for 2 , . . . , m R that
2 (v2 v1 ) + + m (vm v1 ) = 0.
Then
1 v1 + + m = 0
with 2 = 2 , . . . , m = m and
1 = (2 + + m ).
In particular, 1 + + m = 0 and it follows that 1 = = m = 0 and
thereby 2 = = m = 0. For (iii ) = (i ) assume that
!
!
v1
vm
1
+ + m
= 0.
1
1

2.6. Affine independence

19

Then
0 = 1 v1 + + m v m = 1 v1 + + m v m ( 1 + + m ) v1

= 2 ( v2 v1 ) + + m ( v m v1 )

By assumption this implies that 2 = = m = 0 and thereby also 1 = 0.

DEFINITION 2.6.3
The convex hull
conv(v1 , . . . , vm+1 )
of m + 1 affinely independent vectors is called an m-simplex.
So a 0-simplex is a point, a 1-simplex is a line segment, a 2-simplex is
a triangle, a 3 simplex is a tetrahedron, . . . In a sense, simplices (= plural of
simplex) are building blocks for all convex sets. Below you see a picture of
(the edges of) a tetrahedron, the convex hull of 4 affinely independent points
in R3 .

Chapter 2. Basics

20

2.7 Caratheodorys theorem

A finitely generated cone cone(v1 , . . . , vm ) is called simplicial if v1 , . . . , vm are
linearly independent vectors. These cones are usually easy to manage.
Every finitely generated cone is the union of simplicial cones. This is the
content of the following very important result essentially due to Caratheodory5 .
THEOREM 2.7.1 (Caratheodory)
Let v1 , . . . , vm R n . If

v cone(v1 , . . . , vm )

then v belongs to the cone generated by a linearly independent subset of {v1 , . . . , vm }.

Proof. Suppose that
v = 1 v1 + + m v m
with 1 , . . . , m 0 and v1 , . . . , vm linearly dependent. The linear dependence means that there exists 1 , . . . , m R not all zero such that
1 v1 + + m vm = 0.

(2.3)

We may assume that at least one i > 0 multiplying (2.3) by 1 if necessary.

But
v = v 0 = v ( 1 v1 + + m v m )

= (1 1 )v1 + + (m m )vm .

(2.4)

Let
= min{ 0 | i i 0, for every i = 1, . . . , m}
o
n
i
| i > 0, i = 1, . . . , m .
= min
i
When you insert into (2.4), you discover that v also lies in the subcone generated by a proper subset of {v1 , . . . , vm }. Now keep repeating this procedure
until the proper subset consists of linearly independent vectors. Basically we
are varying in (2.4) ensuring non-negative coefficients for v1 , . . . , vm until
the first time we reach a zero coefficient in front of some v j . This (or these)
v j is (are) deleted from the generating set. Eventually we end up with a linearly independent subset of vectors from {v1 , . . . , vm }.
5 Constantin

Caratheodory (18731950), Greek mathematician.

2.8. The dual cone

21

A special case of the following corollary is: if a point in the plane is in the
convex hull of 17364732 points, then it is in the convex hull of at most 3 of
these points. When you play around with points in the plane, this seems very
obvious. But in higher dimensions you need a formal proof of the natural
generalization of this!
COROLLARY 2.7.2
Let v1 , . . . , vm R n . If

v conv(v1 , . . . , vm )

then v belongs to the convex hull of an affinely independent subset of {v1 , . . . , vm }.

Proof. If v conv(v1 , . . . , vm ), then
v
1

cone

v1
1

vm
,...,
1

by Lemma 2.5.3. Now use Theorem 2.7.1 to conclude that

v
1

 u
1
cone
1

uk
,...,
1

where
n

u1
1

uk
,...,
1

v1
1

vm
,...,
1

is a linearly independent subset. By Lemma 2.5.3 we get u conv(u1 , . . . , uk ).

But by definition
!
!
u1
uk
,...,
1
1
are linearly independent if and only if u1 , . . . , uk are affinely independent.

2.8 The dual cone

A hyperplane in R n is given by
H = { x R n | t x = 0}
for R n \ {0}. Such a hyperplane divides R n into the two half spaces

{ x R n | t x 0}

{ x R n | t x 0}.

Chapter 2. Basics

22
DEFINITION 2.8.1
If C R n is a convex cone, we call
C = { R n | t x 0, for every x C }
the dual cone of C.

The subset C R n is clearly a convex cone. One of the main results of these
notes is that C is finitely generated if C is finitely generated. If C is finitely
generated, then
C = cone(v1 , . . . , vm )
for suitable v1 , . . . , vm R n . Therefore
C = { R n | t v1 0, . . . , t vm 0}.

(2.5)

The notation in (2.5) seems to hide the basic nature of the dual cone. Let us
unravel it. Suppose that

a11
a1m
.

.. , . . . , vm = ...
v1 =

an1
anm
and

x1
.
.
=
. .
xn

Then (2.5) merely says that C is the set of solutions to the inequalities
a11 x1 + + an1 xn 0
..
.

(2.6)

a1m x1 + + anm xn 0.
The main result on finitely generated convex cones says that there always
exists finitely many solutions u1 , . . . , u N from which any other solution to
(2.6) can be constructed as
1 u 1 + + N u N ,
where 1 , . . . , N 0. This is the statement that C is finitely generated in
down to earth terms. Looking at it this way, I am sure you see that this is a
non-trivial result. If not, try to prove it from scratch!

2.8. The dual cone

23

EXAMPLE 2.8.2

In the picture above we have sketched a finitely generated cone C along with
its dual cone C . If you look closer at the drawing, you will see that
!
!
!
!
 2


1 
1

2
C = cone
,
and C = cone
,
.
1
2
2
1
Notice also that C encodes the fact that C is the intersection of the two affine
half planes
n

x
y



R2 

1
2

!t

x
y

and

x
y



R2 

2
1

!t

x
y

o
0 .

Chapter 2. Basics

24

2.9 Exercises
(1) Draw the half plane H = {( x, y)t R2 | a x + b y c} R2 for a = b =
c = 1. Show, without drawing, that H is convex for every a, b, c. Prove in
general that the half space
H = {( x1 , . . . , xn )t R n | a1 x1 + + an xn c} R n
is convex, where a1 , . . . , an , c R.
(2) Let v1 , v2 , v3 R n . Show that

{(1 )v3 + ((1 )v1 + v2 ) | [0, 1], [0, 1]} =

{1 v1 + 2 v2 + 3 v3 | 1 , 2 , 3 0, 1 + 2 + 3 = 1}.

(3) Prove that conv(v1 , . . . , vm ) is a closed subset of R n .

(4) Prove that Theorem 2.2.4 is a consequence of Proposition 2.2.5.
(5) Draw the convex hull of
S = {(0, 0), (1, 0), (1, 1)} R2 .
Write conv(S) as the intersection of 3 half planes.
(6) Let u1 , u2 , v1 , v2 R n . Show that
conv(u1 , u2 ) + conv(v1 , v2 ) = conv(u1 + v1 , u1 + v2 , u2 + v1 , u2 + v2 ).
Here the sum of two subsets A and B of R n is A + B = { x + y | x
A, y B}.
(7) Let S R n be a convex set and v R n . Show that
conv(S, v) := {(1 )s + v | [0, 1], s S}
(the cone over S) is a convex set.
(8) Prove Proposition 2.2.6.
(9) Let X = conv(v1 , . . . , v N ), where v1 , . . . , v N R n .
(i) Prove that if z X is an extremal point, then z {v1 , . . . , v N }.
(ii) Prove that v1 is not an extremal point in X if and only if
v1 conv(v2 , . . . , v N ).

2.9. Exercises

25

This means that the extremal points in a convex hull like X consists of the
indispensable vectors in spanning the convex hull.
(10) What are the extremal points of the convex subset
C = {( x, y) R2 | x2 + y2 1}
of the plane R2 ? Can you prove it?
(11) What is the characteristic cone of a bounded convex subset?
(12) Can you give an example of an unbounded convex set C with ccone(C ) =
{0}?
(13) Draw a few examples of convex subsets in the plane R2 along with their
characteristic cones, extremal points and extremal directions.
(14) Prove Lemma 2.5.3
(15) Give an example of a cone that is not finitely generated.
(16) Prove that you can have no more than m + 1 affinely independent vectors
in R m .
!

(17) The vector v =

7
4
19
8

1
8

is the convex combination

1
1

1
+
8

1
2

1
+
4

2
2

1
+
2

2
3

of 4 vectors in R2 .
(i) Write v as a convex compbination of 3 of the 4 vectors.
(ii) Can you write v as the convex combination of 2 of the vectors?
(18) Let
!
!
 2
1 
C = cone
,
.
1
2
(i) Show that

C = cone

!
!
1
2 
,
.
2
1

Chapter 2. Basics

26
(ii) Suppose that
C = cone

!
!
a
b 
,
,
c
d

where
a b
c d

is an invertible matrix. How do you compute C ?

Chapter 3

Separation
A linear function f : R n R is given by f (v) = t v for R n . For every
R we have an affine hyperplane given by
H = { v R n | f ( v ) = }.
We will usually omit affine in front of hyperplane. Such a hyperplane divides R n into two (affine) half spaces given by
H = { v R n | f ( v ) }

H = { v R n | f ( v ) } .

Two given subsets S1 and S2 of R n are separated by H if S1 H and S2 H .

A separation of S1 and S2 given by a hyperplane H is called proper if S1 * H
or S2 * H (the separation is not too interesting if S1 S2 H).
A separation of S1 and S2 given by a hyperplane H is called strict if S1
H< and S2 H> , where
H< = { v R n | f ( v ) < }

H> = { v R n | f ( v ) > } .

Separation by half spaces shows the important result that (closed) convex
sets are solutions to systems of (perhaps infinitely many) linear inequalities.
Let me refer you to Appendix B for refreshing the necessary concepts from
analysis like infimum, supremum, convergent sequences and whatnot.
The most basic and probably most important separation result is strict
separation of a closed convex set C from a point x 6 C. We need a small
preliminary result about closed (and convex) sets.

27

Chapter 3. Separation

28

LEMMA 3.0.1
Let F R n be a closed subset. Then there exists x0 F such that
n 
o

| x0 | = inf | x|x F .

If F in addition is convex, then x0 is unique.

Proof. Let

o
n 

= inf | x| x F .

We may assume from the beginning that F is bounded. Now construct a

sequence ( xn ) of points in F with the property that | xn | < 1/n. Such
a sequence exists by the definition of infimum. Since F is bounded, ( xn )
has a convergent subsequence ( xni ). Let x0 be the limit of this convergent
subsequence. Then x0 F, since F is closed. Also, as x 7 | x| is a continuous
function from F to R we must have | x0 | = . This proves the existence of x0 .
If F in addition is convex, then x0 is unique: suppose that y0 F is another
point with |y0 | = | x0 |. Consider
z=

1
1
1
( x0 + y0 ) = x0 + y0 F.
2
2
2

But in this case, |z| = 21 | x0 + y0 | 12 | x0 | + 21 |y0 | = | x0 |. Therefore | x0 + y0 | =

| x0 | + |y0 |. From the triangle inequality it follows that x0 are y0 collinear
i.e. there exists R such that x0 = y0 . Then = 1. In both cases we
have x0 = y0 .
COROLLARY 3.0.2
Let F R n be a closed subset and z R n . Then there exists x0 F such that

n
o

| x0 z| = inf | x z|x F .
If F in addition is convex, then x0 is unique.

Proof. If F is closed (convex) then

F z = {x z | z F}
is also closed (convex). Now the results follow from applying Lemma 3.0.1
to F z.
If F R n is a closed subset with the property that to each point of R n
there is a unique nearest point in F, then one may prove that F is convex!
This result is due to Bunt (1934)1 and Motzkin (1935).
1 L.

N. H. Bunt, Dutch mathematician

3.1. Separation of a point from a closed convex set

29

3.1 Separation of a point from a closed convex set

The following lemma is at the heart of almost all of our arguments.
LEMMA 3.1.1
Let C be a closed convex subset of R n and let

where x0 C. If 0 6 C, then

o
n 

| x0 | = inf | x| x C ,
x0t z > | x0 |2 /2

for every z C.
Proof. First notice that x0 exists and is unique by Lemma 3.0.1. We argue by
contradiction. Suppose that z C and
x0t z | x0 |2 /2

(3.1)

Then using the definition of x0 and the convexity of C we get for 0 1

that

| x0 |2 |(1 ) x0 + z|2 = (1 )2 | x0 |2 + 2(1 ) x0t z + 2 |z|2

( 1 ) 2 | x0 |2 + ( 1 ) | x0 |2 + 2 | z |2 ,

where the assumption (3.1) is used in the last inequality. Subtracting | x0 |2

from both sides gives
0 2| x0 |2 + 2 | x0 |2 + (1 )| x0 |2 + 2 |z|2 = (| x0 |2 + |z|2 ).
Dividing by > 0 leads to

| x0 |2 | z |2
for every 0 < 1. Letting 0, this implies that x0 = 0 contradicting
our assumption that 0 6 C.
If you study Lemma 3.1.1 closer, you will discover that we have separated
{0} from C with the hyperplane
1
{z R n | x0t z = | x0 |2 }.
2

Chapter 3. Separation

30

x0
C
0

xt0 z = |x0 |2 /2

There is nothing special about the point 0 here. The general result says
the following.
THEOREM 3.1.2
Let C be a closed convex subset of R n with v 6 C and let x0 be the unique point in
C closest to v. Then
1
( x0 v ) t ( z v ) > | x0 v |2
2
for every z C: the hyperplane H = { x R n | t x = } with = x0 v and
= ( x0 v)t v + | x0 v|2 /2 separates {v} strictly from C.
Proof. Let C = C v = { x v | x C }. Then C is closed and convex and
0 6 C . The point closest to 0 in C is x0 v. Now the result follows from
Lemma 3.1.1 applied to C .
With this result we get one of the key properties of closed convex sets.
THEOREM 3.1.3
A closed convex set C R n is the intersection of the half spaces containing it.
Proof. We let J denote the set of all half spaces
H = { x R n | t x }
with C H . One inclusion is easy:
C

H J

H .

In the degenerate case, where C = R n we have J = and the above intersection is R n . Suppose that there exists
x

H J

H \ C.

(3.2)

3.2. Supporting hyperplanes

31

Then Theorem 3.1.2 shows the existence of a hyperplane H with C H and

x 6 H . This contradicts (3.2).
This result tells an important story about closed convex sets. A closed
half space H R n is the set of solutions to a linear inequality
a1 x1 + + an xn b.
Therefore a closed convex set really is the set of common solutions to a (possibly infinite) set of linear inequalities. If C happens to be a (closed) convex
cone, we can say even more.
COROLLARY 3.1.4
Let C R n be a closed convex cone. Then
C=

{ x R n | t x 0}.

Proof. If C is contained in a half space { x R n | t x } we must have

0, since 0 C. We cannot have t x > 0 for any x C, since this would
imply that t (x) = (t x) for . As x C for 0 this
violates t x for every x C. Therefore C and = 0. Now the result
follows from Theorem 3.1.3.

3.2 Supporting hyperplanes

With some more attention to detail we can actually prove that any convex set
C R n (not necessarily closed) is always contained on one side of an affine
hyperplane touching C at its boundary. Of course here you have to assume
that C 6= R n .
First we need to prove that the closure of a convex subset is also convex.
PROPOSITION 3.2.1
Let S R n be a convex subset. Then the closure, S, of S is a convex subset.
Proof. Consider x, y S. We must prove that z := (1 ) x + y S for
0 1. By definition of the closure S there exists convergent sequences
( xn ) and (yn ) with xn , yn S such that xn x and yn y. Now form the
sequence ((1 ) xn + yn ). Since S is convex this is a sequence of vectors in
S. The convergence of ( xn ) and (yn ) allows us to conclude that

(1 ) xn + yn z.
Since z is the limit of a convergent sequence with vectors in S, we have shown
that z S.

Chapter 3. Separation

32

DEFINITION 3.2.2
A supporting hyperplane for a convex set C R n at a boundary point z C is
hyperplane H with z H and C H . Here H is called a supporting half space
for C at z.
Below you see an example of a convex subset C R2 along with supporting hyperplanes at two of its boundary points u and v. Can you spot any
difference between u and v?

THEOREM 3.2.3
Let C R n be a convex set and z C. Then there exists a supporting hyperplane
for C at z.
Proof. The fact that z C means that there exists a sequence of points (zn )
with zn 6 C, such that zn z (z can be approximated outside of C). Proposition 3.2.1 says that C is a convex subset. Therefore we may use Lemma 3.0.1
to conclude that C contains a unique point closest to any point. For each zn
we let xn C denote the point closest to zn and put
un =

zn xn
.
|zn xn |

Theorem 3.1.2 then shows that

utn ( x zn ) >

1
|zn xn |
2

(3.3)

for every x C. Since (un ) is a bounded sequence, it has a convergent subsequence. Let u be the limit of this convergent subsequence. Then (3.3) shows
that H = { x R n | ut x = ut z} is a supporting hyperplane for C at z, since
|zn xn | |zn z| 0 as n .

3.3. Separation of disjoint convex sets

33

3.3 Separation of disjoint convex sets

THEOREM 3.3.1
Let C1 , C2 R n be disjoint (C1 C2 = ) convex subsets. Then there exists a
separating hyperplane
H = {u R n | t u = }
for C1 and C2 .
Proof. The trick is to observe that C1 C2 = { x y | x C1 , y C2 } is a
convex subset and 0 6 C1 C2 . T here exists R n \ {0} with
t ( x y) 0
or x y for every x C1 , y C2 . Here is why. If 0 6 C1 C2 this is
a consequence of Lemma 3.1.1. If 0 C1 C2 we get it from Theorem 3.2.3
with z = 0.
Therefore 1 2 , where
1 = inf{t x | x C1 }

2 = sup{t y | y C2 }

and
H = {u R n | t u = 1 }
is the desired hyperplane.
The separation in the theorem does not have to be proper (example?).
However, if C1 6= or C2 6= then the separation is proper (why?).

3.4 An application
We give the following application, which is a classical result [4] due to Gordan2 dating back to 1873.
THEOREM 3.4.1
Let A be an m n matrix. Then precisely one of the following two conditions holds
(i) There exists an n-vector x, such that
Ax < 0.
2 Paul

Gordan (18371912), German mathematician.

Chapter 3. Separation

34
(ii) There exists a non-zero m-vector y 0 such that
yt A = 0
Proof. Define the convex subsets
C1 = { Ax | x R n }

and

C2 = {y R m | y < 0}

of R m . If Ax < 0 is unsolvable, then C1 C2 = and Theorem 3.3.1 implies

the existence of a separating hyperplane
L = { x R n | t x = }
such that
C1 { x R n | t x }

C2 { x R n | t x }.

(3.4)
(3.5)

These containments force strong retrictions on and : 0 by (3.4), since

0 C1 and 0 by (3.5) as t y 0 for y 0 and y C2 . Therefore = 0.
Also from (3.5) we must have 0 to ensure that t y holds for every y
in the unbounded set C2 . We claim that the result follows by putting y = .
Assume on the contrary that A 6= 0. Then the containment
C1 = { Ax | x R n } { x R n | t x 0}
fails!

3.5 Farkas lemma

The lemma of Farkas3 is an extremely important result in the theory of convex
sets. Farkas published his result in 1901 (see [1]). The lemma itself may be
viewed as the separation of a finitely generated cone
C = cone(v1 , . . . , vr )

(3.6)

from a point v 6 C. In the classical formulation this is phrased as solving

linear equations with non-negative solutions. There is no need to use our
powerful separation results in proving Farkas lemma. It follows quite easily
3 Gyula

Farkas (18471930), Hungarian mathematician.

3.5. Farkas lemma

35

from Fourier-Motzkin elimination. Using separation in this case, only complicates matters and hides the polyhedral nature of the convex subset in
(3.6).
In teaching convex sets last year, I tried to convince the authors of a certain engineering textbook, that they really had to prove, that a finitely generated cone (like the one in (3.6)) is a closed subset of R n . After 3 or 4 email
notes with murky responses, I gave up.
The key insight is the following little result, which is the finite analogue
of Corollary 3.1.4.
LEMMA 3.5.1
A finitely generated cone
C = cone(v1 , . . . , vr ) R n
is a finite interesection of half spaces i.e. there exists an m n matrix A, such that
C = {v R n | Av 0}.
Proof. Let B denote the n r-matrix with v1 , . . . , vr as columns. Consider the
polyhedron
P = {( x, y) Rr +n | y = Bx, x 0}

 y Bx 0 )


( x, y) Rr +n  Bx y 0

x
0

and let : Rr +n R n be the projection defined by ( x, y) = y. Notice that

P is deliberately constructed so that ( P) = C.
Theorem 1.2.2 now implies that C = ( P) = {y R n | Ay b} for
b R m and A an m n matrix. Since 0 C we must have b 0. In fact b = 0
has to hold: an x C with Ax  0 means that a coordinate, z = ( Ax) j > 0.
Since x C for every 0 this would imply z = ( A(x)) j is not bounded
for and we could not have Ax b for every x C (see also Exercise
5).
A cone of the form {v R n | Av 0} is called polyhedral (because it
is a polyhedron in the sense of Definition 1.2.1). Lemma 3.5.1 shows that
a finitely generated cone is polyhedral. A polyhedral cone is also finitely
generated. We shall have a lot more to say about this in the next chapter.
The following result represents the classical Farkas lemma in the language of matrices.

Chapter 3. Separation

36

LEMMA 3.5.2 (Farkas)

Let A be an m n matrix and b R m . Then precisely one of the following two
conditions is satisfied.
(i) The system
Ax = b
of linear equations is solvable with x R n with non-negative entries.
(ii) There exists y R m such that
yt A 0

and

yt b < 0.

Proof. The properties (i ) and (ii ) cannot be true at the same time. Suppose
that they both hold. Then we get that
yt b = yt ( Ax) = (yt A) x 0
since yt A 0 and x 0. This contradicts yt b < 0. The real surprise is the
existence of y if Ax = b cannot be solved with x 0. Let v1 , . . . , vm denote
the m columns in A. Then the key observation is that Ax = b is solvable with
x 0 if and only if
b C = cone(v1 , . . . , vm ).
So if Ax = b, x 0 is non-solvable we must have b 6 C. Lemma 3.5.1 shows
that b 6 C implies you can find y R n with yt b < 0 and yt A 0 simply by
using the description of C as a finite intersection of half planes.

3.6. Exercises

37

3.6 Exercises
(1) Give an example of a non-proper separation of convex subsets.
(2) Let
B1 = {( x, y) | x2 + y2 1}

B2 = {( x, y) | ( x 2)2 + y2 1}
(a) Show that B1 and B2 are closed convex subsets of R2 .
(b) Find a hyperplane properly separating B1 and B2 .
(c) Can you separate B1 and B2 strictly?
(d) Put B1 = B1 \ {(1, 0)} and B2 = B2 \ {(1, 0)}. Show that B1 and B2 are
convex subsets. Can you separate B1 from B2 strictly? What about B1
and B2 ?
(3) Let S be the square with vertices (0, 0), (1, 0), (0, 1) and (1, 1) and P =
(2, 0).
(i) Find the set of hyperplanes through (1, 21 ), which separate S from P.
(ii) Find the set of hyperplanes through (1, 0), which separate S from P.
(iii) Find the set of hyperplanes through ( 23 , 1), which separate S from P.
(4) Let C1 , C2 R n be convex subsets. Prove that
C1 C2 := { x y | x C1 , y C2 }
is a convex subset.
(5) Take another look at the proof of Theorem 1.2.2. Show that
( P ) = { x R n 1 | A x 0}
if P = { x R n | Ax 0}, where A and A are matrices with n and n 1
columns respectively.
(6) Show using Farkas that

x
2 0 1
y =
1 1
2
z
!

is unsolvable with x 0, y 0 and z 0.

1
0

Chapter 3. Separation

38

(7) With the assumptions of Theorem 3.3.1, is the following strengthening:

C1 { x R n | t x < }

and

C2 { x R n | t x }

true? If not, give a counterexample. Can you separate C1 and C2 strictly

if C1 6= and C1 C2 = ? How about C1 C2 6= ?
(8) Let C ( R n be a convex subset. Prove that C 6=
(9) Let C ( R n be a closed convex subset. Define dC : R n C by dC (v) = z,
where z C is the unique point with

o
n

|v z| = inf |v x| x C .
(a) Prove that dC is a continuous function.

n
o

(b) Let z0 C and B = x R n  | x z0 | R for R > 0. Show that
max{dC ( x) | x B} = R.

(10) Find all the supporting hyperplanes of the triangle with vertices (0, 0), (0, 2)
and (1, 0).

Chapter 4

Polyhedra
You already know from linear algebra that the set of solutions to a system
a11 x1 + + an1 xn = 0
..
.

(4.1)

a1m x1 + + anm xn = 0
of (homogeneous) linear equations can be generated from a set of basic solutions v1 , . . . , vr R n , where r n. This simply means that the set of solutions
to (4.1) is

{1 v1 + + r vr | i R } = cone(v1 , . . . , vr ).
Things change dramatically when we replace = with and ask for a set of
basic solutions to a set of linear inequalities
a11 x1 + + an1 xn 0
..
.

(4.2)

a1m x1 + + anm xn 0.
The main result in this chapter is that we still have a set of basic solutions
v1 , . . . , vr . However here the set of solutions to (4.2) is

{1 v1 + + r vr | i R and i 0} = cone(v1 , . . . , vr )

(4.3)

and r can be very big compared to n. In addition we have to change our

notion of a basic solution (to an extremal generator).
Geometrically we are saying that an intersection of half spaces like (4.2)
is generated by finitely many rays as in (4.3). This is a very intuitive and very
39

Chapter 4. Polyhedra

40

powerful mathematical result. In some cases it is easy to see as in

0
y
0
z 0

(4.4)

Here the set of solutions is

cone

1
0
0 !

0 , 1 , 0
0
0
1

(4.5)

What if we add the inequality x y + z 0 to (4.4)? How does the set of

solutions change in (4.5)? With this extra inequality


1
0


0 and 0
0
1

are no longer (basic) solutions. The essence of our next result is to describe
this change.

4.1 The double description method

The double description method is a very clever algorithm for solving (homogeneous) linear inequalities. It first appeared in [7] with later refinements in
[3]. It gives a nice inductive proof of the classical theorem of Minkowski1 and
Weyl2 on the structure of polyhedra (Theorem 4.5.1).
The first step of the algorithm is computing the solution set to one inequality in n variables like
3x + 4y + 5z 0

(4.6)

in the three variables x, y and z. Here the solution set is the set of vectors
with 3x + 4y + 5z = 0 along with the non-negative multiples of just one
vector ( x0 , y0 , z0 ) with
3x0 + 4y0 + 5z0 < 0.
Concretely the solution set to (4.6) is

4
0
4
0
1 !

cone 3 , 3 , 5 , 5 , 1 .
0
0
4
4
1
1 Hermann
2 Hermann

Minkowski (18641909), German mathematician.

Weyl (18851955), German mathematician.

(4.7)

4.1. The double description method

41

The double description method is a systematic way of updating the solution set when we add further inequalities.

4.1.1 The key lemma

The lemma below is a bit technical, but its main idea and motivation are very
simple: We have a description of the solutions to a system of m linear inequalities in basis form. How does this solution change if we add a linear
inequality? If you get stuck in the proof, then please take a look at the example that follows. Things are really quite simple (but nevertheless clever).
LEMMA 4.1.1
Consider
C=



x Rn 

for a1 , . . . , am R n . Suppose that

a1t x
atm x

0 o
..
.

(4.8)

C = cone(v | v V )
for V = {v1 , . . . , v N }. Then
C { x R n | at x 0} = cone(w | w W ),
where (the inequality at x 0 with a R n is added to (4.8))
W ={v V | at v < 0}

(4.9)

{( at u)v ( at v)u | u, v V, at u > 0 and at v < 0}.

Proof. Let C = C { x R n | at x 0} and C = cone(w|w W ). Then

C C as the generators ( at u)v ( at v)u are designed so that they belong to
C (check this!). We will prove that C C . Suppose that z C . Then we
may write
z = 1 v1 + + N v N .
Now let Jz = {vi | i > 0, at vi < 0} and Jz+ = {vi i | i > 0, at vi > 0}. We
prove that z C by induction on the number of elements m = | Jz Jz+ | in
Jz Jz+ . If m = 0, then z = 0 and everything is fine. If | Jz+ | = 0 we are also
done. Suppose that u Jz+ . Since at z 0, Jz cannot be empty. Let v Jz
and consider
z = z (( at u)v ( at v)u)
for > 0. By varying > 0 suitably you can hit the sweet spot where
| Jz+ Jz | < | Jz+ Jz |. From here the result follows by induction.

Chapter 4. Polyhedra

42

EXAMPLE 4.1.2
Now we can write up what happens to the solutions to (4.4) when we add
the extra inequality x y + z 0. It is simply a matter of computing the set
W of new generators in (4.9). Here


1
0
0 o
n 1


a = 1 and V = 0 , 1 , 0 .
1
0
0
1
Therefore

W=

0
1
0 o

1 , 1 , 1 .
0
0
1

EXAMPLE 4.1.3
Suppose on the other hand that the inequality x y z 0 was added to
(4.4). Then

0
1
1 o
n 0

W = 1 , 0 , 1 , 0 .
0
1
0
1

All of these generators are basic solutions. You cannot leave out a single
of them. Let us add the inequality x 2y + z 0, so that we wish to solve

z
x y z
x 2y +z

0
0
0
0
0

(4.10)

Here we apply Lemma 4.1.1 with a = (1, 2, 1)t and V = W above and the
new generators are (in transposed form)

= (0, 1, 0)
= (1, 1, 0)
(0, 1, 0) + 2(0, 0, 1) = (0, 1, 2)
2(0, 1, 0) + 2(1, 0, 1) = (2, 2, 2)

(1, 1, 0) + (0, 0, 1) = (1, 1, 1)

2(1, 1, 0) + (1, 0, 1) = (3, 2, 1)
You can see that the generators (1, 1, 1) and (2, 2, 2) are superfluous, since
1
1
(1, 1, 1) = (0, 1, 2) + (3, 2, 1).
3
3

4.2. Extremal and adjacent rays

43

We would like to have a way of generating only the necessary basic or

extremal solutions when adding a new inequality. This is the essence of the
following section.

4.2 Extremal and adjacent rays

Recall that an extremal ray in a convex cone C is an element v C, such that
v = u1 + u2 with u1 , u2 C implies v = u1 or v = u2 for some 0. So
the extremal rays are the ones necessary for generating the cone. You cannot
leave any of them out. We need some general notation. Suppose that A is an
m d with the m rows a1 , . . . , am R d . For a given x R d we let
I ( x) = {i | ati x = 0} {1, . . . , m}.
For a given subset J {1, . . . , m} we let A J denote the matrix with rows
( a j | j J ) and Ax 0 denotes the collection a1t x 0, . . . , atm x 0 of linear
inequalities.
PROPOSITION 4.2.1
Let
C = { x R d | Ax 0}

(4.11)

where A is an m d matrix of full rank d. Then v C is an extremal ray if and

only if the rank of A I is d 1, where I = I (v).
Proof. Suppose that the rank of A I is < d 1, where v is an extremal ray with
I = I (v). Then we may find a non-zero x R d with A I x = 0 and vt x = 0.
Consider
1
1
(4.12)
v = (v x) + (v + x).
2
2
For small > 0 you can check the inequalities in (4.11) and show that v
x C. Since vt x = 0, v cannot be a non-zero multiple of v x or v + x.
Now the identity in (4.12) contradicts the assumption that v is an extremal
ray. Therefore if v is an extremal ray it follows that the rank of A I is d 1.
On the other hand if the rank of A I is d 1, then there exists a non-zero
vector w R d with

{ x R d | A I x = 0} = {w | R }.
If v = u1 + u2 for u1 , u2 C \ {0}, then we must have I (u1 ) = I (u2 ) = I.
Therefore v, u1 and u2 are all proportional to w. We must have v = u1 or
v = u2 for some > 0 proving that v is an extremal ray.

Chapter 4. Polyhedra

44
DEFINITION 4.2.2
Two extremal rays u and v in
C = { x R d | Ax 0}

are called adjacent if the rank of AK is d 2, where K = I (u) I (v).

Geometrically this means that u and v span a common face of the cone.
We will, however, not give the precise definition of a face in a cone.
The reason for introducing the concept of adjacent extremal rays is rather
clear when you take the following extension of Lemma 4.1.1 into account.
LEMMA 4.2.3
Consider
C=



x Rn 

a1t x

0 o
..
.

atm x 0

for a1 , . . . , am R n . Let V be the set of extremal rays in C and a R n . Then

W ={v V | at v < 0}

{( at u)v ( at v)u | u, v adjacent in V, with at u > 0 and at v < 0}.

is the set of extremal rays in

C { x R n | a t x 0}.
Proof. If you compare with Lemma 4.1.1 you will see that we only need to
prove for extremal rays u and v of C that
w : = ( at u ) v ( at v) u
is extremal if and only if u and v are adjacent, where at u > 0 and at v < 0. We
assume that the rank of the matrix A consisting of the rows a1 , . . . , am is n.
Let A denote the matrix with rows a1 , . . . , am , am+1 := a. We let I = I (u), J =
I (v) and K = I (w) with respect to the matrix A . Since w is a positive linear
combination of u and v we know that ati w = 0 if and only if ati u = ati v = 0,
where ai is a row of A. Therefore
K = ( I J ) { m + 1}.

(4.13)

If u and v are adjacent then A I J has rank n 2. The added row a in A

satisfies at w = 0 and the vector a is not in the span of the rows in A I J . This
shows that the rank of AK is n 1. Therefore w is extremal. Suppose on the

4.2. Extremal and adjacent rays

45

other hand that w is extremal. This means that AK has rank n 1. By (4.13)
this shows that the rank of A I J has to be n 2 proving that u and v are
adjacent.
We will now revisit our previous example and weed out in the generators
using Lemma 4.2.3.
EXAMPLE 4.2.4

z
x y z

0
0
0
0

(4.14)

Here a1 = (1, 0, 0), a2 = (0, 1, 0), a3 = (0, 0, 1), a4 = (1, 1, 1). The
extremal rays are
V = {(0, 1, 0), (1, 1, 0), (0, 0, 1), (1, 0, 1)}
We add the inequality x 2y + z 0 and form the matrix A with the extra
row a5 := a = (1, 2, 1). The extremal rays are divided into two groups
V = { v | a t v < 0} { v | a t v > 0}
corresponding to
V = {(0, 1, 0), (1, 1, 0)} {(0, 0, 1), (1, 0, 1)}.
You can check that
I ((0, 1, 0)) = {1, 3}

I ((1, 1, 0)) = {3, 4}

I ((0, 0, 1)) = {1, 2}

I ((1, 0, 1)) = {2, 4}

From this you see that (1, 1, 0) is not adjacent to (0, 0, 1) and that (0, 1, 0) is not
adjacent to (1, 0, 1). These two pairs correspond exactly to the superfluous
rays encountered in Example 4.1.3. So Lemma 4.2.3 tells us that we only
need to add the vectors

(0, 1, 0) + 2(0, 0, 1) = (0, 1, 2)

2(1, 1, 0) + (1, 0, 1) = (3, 2, 1)
to {(0, 1, 0), (1, 1, 0)} to get the new extremal rays.

Chapter 4. Polyhedra

46

4.3 Farkas: from generators to half spaces

Now suppose that C = cone(v1 , . . . , vm ) R n . Then we may write C =
{ x | Ax 0} for a suitable matrix A. This situation is dual to what we have
encountered finding the basic solutions to Ax 0. The key for the translation
is Corollary 3.1.4, which says that
C=

Ha .

(4.15)

aC

The dual cone to C is given by

C = {a R n | at v1 0, . . . , at vm 0},
which is in fact the solutions to a system of linear inequalities. By Lemma
4.1.1 (and Lemma 4.2.3) you know that these inequalities can be solved using
the double description method and that
C = cone( a1 , . . . , ar )
for certain (extremal) rays a1 , . . . , ar in C . We claim that
C = H a1 H a r
so that the intersection in (4.15) really is finite! Let us prove this. If
a = 1 a1 + + j a j C
with i > 0, then
H a1 H a j H a ,
as a1t x 0, . . . , atj x 0 for every x C implies (1 a1t + + j atj ) x = at x
0. This proves that
H a1 H a r =

Ha = C.

aC

EXAMPLE 4.3.1
In Example 4.1.3 we showed that the solutions of

z
x y z
x 2y +z

0
0
0
0
0

(4.16)

4.3. Farkas: from generators to half spaces

47

are generated by the extremal rays

V = {(0, 1, 0), (1, 1, 0), (0, 1, 2), (3, 2, 1)}.
Let us go back from the extremal rays above to inequalities. Surely five inequalities in (4.16) are too many for the four extremal rays. We should be able
to find four inequalities doing the same job. Here is how. The dual cone to
the cone generated by V is given by
y
x +y
y +2z
3x +2y +z

0
0
0
0

We solve this system of inequalities using Lemma 4.1.1. The set of solutions
to
y
0
x +y
0
y +2z 0
is generated by the extremal rays V = {(2, 2, 1), (1, 0, 0), (0, 0, 1)}. We
add the fourth inequality 3x + 2y + z 0 (a = (3, 2, 1)) and split V according
to the sign of at v:
V = {(2, 2, 1)} {(1, 0, 0), (0, 0, 1)}.
This gives the new extremal rays
3(1, 0, 0) + 3(2, 2, 1) = (3, 6, 3)

3(0, 0, 1) + (2, 2, 1) = (2, 2, 2)

and the extremal rays are {(1, 0, 0), (0, 0, 1), (1, 2, 1), (1, 1, 1)} showing that the solutions of (4.16) really are the solutions of

0
z 0
x 2y +z 0
x y z 0.

We needed four inequalities and not five! Of course we could have spotted
this from the beginning noting that the inequality y 0 is a consequence
of the inequalities x 0, x 2y + z 0 and x y z 0.

Chapter 4. Polyhedra

48

4.4 Polyhedra: general linear inequalities

The set of solutions to a general system
a11 x1 + + a1n xn b1
..
.

(4.17)

am1 x1 + + amn xn bm
of linear inequalities is called a polyhedron. It may come as a surprise to you,
but we have already done all the work for studying the structure of polyhedra. The magnificent trick is to adjoin an extra variable xn+1 and rewrite
(4.17) into the homogeneous system

a11 x1 + + a1n xn b1 xn+1 0

..
.

(4.18)

am1 x1 + + amn xn bm xn+1 0

xn+1 0.

The key observation is that

( x1 , . . . , xn ) solves (4.17)

( x1 , . . . , xn , 1) solves (4.18).

But (4.18) is a system of (homogeneous) linear inequalities as in (4.2) and we

know that the solution set is

cone

u1
0

,...,

ur
0

v1
,
1

vs
,...,
1

!!

(4.19)

where u1 , . . . , ur , v1 , . . . , vs R n . Notice that we have divided the solutions

of (4.18) into xn+1 = 0 and xn+1 6= 0. In the latter case we may assume that
xn+1 = 1 (why?). The solutions with xn+1 = 0 in (4.18) correspond to the
solutions C of the homogeneous system
a11 x1 + + a1n xn 0
..
.
am1 x1 + + amn xn 0.
In particular the solution set to (4.17) is bounded if C = {0}.

4.5. The decomposition theorem for polyhedra

49

4.5 The decomposition theorem for polyhedra

You cannot expect (4.17) to always have a solution. Consider the simple example
x1

x 2
Adjoining the extra variable y this lifts to the system
xy 0

x + 2y 0

y 0

Here x = 0 and y = 0 is the only solution and we have no solutions with

y = 1 i.e. we may have s = 0 in (4.19). This happens if and only if (4.17) has
no solutions.
We have now reached the main result of these notes: a complete characterization of polyhedra due to Minkowski in 1897 (see [5]) and Weyl in
1935 (see [8]). Minkowski showed that a polyhedron admits a description
as a sum of a polyhedral cone and a polytope. Weyl proved the other implication: a sum of a polyhedral cone and a polytope is a polyhedron. You
probably know by now that you can use the double description method and
Farkas lemma to reason about these problems.
THEOREM 4.5.1 (Minkowski, Weyl)
A non-empty subset P R n is a polyhedron if and only if it is the sum P = C + Q
of a polytope Q and a polyhedral cone C.
Proof. A polyhedron P is the set of solutions to a general system of linear
inequalities as in (4.17). If P is non-empty, then s 1 in (4.19). This shows
that
P = {1 u1 + + r ur + 1 v1 + + s vs | i 0, j 0, and 1 + + s = 1}
or
P = cone(u1 , . . . , ur ) + conv(v1 , . . . , vs ).

(4.20)

On the other hand, if P is the sum of a cone and a polytope as in (4.20), then
we define P R n+1 to be the cone generated by
!
!
!
!
u1
ur
v1
vs
,...,
,
,...,
0
0
1
1

Chapter 4. Polyhedra

50
If
P = cone

1
1

,...,

N
N

where 1 , . . . , n R n and 1 , . . . , n R, we know from 4.3 that

!

n x
o
n +1  t

P=
R
 1 x + 1 z 0, . . . , tN x + N z 0 .
z

Therefore
But an element x R n belongs to P if and only if ( x, 1) P.

o
n

P = x R n  1t x + 1 0, . . . , tN x + N 0

o
n
n t
= x R  1 x 1 , . . . , tN x N
is a polyhedron.

4.6 Extremal points in polyhedra

There is a natural connection between the extremal rays in a cone and the
extremal points in a polyhedron P = { x R n | Ax b}. Let a1 , . . . , am
denote the rows in A and let b = (b1 , . . . , bm )t . With this notation we have

P = { x R n | Ax b} =



x Rn 

a1t x b1
..
.
atm x bm

For z P we define the submatrix

Az = {ai | ati z = bi },
consisting of those rows where the inequalities are equalities (binding constraints) for z. The following result shows that a polyhedron only contains
finitely many extremal points and gives a method for finding them.
PROPOSITION 4.6.1
z P is an extremal point if and only if Az has full rank n.
Proof. The proof is very similar to Proposition 4.2.1 and we only sketch the
details. If z P and the rank of Az is < n, then we may find u 6= 0 with
Az u = 0. We can then choose > 0 sufficiently small so that z u P
proving that
z = (1/2)(z + u) + (1/2)(z u)

4.6. Extremal points in polyhedra

51

cannot be an extremal point. This shows that if z is an extremal point, then

Az must have full rank n. On the other hand if Az has full rank n and z =
(1 )z1 + z2 with 0 < < 1 for z1 , z2 P, then we have for a row ai in Az
that
ati z = (1 ) ati z1 + ati z2 .
As ati z1 ati z = bi and ati z2 bi we must have ati z1 = ati z2 = bi = ati z. But
then Az (z z1 ) = 0 i.e. z = z1 .
EXAMPLE 4.6.2
Find the extremal points in

P=

x
y

1
0 o

x

2
R  2 1
1 .
y
1
2
1

We will find the first extremal point and leave the computation of the other
extremal points to the reader. First we try and see if we can find z P with
!
1 1
A z = { a1 , a2 } =
.
2 1
If z = ( x, y)t this leads to solving

x y = 0

2x y = 1,

giving ( x, y) = (1/3, 1/3). Since 1/3 + 2 (1/3) = 1/3 < 1 we see that
z = (1/3, 1/3) P. This shows that z is an extremal point in P. Notice that
the rank of Az is 2.
DEFINITION 4.6.3
A subset
L = {u + tv | t R }
with u, v R n and v 6= 0 is called a line in R n .
THEOREM 4.6.4
Let P = { x R n | Ax b} 6= . The following conditions are equivalent
(i) P contains an extremal point.
(ii) The characteristic cone
ccone( P) = { x R n | Ax 0}
does not contain a line.

Chapter 4. Polyhedra

52
(iii) P does not contain a line.

Proof. If z P and ccone( P) contains a line L = {v + tu | t R }, we must

have Au = 0. Therefore
z = 1/2(z + u) + 1/2(z u),
where z u P and none of the points in P are extremal. Suppose on the
other hand that ccone( P) does not contain a line. Then P does not contain a
line, since a line L as above inside P implies Au = 0 making it a line inside
ccone( P).
Now assume that P does not contain a line and consider z P. If Az
has rank n then z is an extremal point. If not we can find a non-zero u with
Az u = 0. Since P does not contain a line we must have
z + u 6 P
for sufficiently big. Let
0 = sup{ | z + u P}
and
z1 = z + 0 u.
Then z1 P and the rank of Az1 is strictly greater than the rank of Az . If the
rank of Az1 is not n we continue the procedure. Eventually we will hit an
extremal point.
COROLLARY 4.6.5
Let c R n and P = { x R n | Ax b}. If
M = sup{ct x | x P} <
and ext( P) 6= , then there exists x0 ext( P) such that
ct x0 = M.
Proof. The non-empty set
Q = { x R n | ct x = M } P
is a polyhedron not containing a line, since P does not contain a line. Therefore Q contains an extremal point z. But such an extremal point is also an
extremal point in P. If this was not so, we could find a non-zero u with

4.6. Extremal points in polyhedra

53

Az u = 0. For > 0 small we would then have z u P. But this implies

that ct u = 0 and z u Q. The well known identity
z=

1
1
(z + u) + (z u)
2
2

shows that z is not an extremal point in Q. This is a contradiction.

Now we have the following refinement of Theorem 4.5.1 for polyhedra
with extremal points.
THEOREM 4.6.6
Let P = { x R n | Ax b} be a polyhedron with ext( P) 6= . Then
P = conv(ext( P)) + ccone( P).
Proof. The definition of ccone( P) shows that
conv(ext( P)) + ccone( P) P.
You also get this from ccone( A) = { x R n | Ax 0}. If P 6= conv(ext( P)) +
ccone( P), there exists z P and c R n such that ct z > ct x for every x
conv(ext( P)) + ccone( P). But this contradicts Corollary 4.6.5, which tells us
that there exists an extremal point z0 in P with
ct z0 = sup{ct x | x P}.

Chapter 4. Polyhedra

54

4.7 Exercises
(1) Verify that the set of solutions to (4.6) is as described in (4.7).
(2) Find the set of solutions to the system
x +

z 0
y + z 0
z 0

of (homogeneous) linear inequalities.

(3) Express the convex hull

1/4

1/2
1/4
1 o
n

conv 1/4 , 1/4 , 1/2 , 1 R3
1/2
1/4
1/4
1
as a polyhedron (an intersection of halfspaces).
(4) Convert the inequalities
x + y 1
x + y 1
x 2y 2
to a set of 4 homogeneous inqualities by adjoining an extra variable z.
Show that the original inequalities are unsolvable using this.
(5) Is the set of solutions to

x + 2y z 1
x y z 2
2x y z 1
y + z 1
x y + z 0
x + y
1
bounded in R3 ?
(6) Let P1 and P2 be polytopes in R n . Show that
P1 + P2 = {u + v | u P1 , v P2 }
is a polytope. Show that the sum of two polyhedra is a polyhedron.

4.7. Exercises

55

(7) Give an example of a polyhedron with no extremal points.

(8) Let P = { x R n | Ax b} be a polyhedron, where A is an m n matrix
and b R m . How many extremal points can P at the most have?
(9) Show that a polyhedron is a polytope (bounded) if and only if it is the
convex hull of its extremal points.
(10) Let K be a closed convex set in R n . Show that K contains a line if and only
if ccone(K ) contains a line.
(11) Give an example showing that Theorem 4.6.6 is far from true if ext( P) =
.
(12) Let
P = conv(u1 , . . . , ur ) + cone(v1 , . . . , vs )
be a polyhedron, where u1 , . . . , ur , v1 , . . . , vs R n . Show for c R n that
if M = sup{ct x | x P} < , then
sup ct x = sup ct x,
xP

x K

where K = conv(u1 , . . . , ur ). Does there exist x0 P with ct x0 = M?

(13) Eksamen 2005, opgave 1.
(14) Eksamen 2004, opgave 1.
(15) Eksamen 2007, opgave 6.

Appendix A

Linear (in)dependence
The concept of linear (in)dependence is often a stumbling block in introductory courses on linear algebra. When presented as a sterile definition in an
abstract vector space it can be hard to grasp. I hope to show here that it
is simply a fancy way of restating a quite obvious fact about solving linear
equations.

A.1

Linear dependence and linear equations

You can view the equation

3x + 5y = 0
as one linear equation with two unknowns. Clearly x = y = 0 is a solution.
But there is also a non-zero solution with x = 5 and y = 3. As one further
example consider
2x + y z = 0

(A.1)

x+y+z = 0

Here we have 3 unknowns and only 2 equations and x = 2, y = 3 and z = 1

is a non-zero solution.
These examples display a fundamental fact about linear equations. A
system
a11 x1 + + a1n xn = 0

a21 x1 + + a2n xn = 0
..
.

am1 x1 + + amn xn = 0
57

Appendix A. Linear (in)dependence

58

of linear equations always has a non-zero solution if the number of unknowns

n is greater than the number n of equations i.e. n > m.
In modern linear algebra this fact about linear equations is coined using
the abstract term linear dependence:
A set of vectors {v1 , . . . , vn } R m is linearly dependent if n > m.
This means that there exists 1 , . . . , n R not all 0 such that
1 v1 + + n vn = 0.
With this language you can restate the non-zero solution x = 2, y = 3
and z = 1 of (A.1) as the linear dependence
!
!
!
!
2
1
1
0
2
+ (3)
+1
=
.
1
1
1
0
Let us give a simple induction proof of the fundamental fact on (homogeneous) systems of linear equations.
THEOREM A.1.1
The system
a11 x1 + + a1n xn = 0

a21 x1 + + a2n xn = 0
..
.

(A.2)

am1 x1 + + amn xn = 0
of linear equations always has a non-zero solution if m < n.
Proof. The induction is on m the number of equations. For m = 1 we have
1 linear equation
a1 x1 + + a n x n = 0
with n variables where n > m = 1. If ai = 0 for some i = 1, . . . , n then clearly
xi = 1 and x j = 0 for j 6= i is a non-zero solution. Assume otherwise that
ai 6= 0 for every i = 1, . . . , m. In this case x1 = 1, x2 = a1 /a2 , x3 = =
xn = 0 is a non-zero solution.
If every ai1 = 0 for i = 1, . . . , m, then x1 = 1, x2 = = xn = 0 is a
non-zero solution in (A.2). Assume therefore that a11 6= 0 and substitute
x1 =

1
( a12 x2 a1n xn )
a11

A.2. The rank of a matrix

59

x1 into the remaining m 1 equations. This gives the following system of

m 1 equations in the n 1 variables x2 , . . . , xn
a21
a21
a12 ) x2 + + ( a2n
a1n ) xn = 0
a11
a11
..
.
am1
am1
a12 ) x2 + + ( amn
a1n ) xn = 0
( am2
a11
a11

( a22

(A.3)

Since n 1 > m 1, the induction assumption on m gives the existence of a

non-zero solution ( a2 , . . . , an ) to (A.3). Now

1
( a12 a2 a1n an ), a2 , . . . , an )
a11

is a non-zero solution to our original system of equations. This can be checked

quite explicitly (Exercise 4).

A.2

The rank of a matrix

A system
a11 x1 + + a1n xn = 0

a21 x1 + + a2n xn = 0
..
.

(A.4)

am1 x1 + + amn xn = 0
of linear equations can be conveniently presented in the matrix form

x1
0
. .
. .
A
. = . ,
xn
0
where A is the m n matrix

a11 a1n
.
..
..
..
.
.

.
am1 amn

We need to attach a very important invariant to A called the rank of the matrix. In the context of systems of linear equations the rank is very easy to
understand. Let us shorten our notation a bit and let
Li ( x) = ai1 x1 + + ain xn .

Appendix A. Linear (in)dependence

60
Then the solutions to (A.4) are

S = { x R n | L1 ( x) = 0, . . . , Lm ( x) = 0}.
Suppose that m = 3. If one of the equations say L3 ( x) is expressible by the
other equations say as
L3 ( x) = L1 ( x) + L2 ( x),
with , R, then we dont need the equation L3 in S. This is because
L1 ( x ) = 0
L2 ( x ) = 0
L3 ( x ) = 0

L1 ( x ) = 0
L2 ( x ) = 0

Clearly you see that L3 ( x) = 0 if L1 ( x) = 0 and L2 ( x) = 0. In this case

you can throw L3 out without changing S. Informally the rank of the matrix
A is the minimal number of equations you end up with after throwing excess equations away. It is not too hard to make this into a very well defined
concept. We will only use the following very important consequence.
THEOREM A.2.1
Let A be an m n matrix of rank < n. Then there exists a non-zero vector u R n
with Au = 0.
Proof. You may view S = { x R n | Ax = 0} as the set of solutions to

x1
0
. .
. .
A
. = . .
xn
0
By our informal definition of rank we know that

S = { x R n | A I x = 0},
where A I is an m n- matrix consisting of a subset of the rows in A with
m = the rank of A. Now the result follows by applying Theorem A.1.1.

A.3. Exercises

A.3

61

Exercises

(1) Find 1 , 2 , 3 R not all 0 with

!
!
1
3
1
+ 2
+ 3
2
4

5
6

!
0
.
0

(2) Show that a non-zero solution ( x, y, z) to (A.1) must have x 6= 0, y 6= 0

and z 6= 0. Is it possible to find 1 , 2 , 3 in Exercise 1, where one of 1 , 2
or 3 is 0?
(3) Can you find a non-zero solution to
x+y+z = 0
x y + z = 0,
where
(i) x = 0?
(ii) y = 0?
(iii) z = 0?
(iv) What can you say in general about a system
ax + by + cz = 0
a x + b y + c z = 0
of linear equations in x, y and z, where a non-zero solution always
has x 6= 0, y 6= 0 and z 6= 0?
(4) Check carefully that

1
( a12 a2 a1n an ), a2 , . . . , an )
a11

really is a non-zero solution to (A.2) in the proof of Theorem A.1.1.

(5) Compute the rank of the matrix

1 2 3

4 5 6

14 19 24 .

6 9 12

Appendix B

Analysis
In this appendix we give a very brief overview of the basic concepts of introductory mathematical analysis. Focus is directed at building things from
scratch with applications to convex sets. We have not formally constructed
the real numbers.

B.1 Measuring distances

The limit concept is a cornerstone in mathematical analysis. We need a formal
way of stating that two vectors are far apart or close together.
Inspired by the Pythagorean formula for the length of the hypotenuse
in a triangle with a right angle, we define the length | x| of a vector x =
( x1 , . . . , xn )t R n as
q

| x| =

x12 + + x2n .

Our first result about the length is the following lemma called the inequality
of Cauchy-Schwarz. It was discovered by Cauchy1 in 1821 and rediscovered
by Schwarz2 in 1888.
LEMMA B.1.1
For x = ( x1 , . . . , xn )t R n and y = (y1 , . . . , yn )t R n the inequality

( xt y)2 = ( x1 y1 + + xn yn )2 ( x12 + + x2n )(y21 + + y2n ) = | x|2 |y|2

holds. If

( xt y)2 = ( x1 y1 + + xn yn )2 = ( x12 + + x2n )(y21 + + y2n ) = | x|2 |y|2 ,

then x and y are proportional i.e. x = y for some R.
1 Augustin
2 Hermann

Louis Cauchy (17891857), French mathematician

Amandus Schwarz (18431921), German mathematician

63

Appendix B. Analysis

64
Proof. For n = 2 you can explicitly verify that

( x12 + x22 )(y21 + y22 ) ( x1 y1 + x2 y2 )2 = ( x1 y2 y1 x2 )2 .

(B.1)

This proves that inequality for n = 2. If equality holds, we must have



x y 
 1 1
x1 y2 y1 x2 = 
 = 0.
 x2 y2 

This implies as you can check that there exists R such that x1 = y1 and
x2 = y2 .
The formula in (B.1) generalizes for n > 2 by induction (Exercise 1) to

( x12 + + x2n )(y21 + + y2n ) ( x1 y1 + + xn yn )2 =

2

(B.2)

( x1 y2 y1 x2 ) + + ( x n 1 y n y n 1 x n ) ,

where the last sum is over the squares of the 2 2 minors in the matrix
A=

x1 x2 x n 1 x n
y1 y2 y n 1 y n

The formula in (B.2) proves the inequality. If

( x12 + + x2n )(y21 + + y2n ) = ( x1 y1 + + xn yn )2 ,

then (B.2) shows that all the 2 2-minors in A vanish. The existence of
giving proportionality between x and y is deduced as for n = 2.

R3

If you know about the vector (cross) product u v of two vectors u, v

you will see that the method of the above proof comes from the formula

| u |2 | v |2 = | u t v |2 + | u v |2 .
One of the truly fundamental properties of the length of a vector is the
triangle inequality (also inspired by the one in 2 dimensions).
THEOREM B.1.2
For two vectors x, y R n the inequality

| x + y| | x | + |y|
holds.

B.2. Sequences

65

Proof. Lemma B.1.1 shows that

| x + y |2 = ( x + y ) t ( x + y )

= | x|2 + |y|2 + 2xt y

| x|2 + |y|2 + 2| x||y|

= (| x| + |y|)2

proving the inequality.

We need to define how far vectors are apart.
DEFINITION B.1.3
The distance between x and y in R n is defined as

| x y |.
From Theorem B.1.2 you get formally

| x z| = | x y + y z| | x y| + |y z|
for x, y, z R n . This is the triangle inequality for distance saying that the
shorter way is always along the diagonal instead of the other two sides in a
triangle:
y
|x y|

|y z|

x
|x z|

B.2 Sequences
Limits appear in connection with (infinite) sequences of vectors in R n . We
need to formalize this.
DEFINITION B.2.1
A sequence in R n is a function f : {1, 2, . . . } R n . A subsequence f I of f is f
restricted to an infinite subset I {1, 2, . . . }.

Appendix B. Analysis

66

A sequence f is usually denoted by an infinite tuple ( xn ) = ( x1 , x2 , . . . ),

where xn = f (n). A subsequence of ( xn ) is denoted ( xni ), where I = {n1 , n2 , . . . }
and n1 < n2 < . A subsequence f I is in itself a sequence, since it is
given by picking out an infinite subset I of {1, 2, . . . } and then letting f I ( j) =
f ( n j ) = xn j .
This definition is quite formal. Once you get to work with it, you will
discover that it is easy to handle. In practice sequences are often listed as
1, 2, 3, 4, 5, 6, . . .

(B.3)

2, 4, 6, 8, 10, . . .

(B.4)

2, 6, 4, 8, 10, . . .

(B.5)

1 1 1
, , , ...
2 3 4

(B.6)

1,

Formally these sequences are given in the table below

x1

x2

x3

x4

x5

x6

(B.3)
(B.4)

1
2

2
4

3
6

4
8

5
10

6
12

(B.5)
(B.6)

2
1

10

12

1
2

1
3

1
4

1
5

1
6

The sequence (zn ) in (B.4) is a subsequence of the sequence in ( xn ) (B.3).

You can see this by noticing that zn = x2n and checking with the definition of
a subsequence. Why is the sequence in (B.5) not a subsequence of ( xn )?
DEFINITION B.2.2
A sequence ( xn ) of real numbers is called increasing if x1 x2 and decreasing if x1 x2 .
The sequences (B.3) and (B.4) are increasing. The sequence (B.6) is decreasing, whereas (B.5) is neither increasing nor decreasing.
You probably agree that the following lemma is very intuitive.
LEMMA B.2.3
Let T be an infinite subset of {1, 2, . . . } and F a finite subset. Then T \ F is infinite.
However, infinity should be treated with the greatest respect in this setting. It sometimes leads to really surprising statements such as the following.
LEMMA B.2.4
A sequence ( xn ) of real numbers always contains an increasing or a decreasing subsequence.

B.2. Sequences

67

Proof. We will prove that if ( xn ) does not contain an increasing subsequence,

then it must contain a decreasing subsequence ( xni ), with
x n1 > x n2 > x n3 >
The key observation is that if ( xn ) does not contain an ascending subsequence, then there exists N0 such that X N > xn for every n > N. If this was
not so, ( xn ) would contain an increasing subsequence. You can try this out
yourself!
The first element in our subsequence will be X N . Now we pick N1 > N
such that xn < X N1 for n > N1 . We let the second element in our subsequence
be x N1 and so on. We use nothing but Lemma B.2.3 in this process. If the
process should come to a halt after a finite number of steps xn1 , xn2 , . . . , xnk ,
then the sequence ( x j ) with j nk must contain an increasing subsequence,
which is also an increasing subsequence of ( xn ). This is a contradiction.
DEFINITION B.2.5
A sequence ( xn ) converges to x (this is written xn x) if

> 0 N N n N : | x xn | .
Such a sequence is called convergent.
This is a very formal (but necessary!) way of expressing that . . .
the bigger n gets, the closer xn is to x.
You can see that (B.3) and (B.4) are not convergent, whereas (B.6) converges to 0. To practice the formal definition of convergence you should (Exercise 4) prove the following proposition.
PROPOSITION B.2.6
Let ( xn ) and (yn ) be sequences in R n . Then the following hold.
(i) If xn x and xn x , then x = x .
(ii) If xn x and yn y, then
xn + yn x + y

and

xn yn xy.

Before moving on with the more interesting aspects of convergent sequences we need to recall the very soul of the real numbers.

Appendix B. Analysis

68

B.2.1

Supremum and infimum

A subset S R is bounded from above if there exists U R such that x U

for every x S. Similarly S is bounded from below if there exists L R such
that L x for every x S.
THEOREM B.2.7
Let S R be a subset bounded from above. Then there exists a number (supremum)
sup(S) R, such that
(i) x sup(S) for every x S.
(ii) For every > 0, there exists x S such that
x > sup(S) .
Similarly we have for a bounded below subset S that there exists a number (infimum)
inf(S) such that
(i) x inf(S) for every x S.
(ii) For every > 0, there exists x S such that
x < inf(S) + .
Let S = { xn | n = 1, 2, . . . }, where ( xn ) is a sequence. Then ( xn ) is
bounded from above from if S is bounded from above, and similarly bounded
from below if S is bounded from below.
LEMMA B.2.8
Let ( xn ) be a sequence of real numbers. Then ( xn ) is convergent if
(i) ( xn ) is increasing and bounded from above.
(ii) ( xn ) is decreasing and bounded from below.
Proof. In the increasing case sup{ xn | n = 1, 2, . . . } is the limit. In the decreasing case inf{ xn | n = 1, 2, . . . } is the limit.

B.3 Bounded sequences

A sequence of real numbers is called bounded if it is both bounded from
above and below.

B.4. Closed subsets

69

COROLLARY B.3.1
A bounded sequence of real numbers has a convergent subsequence.
Proof. This is a consequence of Lemma B.2.4 and Lemma B.2.8.
We want to generalize this result to R m for m > 1. Surprisingly this is not
so hard once we use the puzzling properties of infinite sets. First we need to
define bounded subsets here.
A subset S R m is called bounded if there exists R > 0 such that | x| R
for every x S. This is a very natural definition. You want your set S to be
contained in vectors of length bounded by R.
THEOREM B.3.2
A bounded sequence ( xn ) in R m has a convergent subsequence.
Proof. Let the sequence be given by
xn = ( x1n , . . . , xmn ) R m .
The m sequences of coordinates ( x1n ), . . . , ( xmn ) are all bounded sequences
of real numbers. So the first one ( x1n ) has a convergent subsequence ( x1ni ).
Nothing is lost in replacing ( xn ) with its subsequence ( xni ). Once we do this
we know that the first coordinate converges! Move on to the sequence given
by the second coordinate and repeat the procedure. Eventually we end with
a convergent subsequence of the original sequence.

B.4 Closed subsets

DEFINITION B.4.1
A subset F R n is closed if for any convergent sequence ( xn ) with
(i) ( xn ) F
(ii) xn x
we have x F.
Clearly R n is closed. Also an arbitrary intersection of closed sets is closed.
DEFINITION B.4.2
The closure of a subset S R n is defined as
S = { x R n | xn x, where ( xn ) S is a convergent sequence}.

Appendix B. Analysis

70

The points of S are simply the points you can reach with convergent sequences from S. Therefore the following result must be true.
PROPOSITION B.4.3
Let S R n . Then S is closed.
Proof. Consider a convergent sequence (ym ) S with ym y. We wish to
prove that y S. By definition there exists for each ym a convergent sequence
( xm,n ) S with
xm,n ym .
For each m we pick xm := xm,n for n big enough such that |ym xm | < 1/m.
We claim that xm y. This follows from the inequality

| y x m | = | y y m + y m x m | | y y m | + | y m x m |,
using that ym y and |ym xm | being small for m 0.
The following proposition comes in very handy.
PROPOSITION B.4.4
Let F1 , . . . , Fm R n be finitely many closed subsets. Then
F := F1 Fm R n
is a closed subset.
Proof. Let ( xn ) F denote a convergent sequence with xn x. We must
prove that x F. Again distributing infinitely many elements in finitely
many boxes implies that one box must contain infinitely many elements.
Here this means that at least one of the sets
N i = {n N | xn Fi }, i = 1, . . . , m
must be infinite. If N k inifinite then { x j | j N k } is a convergent (why?)
subsequence of ( xn ) with elements in Fk . But Fk is closed so that x Fk F.

B.5 The interior and boundary of a set

The interior S of a subset S R n consists of the elements which are not
limits of sequences of elements outside S. The boundary S consists of the
points which can be approximated both from the inside and outside. This is
formalized in the following definition.

B.6. Continuous functions

71

DEFINITION B.5.1
Let S R n . Then the interior S of S is
R n \ R n \ S.
The boundary S is
S R n \ S.

B.6 Continuous functions

DEFINITION B.6.1
A function
f : S Rn ,
where S R m is called continuous if f ( xn ) f ( x) for every convergent sequence
( xn ) S with xn x S.
We would like our length function to be continuous. This is the content
of the following proposition.
PROPOSITION B.6.2
The length function f ( x) = | x| is a continuous function from R n to R.
Proof. You can deduce from the triangle inequality that

|| x| |y|| | x y|
for every x, y R n . This shows that

| f ( x) f ( xn )| | x xn |
proving that f ( xn ) f ( x) if xn x. Therefore f ( x) = | x| is a continuous
function.
The following result is very useful for proving that certain subsets are
closed.
LEMMA B.6.3
If f : R m R n is continuous then
f 1 ( F ) = { x R n | f ( x ) F } R m
is a closed subset, where F is a closed subset of R n .
Proof. If ( xn ) f 1 ( F ) with xn x, then f ( xn ) f ( x) by the continuity of
f . As F is closed we must have f ( x) F. Therefore x f 1 ( F ).

Appendix B. Analysis

72

B.7 The main theorem

A closed and bounded subset C R n is called compact. Even though the
following theorem is a bit dressed up, its applications are many and quite
down to Earth. Dont fool yourself by the simplicity of the proof. The proof
is only simple because we have the right definitions.
THEOREM B.7.1
Let f : C R n be a continuous function, where C R m is compact. Then
f (C ) = { f ( x) | x C } is compact in R n .
Proof. Suppose that f (C ) is not bounded. Then we may find a sequence
( xn ) C such that | f ( xn )| n. However, by Theorem B.3.2 we know that
( xn ) has a convergent subsequence ( xni ) with xni x. Since C is closed we
must have x C. The continuity of f gives f ( xni ) f ( x). This contradicts
our assumption that | f ( xni )| ni after all, | f ( x)| is finite.
Proving that f (C ) is closed is almost the same idea: suppose that f ( xn )
y. Then again ( xn ) must have a convergent subsequence ( xni ) with xni x
C. Therefore f ( xni ) f ( x) and y = f ( x), showing that f (C ) is closed.
One of the useful consequences of this result is the following.
COROLLARY B.7.2
Let f : C R be a continuous function, where C R n is a compact set. Then
f (C ) is bounded and there exists x, y C with
f ( x) = inf{ f ( x) | x C }

f (y) = sup{ f ( x) | x C }.

In more boiled down terms, this corollary says that a real continuous
function on a compact set assumes its minimum and its maximum. As an
example let
f ( x, y) = x18 y113 + 3x cos( x) + ex sin(y).
A special case of the corollary is that there exists points ( x0 , y0 ) and ( x1 , y1 )
in B, where
B = {( x, y) | x2 + y2 117}
such that
f ( x0 , y0 ) f ( x, y)

f ( x1 , y1 ) f ( x, y)

(B.7)

B.7. The main theorem

73

for every ( x, y) B. You may say that this is clear arguing that if ( x0 , y0 ) does
not satisfy (B.7), there must exist ( x, y) B with f ( x, y) < f ( x0 , y0 ). Then
put ( x0 , y0 ) := ( x, y) and keep going until (B.7) is satisfied. This argument
is intuitive. I guess that all we have done is to write it down precisely in the
language coming from centuries of mathematical distillation.

Appendix B. Analysis

74

B.8 Exercises
(1) Use induction to prove the formula in (B.2).
(2)

(i) Show that

2ab a2 + b2
for a, b R.

(ii) Let x, y R n \ {0}, where x = ( x1 , . . . , xn )t and y = (y1 , . . . , yn )t .

Prove that
x2
y2
xi yi
i2 + i2
2
| x | |y|
| x|
|y|
for i = 1, . . . , n.

(iii) Deduce the Cauchy-Schwarz inequality from (2ii).

(3) Show formally that 1, 2, 3, . . . does not have a convergent subsequence.
Can you have a convergent subsequence of a non-convergent sequence?
(4) Prove Proposition B.2.6.
(5) Let S be a subset of the rational numbers Q, which is bounded from
above. Of course this subset always has a supremum in R. Can you
give an example of such an S, where sup(S) 6 Q.
(6) Let S = R \ {0, 1}. Prove that S is not closed. What is S?
(7) Let S1 = { x R | 0 x 1}. What is S1 and S1 ?

Let S2 = {( x, y) R2 | 0 x 1, y = 0}. What is S2 and S2 ?

(8) Let S R n . Show that S S and S S = S. Is S contained in S?

Let U = R n \ F, where F R n is a closed set. Show that U = U and

U U = .

(9) Show that

|| x| |y|| | x y|
for every x, y R n .
(10) Give an example of a subset S R and a continuous function f : S R,
such that f (S) is not bounded.

Appendix C

Polyhedra in standard form

A polyhedron defined by P = { x R n | Ax = b, x 0} is said to be in
standard form. Here A is an m n-matrix and b an m-vector. Notice that
P=


xR 
n

Ax
b
Ax b
x
0

(C.1)

A polyhedron P in standard form does not contain a line (why?) and

therefore always has an extremal point if it is non-empty. Also
ccone( P) = { x R n | Ax = 0, x 0}.

C.1

Extremal points

The determination of extremal points of polyhedra in standard form is a direct (though somewhat laborious) translation of Proposition 4.6.1.
THEOREM C.1.1
Let A be an m n matrix af rank m. There is a one to one correspondence between
extremal points in
P = { x R n | Ax = b, x 0}
and m linearly independent columns B in A with B1 b 0. The extremal point
corresponding to B is the vector with zero entries except at the coordinates corresponding the columns of B. Here the entries are B1 b.
Proof. Write P as in (C.1):
n


xR 
n

Axb
75

Appendix C. Polyhedra in standard form

76
where

A = A ,
I

is an (2m + n) n matrix with I the n n-identity matrix. For any z P, Az

always contains the first 2m rows giving us rank m by assumption. If z P
is an extremal point then Az has rank n. So an extremal point corresponds
to adding n m of the rows of I in order to obtain rank n. Adding these
n m rows of the n n identity matrix amounts to setting the corresponding
variables = 0. The m remaining (linearly independent!) columns of A give
the desired m m matrix B with B1 b 0.
We will illustrate this principle in the following example.
EXAMPLE C.1.2
Suppose that

P=

! x
x 
 1 2 3
y 
y =
4 5 6
z
z

!
o
1
, x, y, z 0 .
3

According to Theorem C.1.1, the possible extremal points in P are given by

1 2
4 5

! 1

1
3

2 3
5 6

! 1

1
3

!
1/3
,
1/3
!
1
.
1/3

1 3
4 6

! 1

1
3

!
1/2
,
1/6

From this you see that P only has the two extremal points

x1
1/3

y1 = 1/3
z1
0

and

x2
1/2

y2 = 0 .
z2
1/6

If you consider the polyhedron

P=

! x
x 
 1 2 3
y 
y =
4 5 6
z
z

!
o
1
, x, y, z 0 ,
1

C.2. Extremal directions

77

then the possible extremal points are given by

! 1
!
!
! 1
1 2
1
1
1 3
=
,
4 5
1
1
4 6
! 1
!
!
2 3
1
1
=
.
5 6
1
1

1
1

!
1/2
,
1/2

What does this imply about Q?

C.2

Extremal directions

The next step is to compute the extremal infinite directions for a polyhedron
in standard form.
THEOREM C.2.1
Let A be an m n matrix of rank m. Then the extremal infinite directions for
P = { x R n | Ax = b, x 0}
are in correspondence with ( B, a j ), where B is a subset of m linearly independent
columns in A, a j a column not in B with B1 a j 0. The extremal direction corresponding to ( B, a j ) is the vector with entry 1 on the j-th coordinate, B1 a j on the
coordinates corresponding to B and zero elsewhere.
Proof. Again let
P=
where



x Rn 

A x b

A = A ,
I

is an (2m + n) n matrix with I the n n-identity matrix. The extremal

directions in P are the extremal rays in the characteristic cone

n
o

ccone( P) = x R n  A x 0
,

Extremal rays correspond to z ccone( P) where the rank of Az is n 1. As

before the first 2m rows of A are always in Az and add up to a matrix if
rank m. So we must add an extra n m 1 rows of I. This corresponds
to picking out m + 1 columns B of A such that the matrix B has rank m.
Therefore B = ( B, a j ), where B is a matrix of m linearly independent columns
and a j 6 B. This pair defines an extremal ray if and only if B v = 0 for a nonzero v 0. This is equivalent with B1 a j 0.

Appendix C. Polyhedra in standard form

78

EXAMPLE C.2.2
The following example comes from the 2004 exam. Consider the polyhedron

( x

P = y R3
z

x + 2y 3z = 1
3x + y 2z = 1
x
0
y
0
z 0

in standard form. Compute its infinite extremal directions and extremal

points.
The relevant matrix above is
!
1 2 3
A=
3 1 2
The procedure according to Theorem C.2.1 is to pick out invertible 2 2 submatrices B of A and check if B1 a 0 with a the remaining column in A.
Here are the computations:
!
! 1
!
1 2
3
51
=
75
3 1
2
1 3
3 2
2 3
1 2

! 1

2
1

! 1

1
3

Therefore the extremal rays are

1
1
5

7
5 ,
1

!
7
.
5

and

5
7

71
57

1

7 .
5

Using Theorem C.1.1 you can check that the only extremal point of P is
1
5

2
5 .
0

This shows that

1
1
( 1
1
5
5
7

2

7
P = 5 + 1 5 + 2 1 + 3 7
5
0
1
5
7

1 , 2 , 3 0 .

C.3. Exercises

C.3

79

Exercises

1. Let P be a non-empty polyhedron in standard form. Prove

(a) P does not contain a line.
(b) P has an extremal point.
(c)
ccone( P) = { x R n | Ax = 0, x 0}.
2. This problem comes from the exam of 2005. Let

(
y

5

P=
z R

u
v

x
y 2z u
x +2y +4z 2u +v
x
y
z
u
v

=
=

1
1
0
0
0
0
0

Compute the extremal points and directions of P. Write P as the sum of

a convex hull and a finitely generated convex cone.

Bibliography
[1] Julius Farkas, Theorie der einfachen Ungleichungen, J. Reine Angew. Math.
124 (1901), 127.
[2] Joseph Fourier, Solution dune question perticuli`ere du calcul des inegalites,
Nouveau Bulletin des Sciences par la Societe philomatique de Paris
(1826), 317319.
[3] Komei Fukuda and Alain Prodon, Double description method revisited,
Combinatorics and computer science (Brest, 1995), Lecture Notes in Comput. Sci., vol. 1120, Springer, Berlin, 1996, pp. 91111.
[4] Paul Gordan, Ueber die Auflosung linearer Gleichungen mit reellen Coefficienten, Math. Ann. 6 (1873), no. 1, 2328.
[5] Hermann Minkowski, Allgemeine Lehrsatze uber

die konvexen Polyeder,

Nachrichten von der koniglichen

Gesellschaft der Wissenschaften zu

Gottingen,

mathematisch-physikalische Klasse (1897), 198219.

[6] T. S. Motzkin, Two consequences of the transposition theorem on linear inequalities, Econometrica 19 (1951), 184185.
[7] T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall, The double
description method, Contributions to the theory of games, vol. 2, Annals of
Mathematics Studies, no. 28, Princeton University Press, Princeton, N. J.,
1953, pp. 5173.
[8] Hermann Weyl, Elementare Theorie der konvexen Polyeder, Commentarii
Mathematici Helvetici 7 (1935), 290306.

81

Index
Az , 58
H< , 31
H> , 31
H , 31
H , 31
I ( x) indices of equality (cone),
50

S , for subset S R n , 81
ccone(C ), 19
cone(v1 , . . . , vm ), 20
conv( X ), 16
conv({v1 , . . . , vm }), 14
conv(v1 , . . . , vm ), 14
ext(C ), 18
S, for subset S R n , 80
S, for subset S R n , 81
u v for u, v R n , vii
u v, 74
ut v for u, v R n , vii

has convergent subsequence,

79
sequences, 79
set in R n , 79
Caratheodorys theorem, 23
Caratheodory, Constantin, 23
Cauchy, Augustin Louis, 73
Cauchy-Schwarz inequality, 73
characteristic cone, 19
circle problem of Gauss, 12
closed subset, 80
intersection of, 81
closure of a subset, 80
compact subset, 83
cone
polyhedral, 41
continuous function, 82
on compact subset, 83
assumes min and max, 83
convergent sequence, 77
convex cone, 19
dual, 25
extremal ray, 19
finitely generated, 20
is closed, 40
simplicial, 23
convex hull, 14
of finitely many vectors, 14
of subset, 16

adjacent extremal rays, 51

affine half space, 31
affine hyperplane, 31
affine independence, 21
boundary, 81
bounded, 78
from above, 78
from below, 78
sequence
83

Index

84
convex subset
closure of, 36
definition, 11
intersection of half spaces, 35
cross product, 74
distance in R n , 75
double description method, 46
dual cone, 25
extremal direction, 19
in polyhedron of standard form,
89
extremal point, 18
in polyhedra, 59
in polyhedron, 58
in polyhedron of standard form,
87
extremal ray, 19
adjacent, 51
condition, 50
Farkas lemma, 39
Farkas, Gyula, 39
finitely generated cone, 20
Fourier, J., 5
Fourier-Motzkin elimination, 5
Gauss, Carl Friedrich, 12
Gordans theorem, 38
Gordan, Paul, 38
half space, 31
half space, 25
affine, 31
supporting, 36
homogeneous system, vii
hyperplane, 25
affine, 31
supporting, 36

independence
affine, 21
infimum, 78
integral points
in polygon, 12
inside circle, 12
interior, 81
intersection of half spaces, 35
intersection of subsets, 17
length function
is continuous, 82
length of a vector, 73
limit concept, 73
line in R n , 60
line segment, 11
linear inequalities
homogeneous, vii
linear dependence, 66
linear equations, 66
linear function, 31
linear independence, 65
linear inequalites
homogeneous, vii
linear inequalities, vii, 2
solving using elimination, 3
magnificent trick, 56
mathematical analysis, 73
Minkowski, Hermann, 46, 57
Minkowski-Weyl theorem, 57
Motzkin, T. S., 5
Ostrowski, A., 5
Picks formula, 12
Pick, Georg Alexander, 12
polyhedral convex sets, 12
polyhedron, 5
in standard form, 87

Index
of standard form
extremal directions in, 89
extremal points in, 87
polyheral cone, 41
polytope, 5
Pythagorean formula, 73
rank of a matrix, 68
recession cone, 19
Schwarz, Hermann Amandus, 73
separation of convex subsets, 31
disjoint convex sets, 37
from a point, 33
proper, 31
strict, 31
sequence, 76
convergent, 77
decreasing, 77
increasing, 77
simplex, 22
simplicial cone, 23
standard form of polyhedron, 87
subsequence, 76
supporting half space, 36
supporting hyperplane, 36
existence of, 37
supremum, 78
tetrahedron, 22
triangle inequality, 74
vector product, 74
Weyl, Hermann, 46, 57

85