# 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. – Theo Bendit May 24 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. – VHarisop May 24 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)$. – Theo Bendit May 24 at 0:49
• You are right, it makes sense to assume $S$ should be closed. – VHarisop May 24 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^*$$).
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.