Proximal operator (${\mathrm{prox}}_f$)

For a proper lower-semicontinuous convex function $f$, the proximal operator is ${\mathrm{prox}}_f(y)=\arg {\min }_x\{f(x)+\Vert x-y{\Vert }^2/2\}$. Its optimality condition is $y-x\in \partial f(x)$.

The Moreau envelope of a proper closed convex function isIt is differentiable even when $f$ is not, with $\nabla M_{t}f(x)=[x-{\mathrm{prox}}_{tf}(x)]/t$ and $1/t$-Lipschitz gradient.

For a nonempty closed convex set $C$, the squared-distance function is the Moreau envelope of its indicator functional of a constraint set. It is convex and differentiable withand this gradient is one-Lipschitz.

For $t>0$, the generalized Moreau decomposition is ${\mathrm{prox}}_{tf}(y)=y-t{\mathrm{prox}}_{t^{-1}{f}^{\ast }}(y/t)$, where $f^{\ast }$ is the convex conjugate.

For a nonempty closed convex set $C$, the Moreau decomposition and ${\sigma }_C^{\ast }={\iota }_C$ give ${\mathrm{prox}}_{t{\sigma }_C}(y)=y-t{\Pi }_C(y/t)$.

The proximal gradient method minimizes $g+h$, where $g$ has an $L$-Lipschitz gradient and $h$ is convex with a tractable proximal operator, by $x_{r+1}={\mathrm{prox}}_{\alpha h}(x_r-\alpha \nabla g(x_r))$. A standard choice $0<\alpha \le 1/L$ gives objective error $O(1/r)$ in the general convex case.