3
$\begingroup$

Let $K\subseteq\mathbb R^d$ be a non-empty, closed, convex set and $x_0\in \partial K$ (the boundary of $K$). Let $u\in\mathbb R^d$ be a vector satisfying $\langle u,x-x_0\rangle\leq 0$ for all $x\in K$ (that is, $u$ is in the normal cone to $K$ at $x_0$). For all integers $n\geq 1$, let $T_n=n(K-x_0)$.

Fix some $z\in\mathbb R^d$ and define, for all $n\geq 1$, $z_n=\pi_{T_n}(z+nu)$, where $\pi_{T_n}$ is the metric projection onto $T_n$. Is it necessarily true that the sequence $(z_n)_{n\geq 1}$ converges?

First, one can show that $(z_n)_{n\geq 1}$ is bounded. Hence, it would be sufficient to check that all converging subsequences converge to the same limit. Let $t$ be such a limit.

Let $T$ be the tangent cone to $K$ at $x_0$, that is, $T$ is the closure of $\displaystyle{\bigcup_{n\geq 1} T_n}$.

Then, it must hold that $t\in T$. Moreover, one can check that $\langle u,t\rangle=0$.

My first guess was that $t$ should be $\pi_{T\cap u^\perp}(z)$ but, even though it seems correct on a few examples, it does not seem to be true in general.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

$\newcommand\R{\Bbb R}\newcommand\N{\Bbb N}\newcommand\conv{\operatorname{conv}}$The answer is no.

Indeed, let us use the example by Shapiro of a closed convex set in $\R^2$ such that the metric projection onto that set is not everywhere directionally differentiable.

Accordingly, for $n\in\N:=\{1,2,\dots\}$ let $a_n:=\frac\pi{2^n}$, $$A:=\{(\cos a_n,\sin a_n)\colon n\in\N\},$$ \begin{equation} K:=\conv(A\cup\{(0,0),(1,0)\}), \end{equation} where $\conv$ denotes the convex hull, so that $K$ is a compact convex set.

Let $x_0:=(1,0)$, so that $x_0\in\partial K$. Let $u:=(1,0)$, so that $u\cdot(x-x_0)\le0$ for all $x\in K$, where $\cdot$ denotes the dot product.

Let $z:=(0,1)$. Our $z$ and $x_0+u=(2,0)$ were respectively denoted as $d$ and $x_0$ by Shapiro.

Note that \begin{equation} z_n=\pi_{T_n}(z+nu)=n(\pi_K(x_0+u+z/n)-x_0) \end{equation} and $x_0=\pi_K(x_0+u)$. So, we can represent $z_n$ as a quotient: \begin{equation} z_n=Q(1/n),\quad Q(h):= \frac{\pi_K(x_0+u+h z)-\pi_K(x_0+u)}h. \end{equation}

Shapiro showed that there are two positive sequences $(s_j)$ and $(t_j)$ converging to $0$ such that \begin{equation} \lim_j \pi_2 Q(t_j)=:L_1\ne L_2:=\lim_j \pi_2 Q(s_j), \end{equation} where $\pi_2 a$ denotes the second coordinate of $a\in\R^2$.

Let now \begin{equation} n_j:=\lceil 1/t_j\rceil,\quad m_j:=\lceil 1/s_j\rceil, \end{equation} so that $1/n_j=t_j+O(t_j^2)$ and $1/m_j=s_j+O(s_j^2)$. Therefore and because $\pi_K$ is $1$-Lipschitz, we get \begin{equation} \lim_j \pi_2 z_{n_j}=\lim_j \pi_2 Q(1/n_j)=L_1\ne L_2=\lim_j \pi_2 Q(1/m_j)=\lim_j \pi_2 z_{m_j}. \end{equation}
Thus, the sequence $(z_n)$ does not converge. $\quad\Box$

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Thank you!!! Your answer gives me exactly what I wanted: It is enough that $\pi_{K-x_0}$ has a directional derivative at $u$ in the direction of $z$. Indeed (and this is what I missed, which makes me feel stupid), one has $\pi_{T_n}(z+nu)=\pi_{n(K-x_0)}(z+nu)=n\pi_{K-x_0}(z/n+u)$ which does have a limit as $n\to\infty$ if $\pi_{K-x_0}$ has directional derivatives at $u$. Thank you again! $\endgroup$ Commented Sep 26 at 0:17
4
$\begingroup$

For simplicity, assume that $x_0 = 0$. Then, $$ z_n = n \pi_K(u + z/n) = \frac{\pi_K(u + z/n) - \pi_K(u)}{1/n}, $$ where we used $0 = x_0 = \pi_K(u)$. Hence, you are basically asking whether $\pi_K$ is differentiable at $u$ in direction $z$.

  • For polyhedral sets $K$, you indeed obtain $\pi_{K \cap u^\perp}(u)$
  • If $K$ is a circle, you get a positive multiple of $\pi_{K \cap u^\perp}(u)$ (the factor depends on the radius of the circle and of the magnitude of $u$)
  • Finally, there are convex sets $K$ with a nondifferentiable projection, see "Directionally Nondifferentiable Metric Projection" by Shapiro.
Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! I am wondering, though, if the following is true: Given a non-empty, closed, convex set $K\subseteq\mathbb R^d$ ($d\geq 1$) and $u\in\mathbb R^d\setminus K$, if $\pi_K$ has directional derivatives at $u$ (in all directions), does it necessarily have directional derivatives at any point of the ray starting from $\pi_K(u)$, going through $u$? $\endgroup$ Commented Oct 24 at 0:17
  • $\begingroup$ Yes, this should hold. It directly follows from Corollary 4.4 in the paper "Generalized second-order derivatives of convex functions in reflexive Banach spaces" by Do. Basically, it should also follow from the theory in Rockafellar's "Generalized second derivatives of convex functions and saddle functions", but it is not stated explicitly. Note that these papers use the notion of "second epidifferentiability". Maybe it is also possible to prove this by direct arguments. $\endgroup$ Commented Oct 24 at 8:06
  • 1
    $\begingroup$ I also found a direct argument: Proposition 2.2 in "Directional differentiability of the metric projection in Hilbert space" by Noll. $\endgroup$ Commented Oct 24 at 8:07
  • $\begingroup$ Thank you! Noll's proof is very elegant! Do's paper is also very nice, and it shows that directional derivatives of metric projections (when they exist) are automatically proximal mappings, hence, satisfy a lot of good properties. By the way, fun fact: There is another paper with almost the same title as Do's paper, by Ndoutoume and Théra in 1995 (three years later). The paper is very different en flavor though. The only difference, in the title, is the spelling of "Generalized"! Anyways, thanks again for pointing to these great references. $\endgroup$ Commented Oct 26 at 17:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.