Hahn-Banach Separation Theorems

Idea: Given two sets, $A$ and $B$, when can we draw a line ``between" them?

If $A$ and $B$ are convex, then we have a chance. If they aren't, we could easily run into problems

Example: In $\mathbb{R}^2$;

$$A := \{ (x,y) : y > x^4 \}.$$

$$B := \{ (x,y) : x \in [-1,1], y \in (-1,0) \}$$

Definition 1.1.1   Let $X$ be a topological vector space. We say $A,B \subset X$ are separated (strictly separated ) if there is $f \in X^*, f \neq 0$, and $\alpha \in \mathbb{R}$ such that

$$A \subset ($$ Re $$f)^{-1}( (-\infty, \alpha ]),$$

$$B \subset ($$ Re $$f)^{-1}( [\alpha, +\infty)).$$

For strictly separated,

$$A \subset ($$ Re $$f)^{-1}( (-\infty, \alpha )),$$

$$B \subset ($$ Re $$f)^{-1}( (\alpha, +\infty)).$$

Terminology:
$($ Re $f)^{-1} ((-\infty,\alpha])$ is called a closed half-space.
$($ Re $f)^{-1} ((-\infty, \alpha))$ is called an open half-space.
$($ Re $f)^{-1} (\{ \alpha \} )$ is called a closed affine hyperplane.

Answer: Convex sets almost always can be separated under mild topological conditions.

Recall: For $V$ a nonempty, convex balanced set, which is absorbing at each point, the function $p$, defined by

$$p(x) = \inf \{ t \geq 0 : x \in tV \},$$

is a seminorm. In fact, $p$ is the unique seminorm so that $\{ x \in X : p(x) < 1 \} = V$.

The same proof shows:

Proposition 1.1.2   If $V$ is an open, convex set containing 0 in a TVS $X$, then $p$, as above, is a continuous sublinear functional.

Theorem 1.1.3   Hahn-Banach Separation Theorem (Open Set)
Let $X$ be a TVS. Let $A$ and $B$ be disjoint, convex, nonempty subsets of $X$ with $A$ open. There is $f \in X^*$, $\alpha \in \mathbb{R}$ such that $\forall a \in A, \forall b \in B$,

    Re $$f (a) < \alpha \leq$$    Re $$f(b)$$

Proof. (Not the one in the book.)

Case 1)

$\mathbb{F}= \mathbb{R}$. Pick $a_0 \in A$ and $b_0 \in B$, and let

$$C := A - B - a_0 + b_0$$

$$C = \bigcup_{b \in B} A - b - a_0 + b_0$$

Then $C$ is a convex open set containing 0. Let $z = -a_0 + b_0$. If $z \in C$, then $0 \in A - B$ and $A \cup B \neq \emptyset$, a contradiction. Hence, $z \notin C$.

Let $m$ be the Minkowski functional of $C$ as in the proposition. Then, $m(z) \geq 1$. On $\mathbb{R}z$, define $\phi_0$ by

$$\phi_0(sz) = s, \forall s \in \mathbb{R}$$

On $\mathbb{R}z$, for $s \geq 0$,

$$\phi_0 (sz) = s, \leq s m(z) = m(sz )$$

For $s \leq 0$,

$$\phi_0 (sz) = s \leq 0 \leq m(sz)$$

So $\phi_0$ is a linear functional on $\mathbb{R}z$ which is dominated by $m$. By the Hahn-Banach Extension Theorem, there is a linear functional $\phi \in X^*$ with $\phi$ dominated by $m$ (but we don't get that $\phi$ is continuous).
However, $\phi$ is indeed continuous since $\phi(x) \leq m(x) \leq 1$ for all $x \in C$ means that for all $\epsilon > 0$,

$$\vert\phi\vert \leq \epsilon$$    on $$\epsilon C \cap -\epsilon C.$$

Note that $\epsilon C \cap -\epsilon C$ is a neighborhood of 0.
For $a \in A$, $b \in B$,

$$\phi(a - b + z) < 1$$

$$\phi(a) - \phi(b) < 0$$

as $\phi(z) = 1$. Since $\phi(a) < \phi(b)$ for $a \in A$, $b \in B$. Since $A$ is convex and open, $\phi(A)$ is an open convex set in $\mathbb{R}$ (an open interval). As $B$ is convex, $\phi(B)$ is an interval. Let

$$\alpha = \sup \phi(A)$$

and we are done.

Case 2)

$\mathbb{F}= \mathbb{C}$. Since $X$ is also a topological vector space over $\mathbb{R}$, by case 1, we can find $\psi : X \rightarrow \mathbb{R}$ so that the theorem holds. By the correspondence between real and complex-valued functionals, there is $\phi \in X^*$ such that Re $\phi = \psi$.

$\qedsymbol$

Corollary 1.1.4   If $A$ and $B$ are disjoint convex, nonempty, open subsets of a TVS $X$, then they are strictly separated.

Proof. Notice that in the above proof, if $B$ is open, then $\phi(B)$ is open and so $\alpha < \phi(b)$ for all $b \in B$; i.e., $A$ and $B$ are strictly separated. $\qedsymbol$

Wednesday, January 10, 2006:

Proposition 1.1.5   Let $X$ be a TVS, $K \subset V \subset X$, $K$ compact and $V$ open. Then there is a neighborhood of 0, $N$, so that $K + N \subset V$.

Proof. Assume this is false; i.e., for every open set $U$ containing 0, $U + K \not\subset V$. Let $\mathcal{U}$ be the set of neighborhoods of 0, ordered by reverse inclusion. For each $U \in \mathcal{U}$, there is $x_U \in K$, $y_U \in U$ such that $x_U + y_U \notin V$. Notice: $y_U \rightarrow 0$. Now, as $x_U \in K$, for all $U \in \mathcal{U}$, as $K$is compact, theere is a cluster point $x \in K$ for $(x_U)$. Thus, $(x_U + y_U)$ has a cluster point in $K$. Since $x_U + y_U \in V^c$, a closed set, for all $U$, all cluster points must be in $V^c$. $\qedsymbol$

Theorem 1.1.6   Hahn-Banach Separation Theorem (Compact Sets)
Let $A$ and $B$ be disjoint, convex, closed subset of a LCS $X$. Suppose further that $B$ is compact. Then, there is $f \in X^*$, $\alpha \in \mathbb{R}$, and $\epsilon > 0$ so that for all $a \in A$ and $b \in B$,

    Re $$f(a) < \alpha < \alpha + \epsilon <$$    Re $$f(b)$$

Proof. (Not the one in the book).
By the Proposition, there is a neighborhood of 0, $U$, such that $B + U \subset A^c$. WLOG, $U$ is convex (this is where we use the fact $X$ is an LCS), so $B + U$ is convex. By the Hahn-Banach separation theorem for open sets, there is $f \in X^*$ and $\alpha \in \mathbb{R}$ such that

    Re $$(x) \leq \alpha <$$    Re $$f(y)$$

for all $x \in A$, $y \in B + U$. Since Re $f(B)$ is a compact subset of Re $f(B+U)$ and both sets are intervals, so there is $\epsilon > 0$ such that in

$$\inf$$    Re $$f(B) - \inf$$    Re $$f(B+U) > \epsilon$$

Thus,

    Re $$f(x) \leq a < a + \epsilon \leq$$    Re $$f(b)$$

for all $x \in A$, $b \in B$. $\qedsymbol$

Corollary 1.1.7   Let $X$ be a LCS

1. If $A$ is a closed convex set and $x \notin A$, then $A$ and $\{ x \}$ are strictly separated.
2. If $A \subset X$, then $\overline{co}(A)$ is the intersection of the closed half-spaces containing $A$.
3. If $Y \leq X$ ($Y$ is a closed linear subspace of $X$) and $x \notin Y$, then there is $f \in X^*$, $f \vert _Y \equiv 0$, $f(x) = 1$.

Note: In $L^p$, $0 < p < 1$, (3) is not true (as there are no nonzero continuous linear functionals). So we need $X$ to be a LCS, not just a TVS.