GIVEN
Let $K \subset \mathbb{R}^n$ be a nonempty, closed and convex set. The associated distance function is $d_K$. Find the subdifferential $\partial d_K(x_0)$ for all $x_0 \in K$.
USEFUL DEFINITIONS
Convex Subdifferential
The subdifferential of a proper, lower semi-continuous, and convex function $f$ at a point $x_0 \in \text{dom}(f)$ is:
$$
\partial f (x_0) = \big\{ z \in \mathbb{R}^n : f(x) \geq f(x_0) + \langle z, x – x_0 \rangle , \; \forall x \in \mathbb{R}^n \big\}
$$
Normal Cone
The normal cone of a nonempty, closed, and convex set $K$ at a point $x_0 \in K$ is:
$$
N_K(x_0)=\big\{ z:\langle z, \;x-x_0 \rangle \leq 0,\; \forall x \in K\big\}
$$
CONTEXT
After some research I have found out that this is a well-known result: $\partial d_K (x_0) = \bar{B}\cap N_K (x_0)$ for all $x_0 \in K$. Here $\bar{B}$ refers to the closed unit ball.
Note that this is true for Banach spaces. I am unsure of the result in my case. I also cannot use infimal convolution as I have not learned it yet.
However, I could not find any proof of it anywhere, and thus I am trying to prove that $\Vert z \Vert \leq 1$ (giving $z \in \bar{B}$) and that $\langle z, \; x – x_0 \rangle \leq 0$ (giving $z \in N_K(x_0)$). Here $z \in \partial d_K (x_0)$.
ATTEMPT
Let $x_0$ be a fixed point in $K$.
The distance function $d_K(x) = \inf_{y \in K} \Vert x – y\Vert$ over a convex set $K$ is convex, proper and lower semi-continuous. Since $x_0 \in K$ then $d_K (x_0) = 0$.
Using the above definition, obtain:
$$
\partial d_K (x_0) = \big\{ \zeta \in \mathbb{R}^n : d_K(x) \geq \langle z, \; x – x_0 \rangle , \; \forall x \in \mathbb{R}^n \big\}
$$
Part 1 — Normal Cone
Case 1: $x \in K$
Here, $d_K (x) = 0$ and the above equation gives $\partial d_K(x_0)=N_K (x_0)$.
Case 2: $x \notin K$
Here, $d_K (x) = \Vert x – p\Vert > 0$, where $p$ is the projection of $x$ onto $K$.
I am completely stuck here and have tried multiple failed attempts. How can I prove that $z \in N_K (x_0)$?
Part 2 — Closed Unit Ball
Since $\Vert x – p \Vert \geq \langle z,\; x-x_0 \rangle$ for all $x \in \mathbb{R}^n$. Choose $x = z + x_0$ to obtain:
$$\
\Vert z + x_0 – p \Vert \geq \langle z,\; z \rangle = \Vert z \Vert^2
$$
Since $\Vert z + x_0 – p \Vert \leq \Vert z \Vert + \Vert x_0 – p\Vert$, then obtain:
$$
\Vert z \Vert \leq 1 + \frac{\Vert x_0 – p \Vert}{\Vert z \Vert}
$$
If $x_0 \in \text{bdry}(K)$, then $p = \text{proj}_K (z + x_0) = x_0$ since $z$ is normal (I am unsure of this). Thus the previous inequality gives $\Vert z \Vert \leq 1$.
I have no clue what to do for $x_0 \in \text{int}(K)$.
(Here $\text{int}$ is interior, $\text{bdry}$ is boundary).
I am very confused and have put in too much time without any results. Please, any insight is immensely appreciated.
Best Answer
If $x_0$ belongs to the boundary of $K$, then the subdifferential requested is the intersection of $N_K(x_0)$ and the closed unit ball.
If $x_0$ belongs to the interior of $K$, then it is $\{0\}$.
For completeness, if $x_0$ is outside $K$, then it is $(x_0-P_Kx_0)/d_K(x_0)$.
For proofs, see Bauschke-Combettes Convex Analysis and Monotone Operator Theory in Hilbert Spaces, second edition, Example 16.62.