#a # : 1. Since S(0, 1) is compact, there exists a subsequence of +a , that we

I I

again label as +a , and a vector a with #a# : 1 such that a ; a. If we now let

I I

k ; - in (1), we get that

1a, x2 - 1a, z2 for all x in C.

?

If we set : 1a, z2, we see that the hyperplane Ha contains z and is a

supporting hyperplane to C.

It follows from Exercise 2.16 that the supporting hyperplane is nontrivial if

int(C) " `.

De¬nition 4.2. A point x belonging to a convex set C is an extreme point of

C if, for no pair of distinct points x , x in C and for no 90, 90, ; :1,

is it true that x : x ; x .

CONVEX SETS IN RL

58

In other words, a point x in a convex set C is an extreme point of C if x

is interior to no closed interval [x , x ] in C. We leave it as an exercise for the

reader to show that an extreme point is a boundary point.

Let

C : +(x , x ) : x ; x - 1,.

The set of extreme points of C is +(x , x ) : x ; x : 1,.

Let

C : +(x , x ) : x ; x : 1,, C : +(x , x ) : x ; x : 1, x . 0,,

and let C : C 6 C . Then the set of extreme points of C is C .

A convex set need not have any extreme points, as evidenced by C . Another

example of a convex set without any extreme points is +(x , x ) : x : 0,.

T 4.2. L et C be a compact convex set. T hen the set of extreme points of

C is not empty, and every supporting hyperplane of C contains at least one

extreme point of C.

The following observation will be used in the proof of the theorem.

L 4.1. L et C be a convex set and let H be a supporting hyperplane to C. A

point x in H 5 C is an extreme point of C if and only if x is an extreme point

of H 5 C.

Proof. Let x in H 5 C be an extreme point of C. If x were not an extreme

point of H 5 C, then x would be an interior point of some closed interval

[x , x ] contained in H 5 C. But then [x , x ] would be contained in C, and

x would not be an extreme point of C. Thus, if x is an extreme point of C,

then it is also an extreme point of H 5 C.

Let x be an extreme point of H 5 C. If x were not an extreme point of C,

then there would exist points x and x in C with at least one of x and x not

in H such that for some 0 : t : 1

x : tx ; (1 9 t)x .

Suppose that H : H?, that 1a, x2 - for x in C, and that x , H?. Then

a a

1a, x 2 : and

: 1a, x 2 : t1a, x 2 ; (1 9 t)1a, x 2 : t ; (1 9 t) : .

This contradiction shows that x must be an extreme point of C.

We now show that the set of extreme points of a compact convex set is not

empty.

SUPPORTING HYPERPLANES: EXTREME POINTS 59

L 4.2. T he set of extreme points of a compact convex set C is not empty.

Proof. If C is a singleton, then there is nothing to prove. Therefore we may

suppose that C is not a singleton. Since C is compact and the norm is a

continuous function, there exists a point x* in C of maximum norm. Thus

#x# - #x*# for all x in C and #x*# 9 0.

We assert that x* is an extreme point of C. If x* were not an extreme point,

there would exist distinct points x, and x in C different from x* and scalars

9 0, 9 0, ; : 1 such that

x* : x ; x .

Since

#x*# : # x ; x # - #x # ; #x #,

we see that if either #x # or #x # were strictly less than #x*#, we would have

#x*# : ( ; )#x*# : #x*#.

This contradiction implies that

#x # : #x # : #x*#. (2)

But then,

#x*# : # x ; x # : #x # ; 2 1x , x 2 ; #x #

- #x # ; 2 #x # #x # ; #x #

: ( ; )#x*# : #x*#.

Hence we must have

1x , x 2 : 2 #x # #x #.

2

Since 9 0, 9 0, we have 1x , x 2 : #x # #x #. Therefore x : x for some

. 0. The relation (2) implies that : 1, and so x : x . This contradicts the

assumption that x and x are distinct. Thus x* is an extreme point.

We now complete the proof of the theorem. Let H? be a supporting

a

hyperplane to C. Since C is compact, the point x in C such that 1a, x 2 :

is also in C. Hence H? 5 C is nonempty and is compact and convex. By Lemma

a

?

4.2, Ha 5 C contains an extreme point x . By Lemma 4.1, x is also an extreme

C C

point of C.

CONVEX SETS IN RL

60

T 4.3. L et C be a compact convex set. L et C denote the set of extreme

C

points of C. T hen C : co(C ).

C

We ¬rst note that by Theorem 4.2 the set C is not empty.

C

Since C 3 C and C is convex, we have that co(C ) 3 co(C) : C. Since C is

C C

compact, we have that co(C ) 3 C : C.

C

We now assert that C 3 co(C ). If the last assertion were not true, then there

C

would exist an x , co(C ) and in C. Since co(C ) is closed and convex, it

C C

follows from Theorem 3.1 that there exists a hyperplane H? such that for all

a

x + co(C )

C

1a, x2 : : 1a, x 2. (3)

Let

: max+1a, x2 : x + C,. (4)

Since C is compact, the maximum is attained at some point x in C, and thus

*

Ha is a supporting hyperplane to C at x . By Theorem 4.2, H@ contains an

@ a

*

@

extreme point x of C. Thus, x + Ha 5 co(C ), and so by (3),

C

: 1a, x 2 : .

Since x + C, it follows from (3) and (4) that

: 1a, x 2 - .

Combining the last two inequalities gives : . This contradiction shows that

C 3 co(C ).

C

In more general contexts Theorem 4.3 is known as the Krein”Milman

theorem. We shall see in Section 7 that in RL the conclusion of Theorem 4.3 can

be strengthened to C : co(C ).

C

We conclude this section with an example of a compact convex set whose

set of extreme points is not closed. In R let

C : +x : (x 9 1) ; x - 1, x : 0,,

C : +x : x : 0, x : 0, 91 - x - 1,,

and let C : co(C 6 C ). Then C is the union of the points (0, 0, 1), (0, 0, 91)

C

and all points other than the origin that are on the circumference of the circle

in the plane x : 0 whose center is at (1, 0, 0) and whose radius is 1. The origin

is a limit point of this set yet is not in the set.

SYSTEMS OF LINEAR INEQUALITIES: THEOREMS OF THE ALTERNATIVE 61

Exercise 4.1. Let S be a convex set. Show that a point x in S is an extreme

point of S if and only if the set S : +x , Y +x : x + S, x " x , is convex.

Exercise 4.2. Show by examples that Theorem 4.3 fails if the convex set C has

a nonempty set of extreme points and is merely assumed to be closed or is

merely assumed to be bounded rather than closed and bounded.

Exercise 4.3. Let S be a set in RL. Show that every point of S is either an

interior point or a boundary point. Show that if S is compact, then the set of

boundary points of S is not empty. Show that if x is an extreme point of S,

then it is a boundary point of S.

Exercise 4.4. Let C be a convex subset of RL with nonempty interior. Show

that C 5 int(C) is empty.

C

Exercise 4.5. Show directly, without using Lemma 4.2, that the set of extreme

points of a closed ball is the set of its boundary points. Hint: To simplify

notation, take the center of the ball to be the origin.

Exercise 4.6. Let C be a closed convex set in RL not equal to RL. Show that C

is the intersection of all closed half spaces containing C that are determined by

the supporting hyperplanes of C.

Exercise 4.7. Let x be a point in RL. Let C denote the closed cube with center

B

at x and length of side equal to 2 . Thus

C : +x : "x 9 x " - , i : 1, . . . , n,.

B G G

The vertices of the cube are the 2L points of the form ( , , . . . , ) where the

L

take on the values <1.

G

(a) Show that the set of 2L vertices is the set of extreme points of C .

B

(b) Show directly, without using Theorem 4.3, that C is the convex hull of

B

the set of vertices. (Hint: Use induction on n.)

5. SYSTEMS OF LINEAR INEQUALITIES:

THEOREMS OF THE ALTERNATIVE

In this section we shall use the separation theorems to obtain so-called

theorems of the alternative. Theorems of the alternative have the following

form. Given two systems of inequalities, I and II, either system I has a solution

or system II has a solution but never both. Necessary conditions for many

optimization problems follow from these theorems.

CONVEX SETS IN RL

62

The following de¬nitions and lemma are needed in our discussion. A vector

x : (x , . . . , x ) in RL is said to be nonnegative, or x . 0, if, for every

L

i : 1, 2, . . . , n, x . 0. A vector x in RL is said to be positive, or x 9 0, if, for

G