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