Let C be a nonempty, closed convex subset of X. Let $x,y\in X$. Show that $y=P_c(x)\iff y\in (Id + N_c)^{-1}(x)$.

Question

Liam looking for some pointers on where to stat with the following:

Let C be a nonempty, closed convex subset of X. Let $x,y\in X$. Show that $y=P_c(x)\iff y\in (Id + N_c)^{-1}(x)$.

Typical with projection problems of this sort I would try to use the fact that $$P_c(\bar{x})=\bar{c}\iff (\forall\; c\in C)\;\;\;\langle c-\bar{c},\bar{x}-\bar{c} \rangle\leq0$$ however, I am not sure how to tie this in with $y\in (Id + N_c)^{-1}(x)$.

Answer 1

You are almost there. Indeed, \begin{equation} \begin{split} y = P_C(x) \iff \langle z - y, x - y \rangle \le 0\text{ } \forall z \iff x - y \in N_C(y) &\iff x \in (\mathrm{Id} + N_C)(y)\\ &\iff y \in (\mathrm{Id} + N_C)^{-1}(x), \end{split} \end{equation} N.B. The inverse operator $(\mathrm{Id} + N_C)^{-1}$ is well-defined and single-valued because the convex cone operator $N_C$ is maximally monotone, being the subdifferential of the lower semi-continuous function $i_C$. See Rockafellar's Theorem A.

Still using the fact that $N_C = \partial i_C$, there is an alternative way to reach the same conclusion by simple invoking the fact that, in general $y = \mathrm{prox}_f(x) \iff x - y \in \partial f(y)$.