You are currently browsing the tag archive for the ‘Hahn-Banach Theorem’ tag.

**1. Separation Theorems **

We begin with some definitions of halfspaces:

**Definition 1 ** Let and .

- Open half space :
- Open half space :
- Closed half space :
- Closed half space :

**Definition 2**Let and be two set in and a hyperplane. The sets and are said to be separated by if lies in and . The sets are and are strictly separated by if lies in and . See Figure 1.

Separation theorems deal with sufficient conditions for separation of sets by hyperplane. There are numerous separation theorems with increasing order of complexity. We will look at two separation theorems. In the following discussion the norm we consider is the Euclidean norm. We begin with the following definition of distance to a set

**Definition 3**The distance between a point and a set is defined as

We require the following lemma that characterize the distance of a point to a closed set. The proof can be found in standard analysis textbooks.

**Lemma 5**Let and be two non-empty sets in . Further, let be closed and compact. Then there exists two points and such that

*Proof:* Claim1: The function: is a continuous function. (Easy to prove. Think why).

Since is a compact set and is a continuous function, it attains a minimum on a point on , \ie,

Also by previous lemma there exists a point in such that

Let be some point in and some point in . Then

where follows from the definition of distance to the set and follows from (1). So for any and , we have . Hence

since and .

We will now look into this distance functions more closely.

**Lemma 6**Let be a closed convex set and be a point in . Then there exists an unique point such that

\ie, the point achieves the distance. Moreover, the inner-product

*Proof:* Existence of some point in follows from Lemma 4 because is closed. We will have to show that the point is unique and the inner product inequality is satisfied. We will begin with the inequality. Since and , the line segment . Since is the minimum distance,

So we have

Squaring both sides and after some basic simplification (check this)

Observe that this inequality should hold true for all , especially very small . Since for very small , , it follows that the above expression is non-negative for all if and only if , which proves the inequality.

Suppose there exist one more point such that . Then by the above inequality we have

and

Adding both these inequalities we obtain

which implies .

Geometrically, the inequality means that the angle between the vectors and is obtuse.

**Hw 1**Let be a closed convex set. Then for any , from the previous lemma, we have seen that there exists a unique point such which attains the minimum distance. For any , call the point that attains the distance, the projection of the point on . Then we can define a projection function . Prove that is a Lipschitz function.This function is called the projection operator. (Hint: Use the inner product inequality)

We will now look at the first separation theorem:

**Theorem 7**Let and be non-empty non-intersecting convex sets. Moreover let be a compact set and be a closed set. Then there exists an hyperplane that strictly separates both the sets.

*Proof:* Since is compact and is closed, by Lemma 5, there exists two points and such that is the closest point in of the point and the closest point in of the point .

Let be some point in . Then from Lemma 6, we have

which implies

Observe the strict inequality in the last line. This is because which implies . Hence we have

Now let be some point in . Then from Lemma 6, we have

Using this inequality and similar trick as before, it follows that

It is easy to see from (2) and (3) that the hyperplane strictly separates the sets and .

The next separation theorem looks at separation of a point and an open set. Before that lets look at hyperplanes again. Earlier we have seen that a Hyperplane in is an affine space and its dimension is of dimension . It also follows that any affine subspace of dimension in is a hyperplane.

*Proof:* To show that is an hyperplane, we have to find a scalar and a vector such that

Let . Since is an affine subspace, translating the space by , \ie, is a subspace again of dimension . Since is a subspace (which is a vectorspace) of there exists vectors such that they form the basis of . By Gram-Schmidt orthogonalization we can also assume that these vectors form an orthonormal set. Since these are orthonormal, they are linearly independent in . But since is of dimension , we can find one more vector which is orthogonal to every vector in the set . ( together with will form a basis of ). Since is orthogonal to any basis vector of the subspace , it follows that it is orthogonal to every vector in the subspace . Indeed, it can be shown that any vector orthogonal to should belong to (think projections ?). Hence

Since , we have

which is the equation of a hyperplane with and .

We will now get back to the main separation theorem. The following separation theorem is a special case of geometric Hahn-Banach theorem.

**Theorem 9 (Geometric Hahn-Banach theorem)**

*Let be an open convex set and be some point. Then there exists a hyperplane which contains and strictly isolates .*

*Proof:* Without loss of generality we can assume that . Otherwise, we can translate both and so that .

We will prove this in three stages: First we will prove the theorem for , i.e, a plane. Consider the circle . Now we project the convex set onto the circle in the following way:

as

Observe that the angle of the arc should be less than . Otherwise,if it is greater than , consider a point on the arc . Let this point be the image of a point . Since the arc is greater than , the diametrically opposite point of should also be in the set . Call that point and its inverse image as . Since is convex, observe that the line segment should be in the set and also the line segment should contain the origin. Hence , which is a contradiction to our assumption.

Also, since is an open set, observe that the image of , will be an open arc on . Now consider an end point of the arc. This can be done, since the arc is open. Now consider the line joining the end point and the center origin. This line contains the origin and the set is on one side of the line. This line is the required hyperplane for two dimensions.

*Now let us consider higher dimensions :*

*We will first now prove that there is always a line (one dimension) in higher dimension that passes through the origin such that .* Consider a two dimensional plane through the origin. If it does not have any intersection with , pick some line in the plane and denote it by . This is the required line. Suppose is non-empty, it is easy to see that is a convex and open set that does not contain the origin. Hence by the previous two dimensional result, it follows that there is a line that passes through the origin such that . This is the required line .

Let be an subspace such that and . Also let be the biggest such affine space, \ie, any other subspace with this property is contained in . If the dimension of is , then by Lemma 8, it is a hyperplane and we are done (this is because is an affine subspace through the origin).

We will now prove by contradiction that the dimension of such maximal set is . Let the dimension of be . Since is a subspace there are basis vectors that generate this subspace. Call them . Adding more vectors , the set will form a basis of . So any vector can be represented as a linear combination of the basis vector, i.e.,

Hence we can define the following projection function from to as

Consider the projection of the convex set . The set is convex and open (Why?). Now from the previous argument we can find a line that passes through the origin in but does not intersect . Now consider the inverse image of under the map , \ie, . From (4), we observe that this means only the last coordinates will correspond to and the first coordinates to . Hence it follows that

Observe that is a subspace (why ?) that contains and larger than . Also, it has no intersection with . This is a contradiction since we assumed is the largest subspace with these properties.

So and hence by Lemma 8, is a hyperplane.