How to prove squared distance is differentiable?

Question

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))$

Answer 1

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$.