Hyperplane Separation Theorem

[This article was first published on Pachá, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

A bit of context to put this on my stats blog: I’m reading Real Analysis books again as a part of my studies. I used to visit Kim C. Border site from time to time to read his excellent materials, and now I read that he passed away. I never audited one of his courses nor studied at Caltech, but we exchanged several emails from 2012 to 2019, mostly about Linear Algebra, and lately also about Arrow’s Impossibility Theorem and social debates in a moment when Chile entered a political crisis that we still haven’t solved. The proof of this theorem, heavily inspired from his style, is a way to tribute him as a very positive influence during my economics studies.

Theorem (Hyperplane Separation Theorem). Let \(\renewcommand{\vec}[1]{\boldsymbol{#1}} \newcommand{\R}{\mathbb{R}} A\) and \(B\) two convex, disjoint, non-empty subsets of \(\R^n\). If \(A\) is closed and \(B\) is compact, exists \(\vec{p}\in \R^n\setminus \{\vec{0}\}\) such that \(\vec{p}\cdot \vec{a} < \vec{p}\cdot \vec{b} \, \, \forall (\vec{a},\vec{b})\in A\times B\).

Proof. Shall be made under a “divide and conquer” approach.

If \(A\) is closed, define the function \[\begin{align*} f: B &\to \R \cr \vec{b} &\mapsto \min_{\vec{a}\in A} \|\vec{b}-\vec{a}\|. \end{align*}\] This function returns the distance from \(\vec{b}\in B\) to \(\vec{a} \in A\) and is a continuous function.

If \(B\) is compact, exists \(\vec{b}_0 \in B\) such that \(f(\vec{b}_0)\leq f(\vec{b}) \:\forall \vec{b}\in B\).

Let \(\vec{y}\in A\) such that \(f(\vec{b}_0)=\|\vec{b}_0-\vec{y}\|\). The vector \[\vec{p}=\frac{\vec{b}_0-\vec{y}}{\|\vec{b}_0-\vec{y}\|}\] is well defined and is such that \(\|\vec{p}\|=1\).

From \(\vec{p}\cdot \vec{p} > 0\), it follows that \[\vec{p}\cdot \frac{\vec{b}_0-\vec{y}}{\|\vec{b}_0-\vec{y}\|} > 0,\] from which we conclude that \[\begin{gather}\label{separacion-1} \vec{p}\cdot \vec{y} < \vec{p}\cdot \vec{b}_0 \tag{*}. \end{gather}\]

From \(\eqref{separacion-1}\) we need to prove that \(\vec{p}\cdot \vec{b}_0 \leq \vec{p}\cdot \vec{b}\) and \(\vec{p}\cdot \vec{a} < \vec{p}\cdot \vec{y}\).

Fix \(\vec{a}\in A\) and define the function \[\begin{align*} g: [0,1] &\to \R \cr \lambda &\mapsto \|\vec{b}_0+\vec{y} – \lambda(\vec{a}-\vec{y})\|^2. \end{align*}\] Provided that \(A\) is convex, \(g\) reaches a minimum at \(\lambda=0\), then \[\begin{align*} g(\lambda) &= (\langle \vec{b}_0-\vec{y} – \lambda(\vec{a}-\vec{y}) , \vec{b}_0-\vec{y} – \lambda(\vec{a}-\vec{y}) \rangle)^2 \cr &= (\langle \vec{b}_0-\vec{y} , \vec{b}_0-\vec{y} \rangle – 2\lambda \langle \vec{b}_0-\vec{y} , \vec{a}-\vec{y}\rangle + \lambda^2 \langle \vec{a}-\vec{y} , \vec{a}-\vec{y} \rangle)^2 \cr \frac{\partial g}{\partial \lambda} &= -2\langle \vec{b}_0-\vec{y} , \vec{a}-\vec{y}\rangle + 2\lambda \langle \vec{a}-\vec{y} , \vec{a}-\vec{y} \rangle. \end{align*}\] Hence, \[\left.\frac{\partial g}{\partial \lambda}\right|_{\lambda=0} = (\vec{b}_0-\vec{y})\cdot (\vec{y}-\vec{a}) \geq 0.\] Dividing by \(\|\vec{b}_0-\vec{y}\|\) we conclude that \[\begin{gather}\label{separacion-2} \vec{p}\cdot \vec{a} \leq \vec{p}\cdot \vec{y}. \tag{**} \end{gather}\]

Fix \(\vec{b}\in B\) and define the function \[\begin{align*} h: & [0,1] \to \R \cr \lambda &\mapsto \|\vec{b}_0-\vec{y} – \lambda(\vec{b}-\vec{y})\|^2. \end{align*}\] By the same argument that leads to \(\eqref{separacion-2}\), we conclude that \[\begin{gather}\label{separacion-3} \vec{p}\cdot \vec{b}_0 \leq \vec{p}\cdot \vec{b}. \tag{***} \end{gather}\]

Finally, \(\eqref{separacion-1}\), \(\eqref{separacion-2}\) and \(\eqref{separacion-3}\) lead to conclude that \(\vec{p}\cdot \vec{a} < \vec{p}\cdot \vec{b}\).

To leave a comment for the author, please follow the link and comment on their blog: Pachá.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)