Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

7. fejezet - Separating and supporting hyperplanes

7. fejezet - Separating and supporting hyperplanes

The result on the existence of separating hyperplane between two compact sets can be considered as a geometric version of Hahn-Banach's theorem on linear functionals. Its first form is an extension theorem since the property required of the functional is that it extends a given functional (defined on a subspace) without increasing the norm. The second form is a separation theorem because the property required of the hyperplane is that it separates two given convex sets. The connection, of course, is that a (closed) hyperplane is a translate of the kernel of a continuous linear functional. In finite dimensional spaces one can follow a simplified "more linear and less topological" way to develop the theory [55]. Using the classical setting of the coordinate spaces the most adequate approach is to rely not only on the basic topology and the linear structure of the space but also on the Euclidean geometry via orthogonal complements and nearest-point-type argumentations as follows.

7.1 Separating and supporting hyperplanes

In the sense of the structure theorem 1.3.8 each non-empty affine set A can be written into the formp+L, where p is an arbitrary element in A and L is a uniquely determined linear subspace.

Definition Affine sets of dimension n - 1 in the n-dimensional coordinate space are called hyperplanes.

Since the co-dimension of the associated linear subspace of a hyperplane is just one its orthogonal complement can be generated by a non-zero vector n which is unique up to a non-zero scalar multiplier. It is clear that the point q is in the hyperplane if and only if the position vector q - p (with respect to p) is orthogonal to n, i.e.

q - p , n = 0 .

(7.1)

We have two further possible cases corresponding to the inequalities

q - p , n > 0   o r   q - p , n < 0 .

(7.2)

The points of the space which are not in the hyperplane 7.1 are in exactly one of the so-called (open) half-spaces determined by the relations 7.2. It can be easily seen that they are non-empty disjoint convex subsets in the coordinate space. Their closures (the open half-spaces together with the hyperplane) are called closed half-spaces. If we substitute n with its additive inverse then the relations characterizing the half- spaces come into each other but they do not change as pointsets. The sides of a hyperplane mean the half-spaces determined by the hyperplane.

Definition The subsets D and E in the coordinate space of dimension n are called separated by the hyperplane L if they are in different sides of L. Strictly separation means that the subsets are in different open sides of the hyperplane.

Figure 44: The nearest-point-type argumentation.

The nearest-point-type argumentation. Let p be a point in the coordinate space of dimension n and consider a compact convex set K in the space such that p is not in K. By a standard compactness argumentation it follows that there exists a point q in K where the distance

d ( p , K ) : = i n f v K d ( p , v )

is attained at. Consider now the vector n:=p - q. If L is the orthogonal complement to n then the standard conclusion is that the hyperplane q+L separates p and K. To prove this observation suppose, in contrary, that K has a point z in the open half space containing p. The segment s(z,q) is in K because of the convexity and it must intersect the interior of the Thales ball around the diameter s(p,q). Therefore we have a point in K which is closer to p than q. This is a contradiction as figure 43 shows. In what follows we shall use this kind of argumentation in more general cases by substituting p with a compact convex set.

Theorem 7.1.1 Let D and E be compact subsets in the coordinate space of dimension n. They are strictly separated if and only if their convex hulls are disjoint.

Proof If the sets are strictly separated then their convex hulls must bedisjoint because they are contained in different open half-spaces determined by the separating hyperplane. To prove the converse statement first of all recall that the convex hull of a compact set is also compact 2.2.2. Suppose that the convex hulls are disjoint and consider the distance

d ( c o n v D , c o n v E ) = i n f { d ( v , w ) | v c o n v D   a n d   w c o n v E }

between them. By a standard compactness argument it follows that there are points p in conv D and q in conv E such that

d ( c o n v D , c o n v E ) = d ( p , q ) .

Let n be the difference vector of the points where the minimal distance is attained at and consider the linear subspace L which is orthogonal to n. Using a standard nearest-point-type argumentation it can be easily seen that the open band determined by the hyperplanes p+L and q+L is disjoint from both conv D and conv E. Therefore the hyperplane bisecting the band strictly separates the sets conv D and conv E together with D and E, respectively. ▮

Definition We say that a hyperplane bounds a set D if D is contained in one of the half spaces. If the hyperplane H bounding D has a common point p with the set D then H is said to support D at the point p.

Theorem 7.1.2 (The existence theorem of supporting hyperplanes) Let K be a closed convex subset in the coordinate space ofdimension n. Then for any boundary point p in K there exists a hyperplane supporting K at p.

Proof If dim K < n then any hyperplane containing K is a supporting hyperplane at each point of K. In what follows we are going to construct supporting hyperplanes passing through the boundary points of K. The proof is actually an inductive process on the dimension of the embedding space. The case of the coordinate plane. Let K be a closed convex subset of dimension 2 in the coordinate plane and suppose that the origin is one of the boundary points by translating K if necessary. Consider the central projection of K through the origin to the unit circle. The image of K is a connected arc belonging to a central angle with measure at most π because of the convexity of K.

Figure 45: The case of the coordinate plane.

Therefore there exists a diagonal of the circle which bounds this arc together with the set K. The case of higher dimensional coordinate spaces.

Figure 46: The orthogonal projection.

Let p be an arbitrary boundary point and consider a hyperplane H of dimension n - 1 passing through p in the coordinate space of dimension n. If H supports K then there is nothing to prove. Otherwise let K' be the intersection of H and K. It is a closed convex subset of maximal dimension[7] in H as the coordinate space of dimension n - 1. Taking the supporting hyperplane at p in H to the intersection K' we have a hyperplane H' of dimension n - 2. Let P' be the orthogonal complement to H'. Then P' is of dimension two. Consider the orthogonal projection π(K) in P'. Since H' is a supporting hyperplane to K' in H the point π(p) supports π(K') in the common line l of H and P'.Therefore π(p) is on the boundary of the projected set π(K) as well and we can consider the supporting line l' in P' to the set π(K) at π(p).

Figure 47: The supporting hyperplane.

The corresponding supporting hyperplane to K at p is just the affine hull of the union of H' and l'. ▮

Theorem 7.1.3 (The converse of the existence theorem.) Let K be a closed n- dimensional convex set in the coordinate space of dimension n. If for any boundary point p of K there exits a supporting hyperplane passing through p then K is convex.

Proof If K is just the coordinate space of dimension n then we have nothing to prove. Therefore we can suppose that there exists an element v which is not in K. Let w be in the interior of K and suppose that p is its boundary point on the segment s(v,w). Since w is contained in K together with an open neighbourhood we have that the supporting hyperplane at p does not contain w and, consequently, the hyperplane strictly separates the endpoints v and w. At the same time v and the set K are separated. We have just proved that if v is not in K then there exists a supporting hyperplane of K such that v and K are separated. In fact the opposite half space to that containing K contains v in its interior. Let Ω be the intersection of closed half spaces containing K. It is clear that K is a subset of Ω and the equality of K and Ω follows from the fact that each point v in the complement of K is in the complement of Ω. Therefore Ω is a subsetof K. But the intersection of closed half spaces is convex. So is K as was to be proved. ▮

Remark The theorem can be considered as an external characterization of convexity of sets. Another possibility of such a characterization is to prove that if a closed subset satisfies the nearest-point property then it is convex, see also excercise 7.4.2.

Corollary 7.1.4 Let K be a closed n-dimensional convex set in the coordinate space of dimension n. K is convex if and only if for any boundary point p of K there exits a supporting hyperplane passing through p.