Fundamental Separation Theorem

Let S be a non-empty closed, convex set in $\mathbb{R}^n$ and $y \notin S$. Then, there exists a non zero vector $p$ and scalar $\beta$ such that $p^T y>\beta$ and $p^T x < \beta$ for each $x \in S$

Proof

Since S is non empty closed convex set and $y \notin S$ thus by closest point theorem, there exists a unique minimizing point $\hat{x} \in S$ such that

$\left ( x-\hat{x} \right )^T\left ( y-\hat{x} \right )\leq 0 \forall x \in S$

Let $p=\left ( y-\hat{x} \right )\neq 0$ and $\beta=\hat{x}^T\left ( y-\hat{x} \right )=p^T\hat{x}$.

Then $\left ( x-\hat{x} \right )^T\left ( y-\hat{x} \right )\leq 0$

$\Rightarrow \left ( y-\hat{x} \right )^T\left ( x-\hat{x} \right )\leq 0$

$\Rightarrow \left ( y-\hat{x} \right )^Tx\leq \left ( y-\hat{x} \right )^T \hat{x}=\hat{x}^T\left ( y-\hat{x} \right )$ i,e., $p^Tx \leq \beta$

Also, $p^Ty-\beta=\left ( y-\hat{x} \right )^Ty-\hat{x}^T \left ( y-\hat{x} \right )$

$=\left ( y-\hat{x} \right )^T \left ( y-x \right )=\left \| y-\hat{x} \right \|^{2}>0$

$\Rightarrow p^Ty> \beta$

This theorem results in separating hyperplanes. The hyperplanes based on the above theorem can be defined as follows −

Let $S_1$ and $S_2$ are be non-empty subsets of $\mathbb{R}$ and $H=\left \{ X:A^TX=b \right \}$ be a hyperplane.

• The hyperplane H is said to separate $S_1$ and $S_2$ if $A^TX \leq b \forall X \in S_1$ and $A_TX \geq b \forall X \in S_2$

• The hyperplane H is said to strictly separate $S_1$ and $S_2$ if $A^TX < b \forall X \in S_1$ and $A_TX > b \forall X \in S_2$

• The hyperplane H is said to strongly separate $S_1$ and $S_2$ if $A^TX \leq b \forall X \in S_1$ and $A_TX \geq b+ \varepsilon \forall X \in S_2$, where $\varepsilon$ is a positive scalar.