Proof of Nearest-Point Projection onto a Nonempty Closed Convex Subset of Euclidean Space

Throughout we use the identity $|u+w|^2=|u|^2+2\,u\cdot w+|w|^2$ for $u,w\in\mathbb{R}^n$, which follows by expanding the dot product coordinatewise together with $|x|^2=x\cdot x$ from the elementary properties of the Euclidean norm.

Claim 1, existence. Fix $x\in\mathbb{R}^n$. The set $\{|x-y|:y\in C\}$ is nonempty and bounded below by $0$, so it has a real infimum $d\ge0$. For each natural number $k$ choose $y_k\in C$ with $|x-y_k|\le d+\frac{1}{k}$. By the triangle inequality, $|y_k|\le|x|+|x-y_k|\le|x|+d+1$, so the sequence $(y_k)$ is bounded, and by the Bolzano-Weierstrass theorem some subsequence $(y_{k_j})$ converges to a point $p\in\mathbb{R}^n$.

The point $p$ lies in $C$: otherwise $p$ would lie in the complement of $C$, which is open because $C$ is closed, so some open ball around $p$ would miss $C$, contradicting the convergence of the points $y_{k_j}\in C$ to $p$. Moreover $\big||x-y_{k_j}|-|x-p|\big|\le|y_{k_j}-p|$ by the triangle inequality, so $|x-p|=\lim_j|x-y_{k_j}|=d$. Thus $p\in C$ attains the infimum, that is $|x-p|\le|x-y|$ for all $y\in C$.

Claim 1, uniqueness. Suppose $p,q\in C$ both satisfy $|x-p|=|x-q|=d$. Since $C$ is convex, the midpoint $\frac{1}{2}p+\frac{1}{2}q$ lies in $C$. Applying the expansion above with $u=x-p$ and $w=x-q$ to $|u+w|^2+|u-w|^2=2|u|^2+2|w|^2$ and dividing by $4$ gives

$$\Big|x-\tfrac{p+q}{2}\Big|^2=\tfrac{1}{2}|x-p|^2+\tfrac{1}{2}|x-q|^2-\tfrac{1}{4}|p-q|^2=d^2-\tfrac{1}{4}|p-q|^2 .$$

The left-hand side is at least $d^2$ because $\frac{p+q}{2}\in C$ and $d$ is the infimum, so $|p-q|^2\le0$ and hence $p=q$. This proves Claim 1, and $\pi_C(x)$ is well defined.

Claim 2. Suppose first that $p=\pi_C(x)$, let $y\in C$, and let $t\in(0,1]$. By convexity $p+t(y-p)=(1-t)p+ty\in C$, so

$$|x-p|^2\le\big|x-p-t(y-p)\big|^2=|x-p|^2-2t\,(x-p)\cdot(y-p)+t^2|y-p|^2 .$$

Hence $2(x-p)\cdot(y-p)\le t\,|y-p|^2$ for every $t\in(0,1]$, and letting $t$ tend to $0$ gives $(x-p)\cdot(y-p)\le0$.

Conversely, suppose $p\in C$ satisfies $(x-p)\cdot(y-p)\le0$ for every $y\in C$. For $y\in C$,

$$|x-y|^2=\big|(x-p)-(y-p)\big|^2=|x-p|^2-2\,(x-p)\cdot(y-p)+|y-p|^2\ge|x-p|^2 ,$$

so $p$ attains the minimum, and by the uniqueness in Claim 1, $p=\pi_C(x)$.

Claim 3. If $x\in C$ then $|x-x|=0\le|x-y|$ for every $y\in C$, so $x$ attains the minimum and $\pi_C(x)=x$ by uniqueness. Since $\pi_C$ takes values in $C$ and fixes every point of $C$, it maps $\mathbb{R}^n$ onto $C$.

Claim 4. Let $x,x'\in\mathbb{R}^n$ and put $p=\pi_C(x)$, $p'=\pi_C(x')$. By Claim 2 applied to $x$ with $y=p'\in C$, and to $x'$ with $y=p\in C$,

$$(x-p)\cdot(p'-p)\le0,\qquad (x'-p')\cdot(p-p')\le0 .$$

The second inequality says $(x'-p')\cdot(p'-p)\ge0$. Subtracting it from the first,

$$\big((x-x')-(p-p')\big)\cdot(p'-p)\le0 ,$$

which rearranges to $|p-p'|^2\le(x-x')\cdot(p-p')$. By the Cauchy-Schwarz inequality, applied to the positive semidefinite quadratic form given by the identity matrix, for which the associated bilinear form is the dot product, $(x-x')\cdot(p-p')\le|x-x'|\,|p-p'|$. Hence $|p-p'|^2\le|x-x'|\,|p-p'|$. If $p=p'$ the asserted inequality is trivial; otherwise dividing by $|p-p'|>0$ gives $|p-p'|\le|x-x'|$. Thus $\pi_C$ is Lipschitz with constant $1$. $\blacksquare$