1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can you prove at least an inclusion? $\partial d_K(x_0)\subset N_K(x_0)$ is immediate. $\endgroup$ – Federico Nov 22 '18 at 17:54
  • 1
    $\begingroup$ $\partial d_K(x_0)\subset B_1$ is also clear because $d_K$ is $1$-Lipschitz. $\endgroup$ – Federico Nov 22 '18 at 17:55
  • $\begingroup$ 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. $\endgroup$ – Federico Nov 22 '18 at 17:57
  • 1
    $\begingroup$ @Federico Empty !!!!! if $x_0 \in int(K)$ then $ \partial d_k (x_0) = N_K (x_0) = \{0\} $ $\endgroup$ – Red shoes Nov 22 '18 at 18:18
  • 1
    $\begingroup$ @Redshoes right, of course, my bad; I rushed over it $\endgroup$ – Federico Nov 22 '18 at 18:19
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Not relevant. He is explicitly asking for $x_0\in K$. $\endgroup$ – Federico Nov 22 '18 at 17:52
  • $\begingroup$ 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} \|} \} $ $\endgroup$ – Red shoes Nov 22 '18 at 18:12
  • 1
    $\begingroup$ But if $x\not\in K$ then $N_K(x)$ has nothing to do with $\partial d_K(x)$ $\endgroup$ – Federico Nov 22 '18 at 18:16
  • 1
    $\begingroup$ 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$." $\endgroup$ – Federico Nov 22 '18 at 18:18
  • 1
    $\begingroup$ Actually, under the section ATTEMPT, he reaches a wrong conclusion also in Case 1. $\endgroup$ – Federico Nov 22 '18 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.