<<

. 13
( 59 .)



>>

X 5 Y : ` if and only if 0 , X 9 Y.
 
Let

A : X 9 Y : X ; (91)Y.
 
Since X and Y are convex, by Lemma 2.2, so is A. Since X and Y are disjoint,
 
0 , A. Hence by Theorem 3.2, there exists an a " 0 such that

1a, z2 - 0 all z in A.

Let x be an arbitrary element of X and let y be an arbitrary element of Y.

Then z : x 9 y is in A and

1a, x2 - 1a, y2. (7)

Let : sup+1a, x2 : x + X , and let : inf+1a, y2 : y + Y ,. Then from (7) we

get that and are ¬nite, and for any number such that - - ,

1a, x2 - - 1a, y2

for all x in X and all y in Y. Thus the hyperplane H? separates X and Y.
 
a


T 3.4. L et X and Y be two convex sets such that int(X) is not empty and
int(X) is disjoint from Y. T hen there exists a hyperplane H? that properly
a
 and Y .
separates X

To illustrate the theorem, let X : +(x , x ) : x - 0, 91 : x - 1, and let
  
Y : +(x , x ) : x : 0, 91 - x - 1,. The hypotheses of the theorem are ful-
  
¬lled and x : 0 properly separates X and Y and hence X and Y. Note that


strict separation of X and Y is not possible.
CONVEX SETS IN RL
54


Proof. Since int(X) is convex and disjoint from Y, we can apply Theorem
3.3 with X : int(X) and obtain the existence of an a " 0 and an such that

1a, x2 - - 1a, y2 (8)

for all x in int(X) and all y in Y.
 
Let x + X. By Corollary 2 to Lemma 2.5, X : int(X) . Hence x + int (X) . By
Remark I.5.2 there exists a sequence of points +x , in int(X) such that x ; x.
I I
It then follows from (8) and the continuity of the inner product that (8) holds
?
for all x in X and all y + Y . Thus, the hyperplane Ha separates X and Y . By
 
 
Corollary 2 to Lemma 2.5, int(X ) : int(X). By Exercise 2.16, for x + int(X ),
1a, x2 : , so the separation is proper.

T 3.5. L et K be a compact convex set and let C be a closed convex set
such that K and C are disjoint. T hen K and C can be strongly separated.
Proof. Let

K : K ; B(0, ) : +u : u : x ; z, x + K, #z# : ,,
C
C : C ; B(0, ) : +v : v : y ; z, y + C, #z# : ,.
C
Since K : 8x + K (B(0, ) ; x), it is a union of open sets and hence is open. It
C
is also readily veri¬ed that K is convex. Similarly, the set C is open and
C C
convex. (See Exercise 2.14.)
We now show that there exists an 9 0 such that K 5 C : `. If the
C C
assertion were false, there would exist a sequence + , with 9 0 and ; 0
I I I
and a sequence +w , such that, for each k, w + K 5 C . Since w : u ; z
C
I I CI I I I
with u + K, #z # : and w : v ; z with v + CI and #z # : , we have a
I I
I I I I I I I
sequence +u , in K and a sequence +v , in C such that
I I
#w 9 u # : , #w 9 v # : .
I I I I I I
Hence

#u 9 v # : #(u 9 w ) ; (w 9 v )# - #u 9 w # ; #v 9 w # : 2 . (9)
I I I I I I I I I I I
Since K is compact, there exists a subsequence +u , that converges to an
IH
element u in K. It follows from (9) that v ; u . Since C is closed, u + C. This
 IH  
contradicts the assumption that C and K are disjoint, and so the assertion is
true.
We have shown that there exists an 9 0 such that K and C are disjoint
C C
open convex sets. Hence by Theorem 3.4 there is a hyperplane that properly
separates K and C . Since both K and C are open sets, it follows from
C C C C
Exercise 2.16 that K and C are strictly separated. According to De¬nition 3.4,
C C
this says that K and C are strongly separated.
SEPARATION THEOREMS 55


We now apply the separation theorems to obtain an additional character-
ization of convex sets.

T 3.6. L et A be a set contained in some half space. T hen the closure
of the convex hull of A, co(A) , is the intersection of all closed half spaces
containing A.
Proof. We orient the hyperplanes that determine the closed half spaces
containing A to be the negative closed half spaces. If H?\ is a closed half space
a
containing A, then co(A) is contained in H?\ and hence in the intersection of
a
all such half spaces. Now let x be a point in the intersection. If x were not in
?
co(A) , then by Theorem 3.1, there would exist a hyperplane Ha such that

1a, z2 : : 1a, x2, z + co(A) .

Hence x would not be in the closed half space by H?\ which contains A.
a
Therefore x is not in the intersection of all negative closed half spaces
containing A, which contradicts the assumption that x is in the intersection.
Thus the intersection is contained in co(A) , and the theorem is proved.

The following corollary follows from the theorem and the fact that a closed
convex set not equal to RL is contained in some closed half space.

C¬¬ 1. If A is a closed convex set not equal to RL, then A is the
intersection of all closed half spaces containing A.

Note that the theorem is false if we replace co(A) by co(A). To see this,
consider the set A in R de¬ned by

A : +(x , x ) : x 9 0, x x . 1, 6 +(x , x ) : x 9 0, x x - 91,.
     
Then co(A) : +(x , x ) : x 9 0,, and the intersection of all closed half spaces is
 
+(x x ) : x . 0,.
 
Exercise 3.2. Let V be a linear subspace and let y , V. Show that x in V is the
*
closest point in V to y if and only if y 9 x is orthogonal to V ; that is, for every
*
w in V, y 9 x is orthogonal to w.
*
Exercise 3.3. Let C be a closed convex set and let y , C. Show that x in C is
*
closest to y if and only if 1x 9 y, x 9 y2 . #x 9 y# for all x in C.
* *
Exercise 3.4. In reference to Theorem 3.5, show that if K is assumed to be
convex and closed, then it may not be possible to separate K and C strictly,
let alone strongly.
CONVEX SETS IN RL
56


Exercise 3.5. Show that if F is closed and K is compact, then K ; F is closed.
Give an example in which F and K are closed yet F ; K is not.

Exercise 3.6. Let A and B be two compact sets. Show that A and B can be
strongly separated if and only if co(A) 5 co(B) : `.

Exercise 3.7. Prove Theorem 3.5 using Theorem 3.1 and Exercise 3.5.


Exercise 3.8. Let A be a bounded set. Show that co(A ) is the intersection of all
closed half spaces containing A. Show that the statement is false if A is not
bounded and a proper subset of RL.

Exercise 3.9. Let A be a closed convex set such that cA (the complement of A)
is convex. Show that A is a closed half space.

Exercise 3.10. Let C and C be two convex subsets of RL. Show that there
 
exists a hyperplane that strongly separates C and C if and only if
 
inf+#x 9 y# : x + C , y + C , 9 0.
 

4. SUPPORTING HYPERPLANES: EXTREME POINTS

In studying convex sets we do not wish to restrict ourselves to sets with smooth
boundaries, that is, sets such that every boundary point has a tangent plane.
The concept that replaces that of tangent plane is that of supporting hyper-
plane. It is a concept that has many important consequences, as we shall see.
We ¬rst de¬ne what is meant by a boundary point of a set. A point z is said
to be a boundary point of a set S if for every 9 0 the ball B(z, ) contains a
point x + S and a point y , S. Note that the de¬nition allows us to have y : z
or x : z. For example, in R let S : +x : (x , x ) : 0 : #x# : 1,. Then 0 is a

boundary point of S, and for every 0 : : 1 the only point in B(0, ) that is
not in S is 0. The other boundary points of S are the points x with #x# : 1. If
there exists an 9 0 such that the only point in B(z, ) that is in S is z itself,
then we say that z is an isolated point of S.

De¬nition 4.1. A hyperplane H? is said to be a supporting hyperplane to a set
a

S if, for every x + S, 1a, x2 - and there exists at least one point x + S such

that 1a, x 2 : . The hyperplane H? is said to support S at x . The hyperplane
 
a
H? is a nontrivial supporting hyperplane if there exists a point x in S such that

a
1a, x 2 : .

To illustrate this de¬nition, consider the set S in R de¬ned by

S : +x : 0 - x ; x : 1, x : 0,.
  
SUPPORTING HYPERPLANES: EXTREME POINTS 57


As a set in R, every point of S is a boundary point. The only supporting
hyperplane at a point of S is the trivial one, x : 0. Every point in the set

E : +x : x ; x : 1, x : 0, is also a boundary point of S. At every point of
  
E there is a nontrivial supporting hyperplane with equation ax ; bx : 1 for
 
appropriate a and b.

Remark 4.1. Let K be a compact set in RL. Then for each a in RL there exists
an such that the hyperplane H? with equation 1a, x2 : is a supporting
a
hyperplane to K. To see this, note that the linear functional L de¬ned by
L (x) : 1a, x2 is continuous on K and so attains its maximum at a point x in
*
K. Then 1a, x2 - 1a, x 2 for all x + K. The desired hyperplane is obtained by
*
taking : 1a, x 2.
*
T 4.1. L et C be a convex set and let z be a boundary point of C. T hen
there exists a supporting hyperplane Ha to C such that z + H?. If int(C) " `, the
? a
supporting hyperplane is nontrivial.
Proof. If z , C, then by Theorem 3.2 with y : z there exists a hyperplane H?
a
such that for all x in C

1a, x2 - and 1a, z2 : .

Since z , C and z is a boundary point of C, it follows that z + C. Thus, H? is a
 a
supporting hyperplane to C with z + H?.
a
If z + C, then from the de¬nition of boundary point it follows that there
exists a sequence of points +y , with y , C such that y ; z. It follows from
I I I
Theorem 3.2 that for each positive integer k there exists a vector a " 0 such
I
that

1a , x2 - 1a , y 2 for all x in C. (1)
I II
If we divide through by #a # " 0 in (1), we see that we may assume that

<<

. 13
( 59 .)



>>