compact in RK, where m:(n;1);n(n;1):(n;1). The mapping : RK ; RL

de¬ned by

L>

(p, x , . . . , x ) : p x

L GG

G

is continuous. Since is compact, it follows from Theorem I.9.2 that ( ) is

compact. By Theorem 2.2, ( ) : co(A), so co(A) is compact.

L 2.8. If O is an open subset of RL, then co(O) is also open.

Proof. Since O 3 co(O), the set co(O) has nonempty interior. Therefore, by

Corollary 1 of Lemma 2.5 int(co(O)) is convex and O 3 int(co(O)). (Why?)

Since co(O) is the intersection of all convex sets containing O, we have

co(O) 3 int(co(O)). Since we always have the reverse inclusion, we have that

co(O) : int(co(O)).

CONVEX SETS IN RL

44

Exercise 2.3. Using the de¬nition of a convex set, show that (a) the non-

negative orthant in RL : +x : x : (x , . . . , x ), x . 0 i : 1, . . . , n, is convex and

LG

(b) a hyperplane H? is convex.

a

Exercise 2.4. A mapping S from RL to RK is said to be af¬ne if Sx : T x ; b,

where T is a linear map from RL ; RK and b is a ¬xed vector. (If b : 0,

then S is linear.) Show that if C is a convex set in RL, then S(C) :

+y : y : T x ; b, x + C, is a convex set in RK. In mathematical jargon, you are

about to show that under an af¬ne map convex sets are mapped onto convex

sets or under an af¬ne map the image of a convex set is convex.

Exercise 2.5. Show that the sets P are compact and convex.

L

Exercise 2.6. Show that for any set A the set K(A) of all convex combinations

of points in A is convex.

Exercise 2.7. Show that the open ball B(0, r) is convex.

Exercise 2.8. Consider the linear programming (LP) problem: Minimize 1c, x2

subject to Ax : b, x . 0. Let S : +x : x is a solution of the problem LP,. Show

that if S is not empty, then it is convex.

Exercise 2.9. Let C 3 RL. Show that C is convex if and only if C ; C :

( ; )C for all . 0, . 0.

Exercise 2.10. A set C is said to be a cone with vertex at the origin, or simply

a cone, if whenever x + C, all vectors x, . 0, belong to C. If C is also convex,

C is said to be a convex cone.

(a) Give an example of a cone that is not convex.

(b) Give an example of a cone that is convex.

(c) Let C be a nonempty set in RL. Show that C is a convex cone if and

only if x and x + C implies that x ; x + C for all . 0, . 0.

Exercise 2.11. Show that if C and C are convex cones, then so is C ; C

and that C ; C : co(C 6 C ).

Exercise 2.12. Show that if A is a bounded set in RL, then so is co(A).

Exercise 2.13. Let X be a convex set in RL and let y be any vector not in X.

Let [y, X] denote the union of all line segments [y, x] with x in X.

(a) Sketch a set [y, X] in R.

(b) Show that [y, X] is convex.

SEPARATION THEOREMS 45

Exercise 2.14. Let C be a proper subset of RL. For each 9 0 de¬ne a set (C),

C

the -neighborhood of C, by (C) : 8x + C B(x, ). Show that

C

(C) : +y : #x 9 y# : for some x + C,

C

: 8 (B(0, ) ; x).

x+C

(C) is open. Show that if C is convex, then so is

Show that (C).

C C

Exercise 2.15. Show that if a vector x in RL has distinct representations as

a convex combination of a set of vectors x , x , . . . , x , then the vectors

P

x 9 x , . . . , x 9 x are linearly dependent.

P

Exercise 2.16. Let X be a set contained in the closed negative half space

determined by the hyperplane H?. Show that if x + int(X), then 1a, x) : .

a

Exercise 2.17. Let X be a convex set and let H? be a hyperplane such that

a

X 5 H? : `. Show that X is contained in one of the open half spaces

a

?

determined by Ha.

3. SEPARATION THEOREMS

This section is devoted to the establishment of separation theorems. In some

sense, these theorems are the fundamental theorems of optimization theory.

The validity of this assertion will be made evident in subsequent chapters of

this book.

?

We have seen that a hyperplane Ha divides RL into two half spaces, one on

each side of H?. It therefore seems natural to say that two sets X and Y are

a

separated by a hyperplane H? if they are contained in different half spaces

a

?. There are various types of separation, which we will now

determined by Ha

de¬ne precisely and discuss. The reader should draw sketches in R. (Recall

that in R a hyperplane is a line.)

De¬nition 3.1. Two sets X and Y are separated by the hyperplane H? if, for

a

every x + X, 1a, x2 . and, for every y + Y, 1a, y2 - .

This type of separation does not always correspond to what one intuitively

considers a separation. For example, in R, let

X : +(x , x ) : x : 0, 0 - x - 2,

and let

Y : +(x x ) : x : 0, 1 - x - 3,.

CONVEX SETS IN RL

46

According to De¬nition 3.1, these sets are separated by the hyperplane x : 0.

On the other hand, one would not consider these sets as being separated in

any reasonable way. This example illustrates that two sets which intuitively

should not be considered as being separated can be separated by a hyperplane

H? according to De¬nition 3.1 if the sets both lie in H?. To rule out the

a a

possibility just discussed, the notion of proper separation is introduced.

De¬nition 3.2. Two sets X and Y are properly separated by a hyperplane H? a

if, for every x + X, 1a, x2 . , for every y in Y, 1a, y2 - , and at least one of

the sets is not contained in H?.

a

Geometrically, the de¬nition requires that X and Y be in opposite closed

half spaces and at least one of the sets not be contained in H?. Note that the

a

sets X and Y are not properly separated by the hyperplane x : 0 and that

they cannot be properly separated by any hyperplane.

Proper separation of two sets X and Y does not require that the sets be

disjoint. The sets

X : +(x , x ) : 0 - x - 1, 0 - x - 1,

and

Y : +(x , x ) : 0 - x - 1, 91 - x - 0,

are not disjoint but are properly separated by the hyperplane x : 0. A set may

be a subset of another set, yet the two sets can be properly separated. To see

this, let X* : X and let Y * : +(x , x ) : 0 - x - 1, x : 0,. Then Y * 3 X*

and the sets are properly separated by the hyperplane x : 0. To rule out the

possibilities just described, the notion of strict separation is introduced.

De¬nition 3.3. Two sets X and Y are strictly separated by a hyperplane H? if,

a

for every x in X, 1a, x2 9 and, for every y in Y, 1a, y2 : .

Geometrically, the de¬nition requires that X and Y be in opposite open half

spaces determined by H?. Note that the sets X and Y cannot be strictly

a

separated by any hyperplane. The sets

X : +(x , x ) : 0 - x - 1, 0 : x - 1,

and

Y : +(x , x ) : 0 - x - 1, 91 : x : 0,

are strictly separated by the hyperplane x : 0. Note that X and Y are

properly separated but are not strictly separated by the hyperplane x : 0.

SEPARATION THEOREMS 47

Finally, note that the sets X and Y are not strictly separated by the

hyperplane x : 0.

De¬nition 3.4. Two sets X and Y are strongly separated by a hyperplane H? ifa

there exists an 9 0 such that the sets X ; B(0, 1) and Y ; B(0, 1) are strictly

separated by H?.a

The sets X and Y are not strongly separated by the hyperplane x : 0 and

cannot be strongly separated by any hyperplane. Let 0 : : 1 be ¬xed. Then

for each such the sets

X : +(x , x ) : 0 - x - 1, - x - 1,

E

and

Y : +(x , x ) : 0 - x - 1, 91 - x - 9 ,

E

are strongly separated by the hyperplane x : 0.

It is clear from the de¬nitions that strong separation implies strict separ-

ation, which implies proper separation.

Exercise 3.1. Sketch the pairs of sets (X , Y ), (X , Y ), (X *, Y *), (X , Y ), and

(X , Y ).

E E

The next lemma gives two conditions, each of which is equivalent to strong

separation as given in De¬nition 3.4.

L 3.1. T he following statements are equivalent:

(i) Two sets X and Y are strongly separated by a hyperplane H?.

a

(ii) T here exists an 9 0 such that 1a, x2 9 ; for all x in X and

1a, y2 : 9 for all y in Y.

(iii) T here exists an 9 0 such that

inf+1a, x2 : x + X, . ;

and

sup+1a, y2 : y + Y , - 9 .

Proof. The equivalence of (ii) and (iii) is clear, so we need only prove the

equivalence of (i) and (ii). We note that z + B(0, 1) if and only if 9z + B(0, 1).

Suppose X and Y are strongly separated by H?. Then there exists an 9 0 such

a

that, for all x in X and all z in B(0, 1), 1a, x 9 z2 9 . Thus for all x in X and

CONVEX SETS IN RL

48

all z + B(0, 1),

9 1a, z2 9 9 1a, x2.

If we take z : ( a)/#a#, 0 : : 1, and then let ; 1, we get 9 #a# .

9 1a, x2, or

1a, x2 . ; #a#,

for all x in X. A similar argument shows that

1a, y2 - 9 #a#