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 proximal map of $\tau \Vert \cdot {\Vert }_2$ sends $x$ to $(1-\tau /\Vert x{\Vert }_2{)}_{+}x$, with zero assigned at $x=0$. This removes vectors inside the radius-$\tau$ ball and shortens all larger vectors by a fixed radial distance. It is useful for groupwise sparsity.

On a Banach space one can define the set of minimizers of $E(x)+\Vert x-q{\Vert }^2/2$, but existence and uniqueness need additional geometry or coercivity hypotheses. The optimality condition is $0\in \partial E(x)+\mathcal{J}(x-q)$, with the duality mapping $\mathcal{J}=\partial (\Vert \cdot {\Vert }^2/2)$. The Hilbert completion-of-square shift by a dual vector does not generalize unchanged. On $({\mathbb{R}}^2,\Vert \cdot {\Vert }_1)$ with $E(x)=x_1+x_2$ and $q=0$, every $x_1,x_2\le 0$ with $x_1+x_2=-1$ is a minimizer; the vector $(-1,-1)$ is not one.

For a real Hilbert space, $E(x)=\alpha J(cx-y)+⟨x,z⟩$, $\alpha >0$ and $c\ne 0$, identify $z$ with its vector by the Riesz representation theorem. Completing the square in $\Vert x-q{\Vert }^2/2+⟨x,z⟩$ shifts the input to $q-z$. Substitute $v=cx-y$ and multiply by $c^2$ to obtain the displayed formula, valid also for negative $c$. If $c=0$ and $J(-y)<\infty$, the answer is $q-z$; if $J(-y)=\infty$, the objective is identically infinite and no proper proximal problem remains.

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 $r=\Vert x{\Vert }_2$, the Moreau envelope of the Euclidean norm is $r^2/(2\tau )$ when $r\le \tau$ and $r-\tau /2$ otherwise. Its gradient is $x/\tau$ in the core and $x/r$ outside. The approximation error is between zero and $\tau /2$.

For proper lower semicontinuous convex functions, the Moreau envelope has gradient $\nabla f_{\tau }=(I-{\mathrm{prox}}_{\tau f})/\tau$. This follows by subgradient inversion under convex conjugacy and the quadratic conjugate. Firm nonexpansiveness of the proximal residual makes the gradient $1/\tau$-Lipschitz continuous.

For a proper convex function with sequential lower semicontinuity $U=-\log \mu$, form $U_{\lambda }(x)={\inf }_y\{U(y)+\lambda \Vert x-y{\Vert }^2\}$ with $\lambda >0$. The Moreau envelope theorem gives $\nabla U_{\lambda }(x)=2\lambda (x-{\mathrm{prox}}_{U/(2\lambda )}(x))$. If $e^{-U_{\lambda }}$ is integrable, it defines a smooth surrogate probability density function. Infimizing the logarithm of a probability density function with a positive quadratic penalty has the opposite sign and does not generally smooth it. For the Laplace distribution, that incorrect operation leaves $-\log 2-|x|-1/(4\lambda )$, which is not differentiable at zero.

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.

The squared distance to a convex set is the infimal convolution of the set's indicator functional of a constraint set and the half-squared Hilbert space norm. Its convex conjugate is the sum of the half-squared norm and the support function of the set.

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.

This basic forward-backward update is one of the proximal gradient methods for learning.

For a jointly smooth convex function $f(x,y)$, update $y$ implicitly by its proximal minimization at fixed $x$, then update $x$ explicitly with the gradient at the mixed point $(x,y^{+})$. The combined map is $(\tau L/2)$-averaged for $0<\tau L<2$, as follows by applying cocoercivity at two mixed points. Its fixed points are precisely the minimizers. If a minimizer exists, averaged iteration proves convergence.

For $f(x,y)=h(x,y)+\varphi (y)$, where $h$ is convex with an $L_h$-Lipschitz gradient and $\varphi$ is convex, use a proximal $y$-step for the full section and an explicit $x$-step for $h$. Monotonicity of the two selected subgradients of $\varphi$ combines with cocoercivity of $\nabla h$ to make the full update firmly nonexpansive for $0<\tau L_h\le 1$. Existence of a minimizer then gives convergence, even though the full objective is not smooth.

For two mixed points with difference $(p,q)$ and gradient difference $(a,b)$, the input difference is $(p,q+\tau b)$ and the output difference is $(p-\tau a,q)$. Their squared-norm difference is $-2\tau (⟨p,a⟩+⟨q,b⟩)+{\tau }^2(\Vert a{\Vert }^2-\Vert b{\Vert }^2)$. This exact identity is a reusable way to prove averagedness without assuming the two block maps are individually nonexpansive.

The iterative soft-thresholding algorithm applies the proximal gradient method to $\Vert x{\Vert }_1+\frac{1}{2}\Vert Ax-y{\Vert }_2^2$:Here $S_{\tau }$ is coordinatewise soft thresholding. The objective is convex and coercive, so iterates converge to a minimizer in finite dimensions; uniqueness requires additional hypotheses.