Convex Optimization - Closest Point Theorem

Let S be a non-empty closed convex set in $\mathbb{R}^n$ and let $y\notin S$, then $\exists$ a point $\bar{x}\in S$ with minimum distance from y, i.e.,$\left \| y-\bar{x} \right \| \leq \left \| y-x \right \| \forall x \in S.$

Furthermore, $\bar{x}$ is a minimizing point if and only if $\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\leq 0$ or $\left ( y-\hat{x}, x-\hat{x} \right )\leq 0$

Proof

Existence of closest point

Since $S\ne \phi,\exists$ a point $\hat{x}\in S$ such that the minimum distance of S from y is less than or equal to $\left \| y-\hat{x} \right \|$.

Define $\hat{S}=S \cap \left \{ x:\left \| y-x \right \|\leq \left \| y-\hat{x} \right \| \right \}$

Since $ \hat{S}$ is closed and bounded, and since norm is a continuous function, then by Weierstrass theorem, there exists a minimum point $\hat{x} \in S$ such that $\left \| y-\hat{x} \right \|=Inf\left \{ \left \| y-x \right \|,x \in S \right \}$

Uniqueness

Suppose $\bar{x} \in S$ such that $\left \| y-\hat{x} \right \|=\left \| y-\hat{x} \right \|= \alpha$

Since S is convex, $\frac{\hat{x}+\bar{x}}{2} \in S$

But, $\left \| y-\frac{\hat{x}-\bar{x}}{2} \right \|\leq \frac{1}{2}\left \| y-\hat{x} \right \|+\frac{1}{2}\left \| y-\bar{x} \right \|=\alpha$

It can't be strict inequality because $\hat{x}$ is closest to y.

Therefore, $\left \| y-\hat{x} \right \|=\mu \left \| y-\hat{x} \right \|$, for some $\mu$

Now $\left \| \mu \right \|=1.$ If $\mu=-1$, then $\left ( y-\hat{x} \right )=-\left ( y-\hat{x} \right )\Rightarrow y=\frac{\hat{x}+\bar{x}}{2} \in S$

But $y \in S$. Hence contradiction. Thus $\mu=1 \Rightarrow \hat{x}=\bar{x}$

Thus, minimizing point is unique.

For the second part of the proof, assume $\left ( y-\hat{x} \right )^{\tau }\left ( x-\bar{x} \right )\leq 0$ for all $x\in S$

Now,

$\left \| y-x \right \|^{2}=\left \| y-\hat{x}+ \hat{x}-x\right \|^{2}=\left \| y-\hat{x} \right \|^{2}+\left \|\hat{x}-x \right \|^{2}+2\left (\hat{x}-x \right )^{\tau }\left ( y-\hat{x} \right )$

$\Rightarrow \left \| y-x \right \|^{2}\geq \left \| y-\hat{x} \right \|^{2}$ because $\left \| \hat{x}-x \right \|^{2}\geq 0$ and $\left ( \hat{x}- x\right )^{T}\left ( y-\hat{x} \right )\geq 0$

Thus, $\hat{x}$ is minimizing point.

Conversely, assume $\hat{x}$ is minimizimg point.

$\Rightarrow \left \| y-x \right \|^{2}\geq \left \| y-\hat{x} \right \|^2 \forall x \in S$

Since S is convex set.

$\Rightarrow \lambda x+\left ( 1-\lambda \right )\hat{x}=\hat{x}+\lambda\left ( x-\hat{x} \right ) \in S$ for $x \in S$ and $\lambda \in \left ( 0,1 \right )$

Now, $\left \| y-\hat{x}-\lambda\left ( x-\hat{x} \right ) \right \|^{2}\geq \left \| y-\hat{x} \right \|^2$

And

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

$\Rightarrow \left \| y-\hat{x} \right \|^{2}+\lambda^{2}\left \| x-\hat{x} \right \|-2 \lambda\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\geq \left \| y-\hat{x} \right \|^{2}$

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

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

Hence Proved.