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.

Fix $x$ with nonempty subdifferential $\partial h(x)$ for a convex function $h$. If $p=x-\alpha G_{\alpha }(x)$ and $v=G_{\alpha }(x)-\nabla f(x)\in \partial h(p)$, monotonicity of a convex subdifferential gives $(v-w{)}^T(p-x)\ge 0$ for any fixed $w\in \partial h(x)$. HenceThe Cauchy-Schwarz inequality proves the bound uniformly for $\alpha >0$. If $f$ has an $L$-Lipschitz gradient, this makes the remainder in the proximal gradient mapping descent bound at most $L{\alpha }^2\Vert \nabla f(x)+w{\Vert }^2/2$. Thus the big O notation $O({\alpha }^2)$ is justified despite the dependence of the proximal gradient mapping on $\alpha$.

Target: convex-optimization.bigb, under Coordinate descent.

For $\varphi =f+h$, with $f$ a convex function having an $L$-Lipschitz gradient and $h$ a proper convex function with a well-defined proximal operator, the proximal gradient method with step size $1/L$ satisfies the displayed bound whenever a global minimizer $x^{\ast }$ exists. The one-step subgradient inequality and descent lemma giveThe objective function values are nonincreasing. A telescoping sum over $j=0,\dots ,k-1$, followed by comparison of the last error with the arithmetic mean of the errors, proves the result. The bound controls the last objective function error without requiring a strongly convex function or a unique minimizer.

Target: convex-optimization.bigb, under Proximal gradient method.

For a convex function $h$ with a well-defined proximal operator, and a differentiable function $f$, the proximal gradient mapping is the displacement of one proximal gradient method update divided by its positive step size $\alpha$. Writing $p=x-\alpha G_{\alpha }(x)$, the subgradient optimality condition gives $G_{\alpha }(x)-\nabla f(x)\in \partial h(p)$. For convex functions $f,h$, its zeros are precisely the global minimizers of $f+h$, by the subgradient optimality condition and subdifferential sum rule. When $h=0$, it is the ordinary gradient.

Target: convex-optimization.bigb, under Proximal gradient method.

Let $f:{\mathbb{R}}^p\times {\mathbb{R}}^q\to \mathbb{R}$ be a differentiable convex function whose full gradient is $L$-Lipschitz continuous, with $L>0$. The alternating update first solves the implicit $y$ step and then the explicit $x$ step:The implicit step is the proximal operator of $\tau f(x,\cdot )$, so it exists uniquely. The gradient bound must control the full joint variable; smoothness alone supplies no global constant $L$.

For two updates, let $(p,q)$ be the difference of their mixed points $(x,y^{+})$ and $(a,b)$ the corresponding full gradient difference. The input and output differences are $(p,q+\tau b)$ and $(p-\tau a,q)$. The mixed-point norm identity for alternating updates and Baillon–Haddad theorem giveHence $T$ is a $(\tau L/2)$-averaged operator for $0<\tau L<2$. Its fixed points have both block gradients zero and are exactly the global minimizers of $f$. If a minimizer exists, Browder convergence theorem for averaged operators gives norm convergence of iteration in the stated finite-dimensional setting.

Let $h:{\mathbb{R}}^p\times {\mathbb{R}}^q\to \mathbb{R}$ be convex with an $L_h$-Lipschitz gradient, $L_h>0$, and let $\varphi :{\mathbb{R}}^q\to \mathbb{R}\cup \{+\infty \}$ be a proper lower semicontinuous convex function. For $f(x,y)=h(x,y)+\varphi (y)$, takeThe proper closed convex assumption on $\varphi$ ensures that the implicit section has a well-defined proximal operator.

For two mixed points with difference $(p,q)$, write $(a,b)$ for the gradient difference of $h$ and $w$ for the difference of the selected subgradients of $\varphi$. Inputs differ by $(p,q+\tau (b+w))$ and outputs by $(p-\tau a,q)$. Monotonicity of a convex subdifferential gives $⟨q,w⟩\ge 0$, while cocoercivity gives $⟨p,a⟩+⟨q,b⟩\ge L_h^{-1}(\Vert a{\Vert }^2+\Vert b{\Vert }^2)$. Expanding these squared norms provesfor $0<\tau L_h\le 1$. Thus the combined update is firmly nonexpansive. Its fixed points are the minimizers of $h+\varphi$; if one exists, the Browder convergence theorem for averaged operators gives norm convergence in finite dimensions.

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.