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.

  • $\begingroup$ I'm assuming $S$ is closed? Any open subset of $X$ (including non-convex sets) will satisfy this condition. $\endgroup$ – Theo Bendit May 24 '19 at 0:43
  • $\begingroup$ @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. $\endgroup$ – VHarisop May 24 '19 at 0:46
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Theo Bendit May 24 '19 at 0:49
  • $\begingroup$ You are right, it makes sense to assume $S$ should be closed. $\endgroup$ – VHarisop May 24 '19 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.