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

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 )^Tleft ( y-hat{x} right )leq 0 forall x in S$

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

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

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

$Rightarrow left ( y-hat{x} right )^Txleq left ( y-hat{x} right )^T hat{x}=hat{x}^Tleft ( 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_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.