Let $( \mathbb{R}^d, \| \mathbf{x}\|_2 )$ be a Euclidean Space. For any closed convex set $A\subseteq \mathbb{R}^d$, we define \begin{align} d(\mathbf{x}, A) = \inf \{ \| \mathbf{x} - \mathbf{y} \|_2, ~~\mathbf{y}\in A\}. \end{align} I was wondering how to prove that $d(\mathbf{x}, A)$ is differentiable and that the gradient is Lipschitz?


closed as off-topic by Anton Petrunin, Myshkin, user21574, Alexey Ustinov, Stefan Kohl Aug 17 '16 at 17:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Anton Petrunin, Myshkin, Community, Alexey Ustinov, Stefan Kohl
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ In general, this distance is not differentiable already in $R^2$ at a point $p\in R^2\setminus A$. $\endgroup$ – Włodzimierz Holsztyński Aug 17 '16 at 6:07
  • $\begingroup$ @WłodzimierzHolsztyński , can you refer or give a counter example? $\endgroup$ – Amir Sagiv Aug 17 '16 at 6:18
  • 2
    $\begingroup$ Take $A=\{0\}$, $d(x,A)=\|x\|$ is not differentiable at 0. $\endgroup$ – Fedor Petrov Aug 17 '16 at 6:33
  • $\begingroup$ Borwein+Lewis Convex Analysis, Section 3.3 Exercise 12(d.iii) characterizes the subdifferential of this function. $\endgroup$ – Aryeh Kontorovich Aug 17 '16 at 6:38
  • $\begingroup$ Later in that exercise (d.iv), the gradient is computed for $x\notin A$. $\endgroup$ – Aryeh Kontorovich Aug 17 '16 at 6:40

Borwein+Lewis Convex Analysis, Section 3.3 Exercise 12(d) shows that for convex $A$ and $x\notin A$, $$\nabla f(x) = f(x)^{-1}(x-P_A(x)),$$ where $f(x)=d(x,A)$ is your function and $P_A(x)$ is the projection of $x$ onto $A$ (i.e., the unique $x^*\in A$ achieving the $\inf$). This shows, in particular, that for $x\notin A$, $||\nabla f(x)||_2=1$.

The Lipschitz property follows from Borwein+Lewis Section 2.1 Exercise 8(c.iii), which shows that projection is a contraction.

The full book reference: Convex Analysis and Nonlinear Optimization, Borwein, Jonathan, Lewis, Adrian S. http://www.springer.com/us/book/9780387295701

Edit: I forgot to state the additional hypothesis that $A$ is closed.


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