How to prove squared distance is differentiable? Let $X ⊆ R$ be a closed, convex, non-empty set, and 
$f(x) = ||x-P(x)||^2_2$ 
the “squared-
distance-from-X” function. Show that f is a differentiable function whose gradient is  $∇f(x) = 2(x-P(x))$
 A: Here is a solution using non differentiable analysis (the references below are to
Clarke's "Optimization and Nonsmooth Analysis").
Let $C$ be the non empty convex compact set and write $f(x) = \min_{c \in C} \|x-c\|^2$.
It is straightforward to show that $f$ is Lipschitz with rank one and so has a
generalised gradient.
Note that $\min_{c \in C} \|x-c\|^2 = - \max_{c \in C} -\|x-c\|^2$, and we can write the
$\max$ as $\max_{c \in C} \phi(x,c)$, where
$\phi(x,c) = -\|x-c\|^2$. We see that $\phi$ is smooth and Lipschitz with rank one in $x$. Let $g(x) = \max_{c \in C} \phi(x,c)$ and 
$M(x) = \{c \in C | g(x) = \phi(x,c) \}$.
Note that $M(x)$ is a singleton and denote the element by $P(x)$.
Theorem 2.8.2 shows that $\partial g(x) = \{ {\partial \phi(x,c) \over \partial x} | c \in M(x) \} = \{ {\partial \phi(x,P(x)) \over \partial x} \}$. Proposition 2.2.4 shows that
$g$ is differentiable at $x$ and ${\partial g(x) \over \partial x} = {\partial \phi(x,P(x)) \over \partial x} = 2 (P(x)-x)^T$. 
Hence $f$ is differentiable and ${\partial f(x) \over \partial x} = 2(x-P(x))^T$, from
which the gradient is see to be $2(x-P(x))$.
Simpler solution:
\begin{eqnarray}
f(x+h)-f(x) &=& \|x+h-P(x+h)\|^2 - \|x-P(x)\|^2 \\
&\le& \|x+h-P(x)\|^2 - \|x-P(x)\|^2 \\
&=& 2 (x-P(x))^T h + \|h\|^2
\end{eqnarray}
In the other direction
\begin{eqnarray}
f(x)-f(x+h) &=& \|x+P(x)\|^2 - \|x+h-P(x+h)\|^2 \\
&\le& \|x-P(x+h)\|^2 - \|x+h-P(x+h)\|^2 \\
&=& -2 (x-P(x+h))^T h + \|h\|^2 \\
&=& -2 (x-P(x))^T h + 2(P(x+h)-P(x))^T h+\|h\|^2 \\
&\le& -2 (x-P(x))^T h + 3\|h\|^2
\end{eqnarray}
In particular, this shows that $f$ is differentiable with derivative
$2(x-P(x))^T$.
