Proving Lipshitz continuous over a convex set with Projection Operator

Question

Suppose a problem $$\min_{x \in \mathbb{R}^{n}} f(x)$$

subject to $x \in \Omega$ which is a closed and convex set. If $\nabla f(x)$ is Lipschitz continuous in $\Omega$, then prove that

$$e(x) = x - P_{\Omega}(x- \nabla f(x))$$

is also Lipschitz continuous in $\Omega$.

Thanks in advance.

Answer 1

The key is that projection onto a convex set is non-expansive, that is, for any two points $x, y$, $$ \| P_{\Omega}(x) - P_{\Omega}(y)\| \le \|x-y\|. $$ Now, we assume that $\nabla f(y)$ is Lipschitz continuous on $\Omega$, i.e., there exists some constant $L$ such that $$ \| \nabla f(x) - \nabla f(y)\| \le L\cdot \|x-y\| $$ for any $x, y \in \Omega$. Then, for any two points $x,y \in \Omega$, we have \begin{align} \|e(x)-e(y)\| &= \|x - P_{\Omega}(x- \nabla f(x)) - y + P_{\Omega}(y- \nabla f(y))\|\\ &= \|x - y + P_{\Omega}(y- \nabla f(y)) - P_{\Omega}(x- \nabla f(x))\|\\ &\le \|x - y\| + \| P_{\Omega}(y- \nabla f(y)) - P_{\Omega}(x- \nabla f(x))\|\\ &\le \|x - y\| + \| y- \nabla f(y) - x+ \nabla f(x)\|\\ &\le \|x - y\| + \| y- x \| +\|\nabla f(x) - \nabla f(y)\|\\ &\le \|x - y\| + \| y- x \| + L\|x-y\|\\ &= (2+L) \cdot \|x-y\|, \end{align} where we have repeatedly applied triangle inequality, and exploited the non-expansiveness of the projection onto a convex set, as well as the Lipschitz continuity of $\nabla f(x)$.

The above implies that $e(x)$ is Lipschitz continuous on $\Omega$ with constant $L+2$.

Answer 2

You need to show that $P_\Omega$ is Lipschitz.

In general, $\hat{x}$ minimises a convex function $g$ over a convex set $C$ iff $\langle \nabla g(\hat{x}), c-x \rangle \ge 0$ for all $c \in C$.

Taking $g(c) = {1 \over 2} \|c -x \|^2$, we see that $\hat{c}$ minimises $g$ over $\Omega$ iff $\langle \hat{c}-x, c-\hat{c} \rangle \ge 0$ for all $c \in \Omega$.

Hence we have $\langle p_\Omega(x)-x, c-p_\Omega(x) \rangle \ge 0$ for all $c \in \Omega$. In particular, we have $\langle p_\Omega(x)-x, p_\Omega(y)-p_\Omega(x) \rangle \ge 0$ or $\langle p_\Omega(x), p_\Omega(y)-p_\Omega(x) \rangle \ge \langle x, p_\Omega(y)-p_\Omega(x) \rangle$ for any $x,y$.

Then \begin{eqnarray} \|p_\Omega(x)-p_\Omega(y)\|^2 &=& \langle p_\Omega(x)-p_\Omega(y), p_\Omega(x)-p_\Omega(y)\rangle \\ &=& \langle p_\Omega(x), p_\Omega(x)-p_\Omega(y)\rangle - \langle p_\Omega(y), p_\Omega(x)-p_\Omega(y)\rangle \\ &\le& \langle x, p_\Omega(x)-p_\Omega(y) \rangle - \langle y, p_\Omega(x)-p_\Omega(y) \rangle \\ &=& \langle x-y, p_\Omega(x)-p_\Omega(y) \rangle \\ &\le & \| x- y\| \| p_\Omega(x)-p_\Omega(y)\| \end{eqnarray} From which we get $\| p_\Omega(x)-p_\Omega(y)\| \le \|x-y\|$.

Then you have \begin{eqnarray} \|e(x)-e(y)\| &\le& \|x-y\| + \|p_\Omega(x-\nabla f(x))-p_\Omega(y-\nabla f(y))\| \\ &\le& \|x-y\| + \|x-\nabla f(x)-(y-\nabla f(y))\| \\ &\le& 2 \|x-y\| + L \|x-y\| \end{eqnarray}