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