<<

. 14
( 59 .)



>>

I
#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

<<

. 14
( 59 .)



>>