Proximal normal cone and convex sets

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.

• I'm assuming $S$ is closed? Any open subset of $X$ (including non-convex sets) will satisfy this condition. May 24, 2019 at 0:43
• @TheoBendit: Could you elaborate? I don't see this in the problem statement. By the way, this is Problem 11.3 from Chapter 1 in Nonsmooth Analysis and Control Theory. May 24, 2019 at 0:46
• Sure. Note that $0 \in N_S^P(x)$ for all $x \in S$. If $x$ lies in the interior of $S$, then there can be no other element of $N_S^P(x)$, as $\zeta \in N_S^P(x)$ if and only if $x + t \zeta$ projects onto $S$ at $x$ for some $t > 0$. So, if $S$ is open, $N_S^P(x) = \{0\}$ for all $x$, which makes $\langle \zeta, x' - x \rangle = 0$ for $\zeta \in N_S^P(x)$. May 24, 2019 at 0:49
• You are right, it makes sense to assume $S$ should be closed. May 24, 2019 at 0:51

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.

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$$