Proximal normal cone and convex sets

Question

The proximal normal cone $N_S^P(x)$ for a set $S \subset X$, where $X$ is a Hilbert space, is defined as

$$ N_S^P(x) = \{\zeta \in X : d_S(x + t\zeta) = t\|\zeta\|, \text{ for some } t > 0\}. $$

Suppose that we know that $\langle \zeta, x' - x \rangle \leq 0, \; \forall x, x' \in S, \forall \zeta \in N_S^P(x)$. It follows that $S$ must be convex.

Question: what is a straighforward way to prove convexity of $S$? I have tried to show that

$$ S = \bigcap_{x \in S} \bigcap_{\zeta \in N_S^P(x)} \{ u : \langle \zeta, u - x \rangle \leq 0 \}, $$

where the right hand side is an intersection of halfspaces, hence convex. Proving the inclusion $S \subseteq \dots$ is trivial, but I'm stuck showing the other direction.

Answer 1

Suppose $S$ is non-empty, closed, and non-convex. Then, there exist $a, b \in S$ such that $\frac{a + b}{2} \notin S$. Ideally, I want $\frac{a + b}{2}$ to have a point of projection $x \in S$, as this would imply that $\frac{a + b}{2} - x \in N_S^P(x)$, and hence $$\left\langle\frac{a + b}{2} - x, a - x\right\rangle + \left\langle\frac{a + b}{2} - x, b - x\right\rangle = 2\left\|\frac{a + b}{2} - x\right\|^2 > 0,$$ which would prove the desired property false.

If $S$ were proximinal (i.e. every point has at least one projection onto $S$), then we'd be done, but not every non-empty closed subset of $X$ is proximinal if $X$ is infinite-dimensional. Instead, we'll have to use the following theorem of Lau (see section 5 from this paper):

Theorem: Suppose $X$ is a reflexive Kadec-Klee space (e.g. a Hilbert Space) and $S \subseteq X$ is closed and non-empty. Then there exists a dense $G_\delta$ set $D \subseteq X$ such that every $x \in D$ projects onto a single point of $S$ (i.e. there is a unique element $x^* \in S$ such that $\inf_{s \in S} \|x - s\|$ is minimised uniquely at $s = x^*$).

(This is not a trivial result. There might be an easier proof in the Hilbert Space setting, but I'm not personally aware of it. As best I can tell, we really do need a result like this to show some kind of dense proximinality in order prove this result.)

To use this, let $r = d_S\left(\frac{a + b}{2}\right) > 0$. Using the above theorem, there exists some point $c \in B\left(\frac{a + b}{2}; \frac{r}{2}\right)$ such that $c$ projects (uniquely) onto some point $x \in S$. Then, since $d_S$ is non-expansive, we have $d_S(c) > \frac{r}{2}$. As before, we have $c - x \in N^P_S(x)$, and \begin{align*} \langle c - x, a - x \rangle + \langle c - x, b - x \rangle &= 2\left\langle c - x, \frac{a + b}{2} - x\right\rangle \\ &= 2\left\langle c - \frac{a + b}{2}, \frac{a + b}{2} - x\right\rangle + 2\left\| \frac{a + b}{2} - x\right\|^2 \\ &\ge 2\left\| \frac{a + b}{2} - x\right\|^2 - 2\left\| c - \frac{a + b}{2}\right\| \cdot \left\| \frac{a + b}{2} - x\right\| \\ &= 2\left\| \frac{a + b}{2} - x\right\|\left(\left\| \frac{a + b}{2} - x\right\| - 2\left\| c - \frac{a + b}{2}\right\|\right) \\ &> 2r\left(r - \frac{r}{2}\right) = r^2 > 0. \end{align*} As above, this proves the desired property false. Hence, in order for the property to hold for non-empty, closed $S$, $S$ must also be convex.

Answer 2

I have a proof to this exercise, here we go:

Let us take $x,y\in S$ and $\lambda\in (0,1)$, we consider $a = \lambda x + (1-\lambda) y$. Our goal is to prove that $a\in S$, in this way we are going to see $d_S(a)=0$. Let us $\varepsilon>0$, then there is $x_0\in S$ such that $\|a-x_0\|^2\leq d_S(a)^2 + \varepsilon^2$. If $x_0=a$ then we have the desired, but if $a\neq x_0$ we do the following: Define $f(w) := \|w-a\|^2+\delta_S(w)$, thus $f(x_0)\leq \inf_{w\in X}f(w)+\varepsilon^2$, then by Borwein-Preiss Variational Principle (this result can be found in Nonsmooth Analysis and Control Theory, on page 43), there are $\overline{z},\overline{y}\in X$ such that $\|\overline{z}-x_0\|<\sqrt{\varepsilon}$ and $\|\overline{y}-\overline{z}\|<\sqrt{\varepsilon}$ such that $$0\in \partial_P(f(\cdot) + \varepsilon\|\cdot-\overline{z}\|^2)(\overline{y}) \ \text{ and } \ f(\overline{y})\leq f(x_0) $$ by the sum rule for proximal subdifferential it follows that $$(a-\overline{y})+\varepsilon(\overline{z}-\overline{y})\in N_S^P(\overline{y}),$$ in particular, $\overline{y}\in S$. Then, by the property of exercise we have \begin{align*} \langle (a-\overline{y})+\varepsilon(\overline{z}-\overline{y}),x-\overline{y}\rangle\leq 0 \ \text{ y } \ \langle (a-\overline{y})+\varepsilon(\overline{z}-\overline{y}),y-\overline{y}\rangle\leq 0. \end{align*} Then, $$\langle (a-\overline{y})+\varepsilon(\overline{z}-\overline{y}), a-\overline{y}\rangle\leq 0\Rightarrow \|a-\overline{y}\|^2\leq \varepsilon\langle \overline{y}-\overline{z},a-\overline{y}\rangle\leq \varepsilon \|\overline{y}-\overline{z}\|\cdot \|a-\overline{y}\|$$ therefore $\|a-\overline{y}\|\leq \varepsilon \|\overline{y}-\overline{z}\|\leq \varepsilon\sqrt{\varepsilon}\Rightarrow d_S(a)\leq \varepsilon\sqrt{\varepsilon}$. As $\varepsilon>0$ is arbitrary, it follows that $d_S(a)=0$, and then $a\in S$. $\blacksquare$