Proof of Seperating Hyperplane Theorem (4)

If there exists two disjoint convex sets C,DC,D then there exists a hyperplane a⃗⊤x⃗=b\vec{a}^\top \vec{x} = b that seperates the two sets.

Define the two points c⃗∈C\vec{c} \in C and d⃗∈D\vec{d} \in D that are closest to each other, and let it be the distance between the two sets:

dist(C,D)=inf⁡{∣∣c⃗−d⃗∣∣2∣c⃗∈C,d⃗∈D}dist(C,D) = \inf \{||\vec{c} - \vec{d}||_2 | \vec{c}\in C, \vec{d} \in D \}

The inf⁡\inf function denotes the infimum ⇒ the largest lower bound of ∣∣c⃗−d⃗∣∣2||\vec{c} - \vec{d}||_2

Then there exists a seperating function:

f(x)=(d⃗−c⃗)⊤(x⃗−d⃗+c⃗2)=0f(x)=(\vec{d} - \vec{c})^\top (\vec{x} - \frac{\vec{d}+\vec{c}}{2}) = 0

And we will see that

∀c⃗∈C,f(c⃗)≤0∀d⃗∈D,f(d⃗)≤0\forall \vec{c} \in C, f(\vec{c}) \le 0 \\ \forall \vec{d} \in D, f(\vec{d}) \le 0

We will prove those constraint by contradiction:

Assue ∃u⃗∈D\exists \vec{u} \in D such that f(u⃗)<0f(\vec{u}) < 0

f(u⃗)=(d⃗−c⃗)⊤(u−d⃗+c⃗2)=(d⃗−c⃗)⊤((u⃗−d⃗)+12(d⃗−c⃗))=<d⃗−c⃗,u⃗−d⃗>+12∣∣d⃗−c⃗∣∣22undefinedwe know that this is ≥0\begin{split} f(\vec{u}) &= (\vec{d}-\vec{c})^\top (u-\frac{\vec{d}+\vec{c}}{2}) \\ &= (\vec{d}-\vec{c})^\top ((\vec{u} - \vec{d}) + \frac{1}{2} (\vec{d} - \vec{c})) \\ &=<\vec{d}-\vec{c}, \vec{u}-\vec{d}> + \underbrace{\frac{1}{2} ||\vec{d} - \vec{c}||_2^2}_{\text{we know that this is $\ge 0$}} \\ \end{split}

So implies that for f(u⃗)<0f(\vec{u}) < 0, <d⃗−c⃗,u⃗−d⃗><\vec{d} - \vec{c}, \vec{u} - \vec{d}> has to be lower than 0

Because this inner product is negative, so if I move along the vector u⃗−d⃗\vec{u} - \vec{d} for some distance tt, then I may get closer to c⃗\vec{c}

Let

p⃗=d⃗+t(u⃗−d⃗)=tu⃗+(1−t)d⃗\vec{p} = \vec{d} + t(\vec{u} - \vec{d}) = t\vec{u}+(1-t)\vec{d}

If t∈(0,1)t \in (0,1) then p⃗∈D\vec{p} \in D (Since DD is convex)

Consider

∣∣c⃗−p⃗∣∣22=∣∣c⃗−d⃗−t(u⃗−d⃗)∣∣2=((d⃗−d⃗)−t(u⃗−d⃗))⊤((c⃗−d⃗)−t(u⃗−d⃗))=∣∣c⃗−d⃗∣∣2+t2∣∣u⃗−d⃗∣∣2−2t<c⃗−d⃗,u⃗−d⃗>\begin{split} ||\vec{c} - \vec{p}||_2^2 &= ||\vec{c} - \vec{d} - t(\vec{u}-\vec{d})||^2 \\ &= ((\vec{d} - \vec{d}) - t(\vec{u}-\vec{d}))^\top((\vec{c} - \vec{d})-t(\vec{u}-\vec{d})) \\ &= ||\vec{c} - \vec{d}||^2 + t^2 ||\vec{u}-\vec{d}||^2 - 2t<\vec{c}-\vec{d},\vec{u}-\vec{d}> \end{split}

We want to show that p⃗\vec{p} is closer than d⃗\vec{d} to c⃗\vec{c}

So let’s write the next two terms

t2∣∣u⃗−d⃗∣∣2−2t<c⃗−d⃗,u⃗−d⃗>=t2∣∣u⃗−d⃗∣∣2+2t<d⃗−c⃗,u⃗−d⃗>undefinedstrictly <0\begin{split} & t^2 ||\vec{u} - \vec{d}||^2 - 2t<\vec{c}-\vec{d}, \vec{u}-\vec{d}> \\ =& t^2 ||\vec{u} - \vec{d}||^2 + 2t\underbrace{<\vec{d}-\vec{c}, \vec{u} - \vec{d}>}_{\text{strictly }<0} \\ \end{split}

But we can always choose a value of tt such that the first term is always smaller in magnitude

t<−2<d⃗−c⃗,u⃗−d⃗>∣∣u⃗−d⃗∣∣2t < -\frac{2<\vec{d}-\vec{c},\vec{u}-\vec{d}>}{||\vec{u}-\vec{d}||^2}

So we have proved a contradiction (because now the distance between c⃗\vec{c} and d⃗\vec{d} is no longer the minimal)