Projection onto unit ball before or after minimizing.

181 Views Asked by At

Suppose $f: \mathbf{R}^n \to \mathbf{R}$ is a convex, differentiable function. Apparently the following statement is true for any $x$,

$$ P(x - \alpha \nabla f(x)) \in \mathrm{argmin}_{y : \|y\| \leq 1} \left( 2\alpha \cdot \nabla f(x)^T(y - x) + \|x - y\|^2 \right) \qquad \text{for all $\alpha > 0$.} $$

Here, $P$ denotes the projection operator onto the unit ball. Is there a nice way to see this?

Importantly, it should be noted that $$x - \alpha \nabla f(x)$$ is the unique element in $$\mathrm{argmin}_{y \in \mathbf{R}^n} \left( 2\alpha \cdot \nabla f(x)^T(y - x) + \|x - y\|^2 \right)$$ (Note the change of the domain of the minimization.) Thus, this question is really asking, how to show that projecting after minimizing onto the unit ball is the same as minimizing over the unit ball itself for convex $f$.

1

There are 1 best solutions below

2
On BEST ANSWER

Basic algebra. Complete the square in $y$, namely rewrite

$\alpha \nabla f(x)^T(y-x) + \frac{1}{2}\|x - y\|^2 = \frac{1}{2}\|y - (x - \alpha\nabla f(x))\|^2 -\frac{1}{2}\|\alpha\nabla f(x)\|^2$, so that

$$ \operatorname{argmin}_{y \in C}\alpha \nabla f(x)^T(y-x) + \frac{1}{2}\|x - y\|^2 = \operatorname{argmin}_{y \in C}\frac{1}{2}\|y - (x - \alpha\nabla f(x))\|^2 =: P_C(x-\alpha\nabla f(x)), $$

where $C$ is any closed convex subset of your Hilbert space $H$ (in your particular problem, $\mathcal H = \mathbb R^n$ and $C$ is the unit ball for a norm).