<<

. 11
( 59 .)



>>

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

<<

. 11
( 59 .)



>>