Gradient of the squared distance to a closed convex set?

Question

Let $C$ be a nonempty closed convex set of $\mathbb{R}^n$. How do we prove that $\nabla(\frac{1}{2}(\operatorname{dist}(x,C))^2)=x-P_Cx$? Here $P_C x$ is the orthogonal projection of $x$ onto $C$. Note that $\operatorname{dist}(x,C)=||x-P_Cx||$.

Answer 1

Let $x$ and $h$ be given. Due to the properties of the projection we get $$ (P_C(x)-x)^T(P_C(x+th)-P_C(x))\ge0,\\ (P_C(x+th)-x)^T(P_C(x)-P_C(x+th))\ge0. $$ Since the projection $P_C$ is Lipschitz continuous, the difference quotients $\frac1t( P_C(x+th)-P_C(x))$ are uniformly bounded for all $t>0$. Then there is a sequence $t_n\searrow 0$ such that $$ \frac1{t_n}( P_C(x+t_nh)-P_C(x)) \to d. $$ Dividing both the inequalities above by $t_n$ and passing to the limit $t_n\searrow0$ yields $$ (P_C(x+th)-P_C(x))^T d=0. $$ Multiplying out, we find $$ \begin{split} d_C(x+th)^2-d_C(x)^2 & = (x+th - P_C(x+th)-x+P_C(x))^T(x+th - P_C(x+th)+x-P_C(x))\\& = (th - P_C(x+th)+P_C(x))^T(x+th - P_C(x+th)+x-P_C(x)). \end{split} $$ Dividing by $t_n$ and passing to the limit we get $$ \lim_{n\to\infty}t_n^{-1}( d_C(x+t_nh)^2-d_C(x)^2 )= 2(h - d)^T(x- P_C(x)) = 2h^T(x-P_C(x)). $$ The resulting limit is independent of $d$ and thus independent of the sequence $t_n\searrow0$, which shows $$ \lim_{t\searrow 0}t^{-1}( d_C(x+th)^2-d_C(x)^2 )= 2 h^T(x-P_C(x)). $$ Doing the calculation with $-h$ instead of $h$ we see that the limit of the difference quotient for $t\to0$ exists.

Answer 2

Outside $C$, the distance function $d_C: x \mapsto \min_{y \in C}\|x-y\|$ is $\mathcal C^1$ with derivative given by

$$\nabla d_C(x) = \text{sgn}(x - \Pi_C(x)),$$

where $\;\text{sgn}(x) := \begin{cases}x/\|x\|, &\mbox{ if }x \ne 0,\\ 0, &\mbox{ otherwise.}\end{cases}$.

This result is given in (1.1) of "SMOOTHNESS OF CERTAIN METRIC PROJECTIONS ON HILBERT SPACE".

It's then straightforward to obtain the derivative of the quadrance $d_C^2$.