Fundamental Separation Theorem

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

Proof

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

$left ( x-hat{x} ight )^Tleft ( y-hat{x} ight )leq 0 forall x in S$

Let $p=left ( y-hat{x} ight ) eq 0$ and $eta=hat{x}^Tleft ( y-hat{x} ight )=p^That{x}$.

Then $left ( x-hat{x} ight )^Tleft ( y-hat{x} ight )leq 0$

$Rightarrow left ( y-hat{x} ight )^Tleft ( x-hat{x} ight )leq 0$

$Rightarrow left ( y-hat{x} ight )^Txleq left ( y-hat{x} ight )^T hat{x}=hat{x}^Tleft ( y-hat{x} ight )$ i,e., $p^Tx leq eta$

Also, $p^Ty-eta=left ( y-hat{x} ight )^Ty-hat{x}^T left ( y-hat{x} ight )$

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

$Rightarrow p^Ty> eta$

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 ight }$ 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.