Find the convex subdifferential $\partial d_K$ of the distance function $d_K$ associated to a convex set $K$ at in-set points $x_0 \in K$.

Question

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.

Answer 1

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.

Answer 2

Hint: If $x \notin K$ then $d_K$ is differentiable at $x$.

Let $\bar{x} \in K$ is the unique point projection of $x$ on $K$

Try to prove that it is differentiable at $x$ using definition of differentiability with $ D d_k (x) = \frac{x- \bar{x}}{ \| x- \bar{x} \|} $.