Show that $x^*$ is minimizer of the function over $C$ if $x^*=\prod_C (x^*- \gamma \nabla f(x^*))$.

Question

Assume $f: \mathbb{R}^n \rightarrow\mathbb{R}$ be a differentiable convex function and $C \subseteq\mathbb{R}^n$ be a closed convex set, and $\gamma >0$. Consider the following problem

$$ \min_{x \in C}f(x) $$

Show that $x^*$ is minimizer of the function over $C$ if $x^*=\prod_C (x^*- \gamma \nabla f(x^*))$.

To prove the above we need to use optimality condition as follows

$$ \langle\nabla f(x^*),x-x^* \rangle \geq0\,\,\, \forall x\in C $$

Also, Variational Inequality for projection onto a closed convex set

$$ \langle x-\Pi_C (x),z-\Pi_C (x) \rangle \leq0\,\,\, \forall z\in C $$

Answer 1

Since $x^*$ is global minimizer we have $$ \langle\nabla f(x^*),x-x^* \rangle \geq0\,\,\, \forall x\in C $$

Because $\gamma > 0$

$$ \langle -\gamma \nabla f(x^*),x-x^* \rangle \leq0\,\,\, \forall x\in C $$

Add and subtract $x^*$ to get

$$ \langle \Big(x^*-\gamma \nabla f(x^*)\Big)-x^*,x-x^* \rangle \leq0\,\,\, \forall x\in C $$

Compare with the Variational Inequality and note that $x^*-\gamma \nabla f(x^*) is \notin C$

$$ \langle x-\Pi_C (x),z-\Pi_C (x) \rangle \leq0\,\,\, \forall z\in C $$

so $x^*$ should be $\Pi_C (x^*-\gamma \nabla f(x^*))$ to have VI to be true.