Htykuut

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 Kbig}
$$

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 - yVert$ 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 - pVert > 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 - pVert$, 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.

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