Convex Optimization - Closest Point Theorem

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

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

Proof

Existence of closest point

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

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

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} ight |=Infleft { left | y-x ight |,x in S ight }$

Uniqueness

Suppose $ar{x} in S$ such that $left | y-hat{x} ight |=left | y-hat{x} ight |= alpha$

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

But, $left | y-frac{hat{x}-ar{x}}{2} ight |leq frac{1}{2}left | y-hat{x} ight |+frac{1}{2}left | y-ar{x} ight |=alpha$

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

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

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

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

Thus, minimizing point is unique.

For the second part of the proof, assume $left ( y-hat{x} ight )^{ au }left ( x-ar{x} ight )leq 0$ for all $xin S$

Now,

$left | y-x ight |^{2}=left | y-hat{x}+ hat{x}-x ight |^{2}=left | y-hat{x} ight |^{2}+left |hat{x}-x ight |^{2}+2left (hat{x}-x ight )^{ au }left ( y-hat{x} ight )$

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

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

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

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

Since S is convex set.

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

Now, $left | y-hat{x}-lambdaleft ( x-hat{x} ight ) ight |^{2}geq left | y-hat{x} ight |^2$

And

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

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

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

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

Hence Proved.