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

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.

• Can you prove at least an inclusion? $\partial d_K(x_0)\subset N_K(x_0)$ is immediate. – Federico Nov 22 '18 at 17:54
• $\partial d_K(x_0)\subset B_1$ is also clear because $d_K$ is $1$-Lipschitz. – Federico Nov 22 '18 at 17:55
• Of course you can just work with $x_0\in\partial K$, because if $x_0\in\mathop{\mathrm{int}}(K)$ then both $\partial d_K(x_0)$ and $N_K(x_0)$ are empty. – Federico Nov 22 '18 at 17:57
• @Federico Empty !!!!! if $x_0 \in int(K)$ then $\partial d_k (x_0) = N_K (x_0) = \{0\}$ – Red shoes Nov 22 '18 at 18:18
• @Redshoes right, of course, my bad; I rushed over it – Federico Nov 22 '18 at 18:19

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.

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

• Not relevant. He is explicitly asking for $x_0\in K$. – Federico Nov 22 '18 at 17:52
• He said he got stuck in case two, I gave him a big hint. what I'm saying is that in case 2 $\partial d_k (x_0) = \{ \frac{x_ 0 - \bar{x}}{ \| x_0 - \bar{x} \|} \}$ – Red shoes Nov 22 '18 at 18:12
• But if $x\not\in K$ then $N_K(x)$ has nothing to do with $\partial d_K(x)$ – Federico Nov 22 '18 at 18:16
• I mean, of course what you say is correct, I just don't see what it has to do with "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$." – Federico Nov 22 '18 at 18:18
• Actually, under the section ATTEMPT, he reaches a wrong conclusion also in Case 1. – Federico Nov 22 '18 at 18:28