For a nonempty convex set
the point
is an extreme point if there is no two points
such that
.
We denote
the set of all extreme points.

Proposition

(Krein-Milman theorem). Let
be a nonempty convex set. Then

1. For a hyperplane
that contains
in one of its closed
half-spaces

2. If
is closed
then

3. If
is compact
then

Proof

(1). Assume the contrary:
.
Then there must be
.
There are three cases:

a.
.
Since
and
this means that
does not contain
in one of its half-spaces.

b.
.
Then
.

c.
.
Impossible because
and
.

Proof

(2). If
then any candidate
to be in
may be translated in both directions along any
while remaining in
.
Hence,
.
We have
for the same reason.

If
then for any point
there is a direction
such that the line
hits the relative boundary of
at some point
.
By proposition (
Proper separation 1
) there
is a properly separating hyperplane
at that point. By closedness of
the set
is not empty and
.
We reduced the dimensionality of our proof. Because of the part (1) of the
proposition we can complete this proof by induction in the number of
dimensions.

Proof

(3). We prove the statement by induction in the number of dimensions of
.
For
the statement is trivial. Assume that it is true in
.
Let
and
,
.
There is a line that passes through
such
that
and
.
There are properly separating hyperplanes
and
at points
and
.
By applying the statement in
,
Then by (1),
,
.
Hence,
.

Proposition

(Extreme points of polyhedral
set 1). Let
be a polyhedral set. According to the proposition
(
Minkowski-Weyl
representation
)
We
have

Proof

According to the proposition
(
Minkowski-Weyl representation
)
any point
has the representation
,
,
.
An extreme point
may not have a non zero
-part
because it would contradict the definition of the extreme point. The
also cannot be a convex combination of
.
Therefore, the only possibility is
.

Proposition

(Extreme points of polyhedral
set 2). Let
be a polyhedral subset of
.
Then

1. Let
has the
form
and denote
then

2. Let
has the
form
and
denote
then
iff
has the maximal rank (all columns are linearly independent) and
.

3. Let
has the
form
and denote
then
iff
has the maximal rank (all columns are linearly independent) and
.

Proof

(1). We state that
iff for any direction vector
such
that
for some
and any small
one of the
conditions
is violated. If
then no
can be orthogonal to all
and then one of the conditions
is violated.
Hence,

Conversely, if there is a
that is orthogonal to all
then for such
if
.
Hence,
.

Proof

(2). We apply the part (1) of the proposition. In context of the part (1) the
is represented by
where the
is the coordinate basis. Therefore, the
for such situation has the
form
Note that
is given, hence, the condition
above is not restrictive. The set
contains linearly independent vectors. Let
.
We cannot state that according to (1), for
we need to have at least
independent vectors among
.
Indeed, some of the
might be in the linear span of the
.
Hence, we need to exclude the projection on
.
For
we need to have
where the
is the projection. The original matrix
has
columns in total. To establish the last equality it is enough to form a matrix
from the columns
,
remove the
columns that correspond to
and check that the remaining matrix has the maximal rank
.

Proof

The proof of (3) is the same as the proof of (2).

Proposition

Let
be a closed convex set with at least one extreme point. A convex function
that attains a maximum over
attains the maximum at some extreme point of
.

Proof

Let
be a segment
.
Note that
is open. A convex function that attains its maximum at
is constant on
.
Such statement follows directly from the definition of convexity.

The proof is based on the above statement and the theorem
(
Proper separation 1
). Let
be a point where the maximum is attained. By the above statement either
is constant on
or
.
In the former case we are done. In the latter case there is a properly
separating hyperplane
.
Since
we have
.
If
then we are done: the
is an extreme point. Otherwise we observe that we reduce the dimension of the
proof by switching the consideration from
to
.