Let $( \mathbb{R}^d, \| \mathbf{x}\|_2 )$ be a Euclidean Space. For any nonempty 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?
$\begingroup$
$\endgroup$
11
-
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ńskiCommented Aug 17, 2016 at 6:07
-
$\begingroup$ @WłodzimierzHolsztyński , can you refer or give a counter example? $\endgroup$– Amir SagivCommented Aug 17, 2016 at 6:18
-
2$\begingroup$ Take $A=\{0\}$, $d(x,A)=\|x\|$ is not differentiable at 0. $\endgroup$– Fedor PetrovCommented Aug 17, 2016 at 6:33
-
$\begingroup$ Borwein+Lewis Convex Analysis, Section 3.3 Exercise 12(d.iii) characterizes the subdifferential of this function. $\endgroup$– Aryeh KontorovichCommented Aug 17, 2016 at 6:38
-
$\begingroup$ Later in that exercise (d.iv), the gradient is computed for $x\notin A$. $\endgroup$– Aryeh KontorovichCommented Aug 17, 2016 at 6:40
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
answered Aug 17, 2016 at 12:47