<<

. 19
( 59 .)



>>

Although the separation and support theorems of Sections 3 and 4 are
adequate for most applications to optimization problems, they are not appli-
cable in some situations where proper separation and nontrivial support of
convex sets do occur. To illustrate this, let

C : +x + R : x . 0, x . 0, x : 0,
   
C : +x + R : x . 0, x . 0, x : 0,.
   
These two sets are properly separated by the plane (hyperplane in R)
x 9 x : 0. These sets are convex, are not disjoint, and have empty interiors
 
so that neither Theorem 3.3 nor Theorem 3.4 can be applied to deduce
separation.
Let C : +x + R : x ; x - 1, x : 0,. At each boundary point x with
   
x ; x : 1 there exist a nontrivial supporting hyperplane, namely the plane
 
that is orthogonal to the plane x : 0 and whose intersection with this plane

is the tangent line to the circle x ; x : 1, x : 0 at x . Again, since the
   
convex set C has empty interior, Theorem 4.1 does not give us the existence of
this nontrivial supporting hyperplane.
The sets C , C , and C, considered as sets in R, do have interiors. It turns

out that this observation is the key to theorems that are applicable to examples
such as those described above. We introduce the notion of relative interior of
a convex set C of dimension r. The relative interior is the interior of a convex
set C considered as a set in [C]. In other words we consider the set C as a
set in RP rather than a set in RL.

De¬nition 7.1. Let A be a set of dimension r - n and let M : [A]. A point
x in A is said to be a relative interior point of A if there exists an 9 0 such

that B(x , ) 5 M 3 A. The set of relative interior points of A is called the

MORE ON SEPARATION AND SUPPORT 81


relative interior of A and will be denoted by ri(A). A set A is said to relatively
open if ri(A) : A, that is, if every point of A is a relative interior point of A.

Note that if dim M : n, then a relative interior point is an interior point
and a relatively open set is an open set.
Since a linear manifold M is a closed set, any limit point of A will also be
in M. Thus the closure of A as a subset of M is the same as the closure of A
as a subset of RL.
If A is contained in M and dim M : n, then every point of A is a boundary

point of A. We de¬ne the relative boundary of A to be the set A : ri(A), that

is, those points of A that are not relative interior points of A. If dim M : n,
then the relative boundary of A is the boundary of A.
Let M be a linear manifold of dimension r : n and let be the mapping
de¬ned in Remark 6.3. We noted there that and \ are one to one and
continuous.

L 7.1. If O is an open set in RP, then \ (O) is a relatively open set in M.
If O is a relatively open set in M, then (O) is an open set in RP.
Proof. Let O be an open set in RP and let x + \(O). Then there is a unique

y in O such that \(y ) : x , or equivalently, y : (x ). Since y + O, there
     
exists an 9 O such that the open ball B (y , ) in RP is contained in O. Since
P
is continuous, there exists a 9 0 such that for x + B(x , ) 5 M we have

(x) + B(y , ) : 0. But this says that B(x , ) 5 M 3 \(O). Hence x is a
  
relative interior point of \(O), and so \(O) is relatively open. Since
: ( \)\, a similar argument with replaced by \ shows that if O is
relatively open, then (O) is open in RP.

Let C be a convex set in RL of dimension r : n. As a consequence of the
one-to-one relationship between M : [C] and RP that preserves open sets,
convexity, dimension of convex sets, and linear manifolds, we can obtain many
properties of C by establishing these properties for convex sets of full dimen-
sion. These properties then hold for the set (C) considered as a set of full
dimension in RP and hence for C : \( (C)). In particular, we obtain the
following results in this fashion.

T 7.1. A convex set of dimension r has nonempty relative interior.

This theorem follows from Theorem 6.1 and Lemma 7.1.

L 7.2. L et C be a convex set and let x and x be two points with x + ri(C)
  

and x + C. T hen the line segment [x , x ) is contained in ri(C).
 
C¬¬ 1. If C is convex, then ri(C) is convex.
CONVEX SETS IN RL
82


C¬¬ 2. L et C be convex. T hen


(i) ri(C) : C and

(ii) ri(C) : ri(C ).

Lemma 7.2, Corollary 1 and (i) of Corollary 2 follow from Lemma 2.5 and
the corresponding corollaries. In proving (ii) of Corollary 2 to Lemma 2.5, we
 
argued that since C 3 C, it follows that int(C) 3 int(C ). In general, it is not
true that if A and B are convex sets with A 3 B that ri(A) 3 ri(B), as the
following example shows. Take B to be a closed unit cube in R. Let A be any
closed face of B. Then A 3 B, but it is not true that ri(A) 3 ri(B). In fact, ri(A)
 
and ri(B) are disjoint. Since [C] : [C], it does follow that ri(C) 3 ri(C ).
The proof of the opposite inclusion given in Section 2 is valid if we replace
interiors by relative interiors.
We now state and prove the best possible separation theorem in RL.

T 7.2. L et X and Y be two convex subsets of RL. T hen X and Y can be
properly separated if and only if ri(X) and ri(Y ) are disjoint.

To prove the ˜˜only if™™ part of the theorem, we shall need to de¬ne what is
meant by hyperplane cutting a convex set and to develop conditions under
which cutting occurs.

De¬nition 7.2. A hyperplane H? is said to cut a convex set C if there exist
a
points x and x in C such that 1a, x 2 : and 1a, x 2 9 . A hyperplane that
   
does not cut C is said to bound C.

L 7.3. A hyperplane H? cuts a convex set C if and only if the following two
a
conditions hold:

(i) H? does not contain C and
a
(ii) H? 5 ri(C) " `.
a


Proof. Let H? cut C. Then there exist points x and x in C such that
 
a
1a, x 2 : and 1a, x 2 9 . Since for y + H? we have 1a, y2 : , conclusion (i)
  a
follows. Now let z + ri(C). Then by Lemma 7.2 the line segments (x , z] and

[z, x ) belong to ri(C). Let

z ; t(z 9 x ), 91 - t - 0,

y(t) :
z ; t(x 9 z), 0 - t - 1.

Then y(t) + C for 91-t - 1 and y(t) + ri(C) for 91:t:1. Let (t):1a, y(t)2.
Since is continuous on [91, 1] with (91) : , and (1) 9 , there exists a
t with 91 : t : 1 such that (t ): . But then y(t ) + ri(C) and 1a, y(t )2: ,
    
which establishes (ii).
MORE ON SEPARATION AND SUPPORT 83


Now suppose that (i) and (ii) hold. Then there exist a point x in ri(C) 5 H?
 a
and a point x in C and not in H?. Suppose that 1a, x 2 : . Since x + ri(C),
  
a
there exists a 9 0 such that x : x 9 (x 9 x ) + C. Then
   
1a, x 2 : 9 (1a, x 2 9 ) 9 .
 
If 1a, x 2 9 , then 1a, x 2 : .
 
We now prove Theorem 7.2.
If a hyperplane properly separates the convex sets X and Y, then it certainly
properly separates ri(X) and ri(Y ). Conversely, if a hyperplane properly
separates ri(X ) and ri(Y ), then since ri(X) : X and ri(Y ) : Y , it follows that

the hyperplane properly separates X and Y. Thus a hyperplane properly
separates X and Y if and only if it properly separates ri(X) and ri(Y ). Thus we
may assume without loss of generality that X and Y are disjoint relatively open
convex sets. The proof of separation will be carried out by a descending
induction on d : max(dim X, dim Y ).
If dim X : n, then the separation follows from Theorem 3.4. We now
assume that proper separation occurs if d . k, where 1 : k - n. We now
suppose that dim X : k 9 1 and dim Y - k 9 1. To simplify the notation, we
assume that 0 + X. There is no loss of generality in assuming this, since this can
always be achieved by a translation of coordinates. Since 0 + X, the manifold
[X] is a subspace of dimension k - n 9 1. Let w be a point in RL that is not
in [X]. Let

A : co+X 6 (X ; w),, B : co+X 6 (X 9 w),.

We assert that Y cannot intersect both A and B. See Figure 2.8.




Figure 2.8.
CONVEX SETS IN RL
84


in A can be written
By Theorem 2.2 points

L>
:  (x ; w),
GG G
G
where x + X for i : 1, . . . , n ; 1, the vector : ( , . . . , ) + P , and is
G  L> L> G
either zero or 1. Thus, if + A, then there exists an x + X such that

: x ;  w, 0 -  - 1. (1)

Since

: x ;  w : (1 9  )x ;  (w ; x),

given by (1) is in A. A similar argument shows that
every point

B : + : : x 9  w, x + X, 0 -  - 1,.

Thus if A 5 Y "` and B 5 Y " `, then there exist points y and y in Y such
 
that

y : x ;  w, y : x 9  w,
     
where x , x + X, 0 :  - 1, 0 :  - 1. The inequalities  9 0 and  9 0
    
follow from X 5 Y : `.
Let :  /(  ;  ) and let :  /(  ;  ). Then 9 0, 9 0, ; : 1,
   
and

y ; y : x ; x. (2)
   
Since X and Y are convex, the left-hand side of (2) belongs to X and the
right-hand side belongs to Y. This contradicts X 5 Y : `, and so Y cannot
intersect both A and B.
For the sake of de¬niteness, suppose that A 5 Y : `. Since dim A : k
(why?) and dim Y - k 9 1, by the inductive hypothesis there exists a hyper-
plane H that properly separates A and Y. Since X 3 A, the hyperplane H
properly separates X and Y.
To prove the ˜˜only if™™ assertion, suppose that there exists a hyperplane H
that properly separates X and Y and that there exists a point z in ri(X) 5 ri(Y ).
Then z + H, and thus H 5 ri(X) " ` and H 5 ri(Y ) " `. Since the separation
is proper, at least one of the sets, say X, is not contained in H. Hence by
Lemma 7.3, H cuts X, which contradicts the assumption that H separates X
and Y.
MORE ON SEPARATION AND SUPPORT 85


We conclude this section with results that are stronger than Theorems 4.1
and 4.3.

T 7.3. L et C be a convex set and let D be a convex subset of the relative
boundary of C. T hen there exists a nontrivial supporting hyperplane to C that
contains D.
Proof. Since ri(C) 5 D : `, we have ri(C) 5 ri(D) : `. Hence by Theorem
7.2 there exists a hyperplane H? that properly separates C and D. Thus
a


1a, x2 - for x + C and 1a, y2 . for y + D. (3)

Since each y in D is a relative boundary point of C, for each y in D there exists
a sequence +x , of points in C such that x ; y. For this sequence we have

<<

. 19
( 59 .)



>>