Before we proceed further, in the above corollary, we observe that the property of a linear function was used only in a small part of the proof of corollary 8 in last post. However, observe that the proof (for maximum) would follow through if the function
satisfies the following properties:
,
.
- sub-additive property:

Such functions are called as sub-additive functions. So a sub-additive function which is continuous achieves its maximum on a vertex of a compact convex set. An example of sub-additive function is the norm
. Another example is the support function of a set (we will look at this function later).
We will now look at some interesting examples of extreme points and maximization of linear functionals. We will first begin with the following motivational example.
Examples:
Assignment problem (AP): The AP arises in many contexts and is an example of binary optimization. Here we will motivate the problem in the context of wireless and later generalize the notion.
OFDM (orthogonal frequency division multiplexing) is a multi-carrier modulation which is being used in 4G networks. In OFDM,the data is modulated over different tones in such a way that orthogonality can be maintained across tones.
In general, a BS tower serves multiple users. When using OFDM, the BS generally has to decide the allocation of different tones to different users (OFDMA). Assume for now there are
frequency tones and there are
users. In general the users are distributed in space. Hence each frequency tone will have a different “channel” with respect a user. So let
denote the channel of tone
from the BS to the user
. A good channel in general indicates a higher data rate on that particular tone. A simple map from the channel quality to the data rate obtained is
. So the BS wants to allocate one frequency tone per user and allocate all the tones, such that the sum rate is maximized. For example if
, a sample allocation is given by
, which implies the first tone is allocated to the third user, the second tone to the second user, the third to the fourth user and the fourth to the first user. Observe that any allocation is just a permutation of the integers
. So mathematically the BS should find a permutation
such that the allocated sum rate

is maximized. Observe that if the BS has check for every permutation of
before it can find the permutation that maximizes the sum rate. Suppose there are
tones, then the search space is approximately
which is huge.
In a little while using the extreme points and Krein-Milman theorem, we will come up with a smarter way of solving this problem in polynomial complexity.
We will now start looking more closely at the vertices (extreme points) of a polyhedron. Most of the material is taken from AB. We will first begin with the following theorem that characterizes the vertices of a polyhedron in terms of linear dependence of the vectors.
Proof: Let us first prove that vertex implies linear span. We will prove by contradiction.Let
be a vertex of
. Suppose
does not span
. For notation let the cardinality of
be
Consider the matrix
with
as the columns, \ie,
![\displaystyle A=[a_1,... ,a_m],](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+A%3D%5Ba_1%2C...+%2Ca_m%5D%2C&bg=ffffff&fg=000000&s=0&c=20201002)
an
matrix. Since
does not span the entire
, the kernel space (or null space) of the matrix
is non empty (or the dimension of the kernel is greater than
.) Hence there exists a non zero
. Since
,

We will now prove that
is not a vertex. Let
be a small number. Define

and

Observe that
and hence if
and
lie in the polyhedron
, then
is not an extreme point (vertex) which is a contradiction. We will now prove that for very small
,
and
indeed lie in
. To show that
(or
) lie in
we should show that they satisfy
for all
. Let
. Then

follows since
for
and
since
. Now if
, then

Observe that
. Hence if we choose
very very small, then
. (For example, you can choose
.). Hence
satisfies all the inequalities and hence is in the polyhedron. Similarly, you can show that
satisfies all the inequalities and hence in the polyhedron.
We will now prove the converse, \ie, linear span implies vertex. Suppose
where
. We first have for
,

Since
, we have
and
, which is possible only when
and
. Now consider the set of equations for
.

Since
span the entire
, it follows that there is a unique solution to the above set of equations. However, we have
and
and
. This implies
since the solution should be unique. 
Corollary 2 For any vertex

, the cardinality of the set

should be greater than

, \ie

.
Proof: We require at least
vectors to span
. 
We will now analyze a particular polyhedron that is required to simplify the assignment problem. Before that we require the following definition of a permutation matrix. Suppose
is a permutation of
. Then the permutation matrix
is an
matrix with the
entry given by

So for a given
there are
permutation matrices.
Birkhoff polytope:
Birkhoff polytope
is the set of all doubly stochastic
matrices. Mathematically,

First observe that
is entirely defined by linear inequalities and hence a polyhedron. Also observe that
is a convex set.
Hw 1 Show that

is a compact set.
Lemma 3 An

permutation matrix

is an extreme point of

.
Proof: Suppose
where
. Consider the
-th row of all the three matrices. Suppose
and all the other entries are zero. So we have
![\displaystyle 2[0, 0, ..,1,....0] = [a_{i1}, ..., a_{in}]+[c_{i1}, ..., c_{in}]](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+2%5B0%2C+0%2C+..%2C1%2C....0%5D+%3D+%5Ba_%7Bi1%7D%2C+...%2C+a_%7Bin%7D%5D%2B%5Bc_%7Bi1%7D%2C+...%2C+c_%7Bin%7D%5D&bg=ffffff&fg=000000&s=0&c=20201002)
We have
,
and each term is non-negative. This is possible only when
and zero for all the other entries of the
-th row. This shows that
, which proves that
is an extreme point of
. 
We will now prove the converse of the above statement.
Theorem 4 (Birkhoff- von Neumann Theorem.) The extreme points of
are precisely the set of permutation matrices.
Proof: We prove the lemma by induction. For
, it is an obvious statement. Let us assume it is true till dimension
and prove it for dimension
.
Consider the following affine subspace of
. The space
is the set of all
real numbers
such that

and

Observe that the dimension of the space
is
. (Think why??) Observe that
and is defined as the polyhedron

in
.
Let
be an extreme point of
. So by Theorem 1, an extreme point
of
should satisfy at least
inequalities with equalities. Hence
for at least
entries of the matrix. We make the following observation.
- Every row cannot have more than or equal to
non zero entries: In this case the maximum number of zero entries would be
(each row can have at maximum
zero entries and there are
rows). This cannot be true, since
.
So there is at least one row
with only one non-zero entry at
location. Since
is also doubly stochastic, we have that
. Hence it also follows that there can be no more non zero entries in the column
. Let
be the new matrix obtained after removing the row
and the column
. Observe that
is a doubly stochastic matrix:This is because the original matrix
was doubly stochastic and the contribution from row
and column
is only
.
is an extreme point of
: Suppose
is not an extreme point of
, \ie,
can be expressed as a sum of
, where
and
. Then it is easy to see that by adding one more row (all zeros except at
) and column (all zeros except at
) to
and
at positions
and
will result in new matrices
and
. Observe that
.
So
is an extreme point of
. So by induction hypothesis, we have that
is some
permutation matrix
. Now augment
with the
row and
column to obtain
. 
We will now see how to utilize this theorem to simplify the assignment problem. Recall that the AP was to minimize over all the permutations of
.

Observe that the cost function
is equivalent to

where
is the permutation matrix. So the AP equals

Observe that even now,
is restricted to be either
or
.
Now consider a new problem P2:

over the set

Observe that we are now maximizing over the Birkhoff polytope
and
are real numbers. So we are maximizing a linear function
over a convex compact set
. Hence the maximum occurs at a vertex point of
. But by Birkhoff- von Neumann theorem, the vertices of
are nothing but the permutation matrices. Hence solving P2 is equal to solving AP. Also observe that the new problem P2 is a linear programming problem and is very easy to solve in polynomial complexity.