# Proof of separation theorem (geometry/linear programming)

In this whole text scalar product of two vectors in $\Bbb R^n$ is written $x^Ty=x_1y_1+...+x_ny_n$ instead of $\langle x,y\rangle$

Theorem Let $K\subseteq \Bbb R^n$ be a closed convex set and $x^* \in \Bbb R^n \backslash K$, then there exists an inequality $a^Tx\geq\beta$ such that $a^Ty > \beta$ holds for all $y \in K$ and $a^Tx^* <\beta$.

• What's the point of writing $K\cap\{x\in K:\|x^*-x\|\leq\|x^*-k\|\}$ since $K$ contains the other set?
• I don't see why $a^Tx^*=\beta-1/2\|k^*-x^*\|^2$ I understand why it is important to construct such an $a$ and $\beta$ but it seems like they are not well constructed here (same for $a^Tk^*=\beta+1/2\|k^*-x^*\|^2$).
• $[\lambda k^*+(1-\lambda)k',m]$ is supposed to be the hypotenuse segment but of what triangle? I tried to draw a sketch here

Question 1

That seems to be a typo, as you point out. It seems like maybe they meant to write $$K\cap\{x\in\mathbb{R}^n:\|x-x^*\|\leqslant\|k-x^*\|\},$$ to emphasize that it's the intersection of closed convex set and a compact convex set.

Question 2

This fact can be verified algebraically using the definitions

$$a=k^*-x^*,\quad m=\frac{1}{2}(k^*+x^*),\quad \beta=a^\text{T}m=\frac{1}{2}(k^*-x^*)(k^*+x^*).$$

To wit:

\begin{align} \beta-\frac{1}{2}\|k^*-x^*\|^2 &=\frac{1}{2}(k^*-x^*)^\text{T}(k^*+x^*)-\frac{1}{2}(k^*-x^*)^\text{T}(k^*-x^*)\\ &=\frac{1}{2}(k^*-x^*)^\text{T}(k^*+x^*-k^*+x^*)\\ &=\frac{1}{2}(k^*-x^*)^\text{T}2x^*\\ &=a^\text{T}x^*. \end{align}

The other one is similar.

Question 3

Here's the picture:

We want the length of the dashed line, which is the hypotenuse of the triangle pictured in the inset at lower right.