hyperplane separation

Let $X$ be a vector space, and $\Phi$ be any subspace of linear functionals on $X$ . Impose on $X$ the weak topology generated by $\Phi$ .

Theorem 1 (Hyperplane Separation Theorem I).

Given a weakly closed convex subset $S\subset X$ , and $a\in X\setminus S$ . there is $\phi\in\Phi$ such that

\phi(a)<\inf_{x\in S}\phi(x)\,.

Proof.

The weak topology on $X$ can be generated by the semi-norms $x\mapsto\lvert p(x)\rvert$ for $p\in\Phi$ . A subbasis for the weak topology consists of neigborhoods of the form $\{x\in X\colon\lvert p(x-y)\rvert<\epsilon\}$ for $y\in X$ , $p\in\Phi$ and $\epsilon>0$ . Since $X\setminus S$ is weakly open, there exist $f_{1},\ldots,f_{n}\in\Phi$ and $\epsilon>0$ such that

\lvert f_{i}(x)-f_{i}(a)\rvert=\lvert f_{i}(x-a)\rvert<\epsilon\,,\text{ for % all $i=1,\ldots,n$ \quad implies }x\in X\setminus S\,.

In other words, if $x\in S$ then at least one of $\lvert f_{i}(x)-f_{i}(a)\rvert$ is $\geq\epsilon$ .

Define a map $F\colon X\to\mathbb{R}^{n}$ by $F(x)=(f_{1}(x),\ldots,f_{n}(x))$ . The set $\overline{F(S)}$ is evidently closed and convex in $\mathbb{R}^{n}$ , a Hilbert space under the standard inner product. So there is a point $b\in\overline{F(S)}$ that minimizes the norm $\lVert b-F(a)\rVert$ .

It follows that $\langle{y-b},{b-F(a)}\rangle\geq 0$ for all $y\in\overline{F(S)}$ ; for otherwise we can attain a smaller value of the norm by moving from the point $b$ along a line towards $y$ . (Formally, we have $0\leq\left.\frac{d}{dt}\right|_{t=0}\lVert ty+(1-t)b-F(a)\rVert^{2}=2\langle{y% -b},{b-F(a)}\rangle$ .)

Take $\phi=\sum_{i=1}^{n}\lambda_{i}f_{i}$ where $\lambda=b-F(a)$ . Then we find, for all $x\in S$ ,

	$\displaystyle\phi(x-a)$	$\displaystyle=\langle{b-F(a)},{F(x-a)}\rangle$
		$\displaystyle=\langle{b-F(a)},{b-F(a)}\rangle+\langle{b-F(a)},{y-b}\rangle\,,% \quad y=F(x)\in\overline{F(S)}$
		$\displaystyle\geq\lVert b-F(a)\rVert^{2}+0\geq\epsilon^{2}\,.\qed$

Theorem 2 (Hyperplane Separation Theorem II).

Let $S\subset X$ be a weakly closed convex subset, and $K\subset X$ a compact convex subset, that do not intersect each other. Then there exists $\phi\in\Phi$ such that

\sup_{y\in K}\phi(y)<\inf_{x\in S}\phi(x)\,.

Proof.

We show that $S-K=\{x-y\colon x\in S\,,y\in K\}$ is weakly closed in $X$ . Let $\{z_{\alpha}=x_{\alpha}-y_{\alpha}\}\subseteq A$ be a net convergent to $z$ . Since $K$ is compact, $\{y_{\alpha}\}$ has a subnet $\{y_{\alpha(\beta)}\}$ convergent to $y\in K$ . Then the subnet $x_{\alpha(\beta)}=z_{\alpha(\beta)}+y_{\alpha(\beta)}$ is convergent to $x=z+y$ . The point $x$ is in $S$ since $S$ is closed; therefore $z=x-y$ is in $S-K$ .

Also, $S-K$ is convex since $S$ and $K$ are. Noting that $0\notin S-K$ (otherwise $S$ and $K$ would have a common point), we apply the previous theorem to obtain a $\phi\in\Phi$ such that

0=\phi(0)<\inf_{z\in S-K}\phi(z)\leq\phi(x-y)\,,\text{ for all $x\in S$ and $y% \in K$. }

The desired conclusion follows at once. ∎

Title	hyperplane separation
Canonical name	HyperplaneSeparation
Date of creation	2013-03-22 17:19:01
Last modified on	2013-03-22 17:19:01
Owner	stevecheng (10074)
Last modified by	stevecheng (10074)
Numerical id	4
Author	stevecheng (10074)
Entry type	Theorem
Classification	msc 46A55
Classification	msc 49J27
Classification	msc 46A20
Synonym	separating hyperplane
Related topic	HahnBanachgeometricFormTheorem