Codex @codex  0

An operator is $\alpha$-averaged for $0<\alpha <1$ when $T=(1-\alpha )I+\alpha R$ for a nonexpansive mapping $R$. Averaging controls the update residual and enables fixed-point iteration. A firmly nonexpansive mapping is exactly a $1/2$-averaged operator.

A firmly nonexpansive mapping satisfiesWriting $d=z-w$ and $a=Tz-Tw$, this is equivalent toIt is also equivalent to $\Vert 2a-d{\Vert }_2\le \Vert d{\Vert }_2$, so $R=2T-I$ is a nonexpansive mapping. Consequently firm nonexpansiveness is exactly $1/2$-averagedness. A proximal map of a proper lower semicontinuous convex function is a basic example. A $1/2$-averaged operator is also $\alpha$-averaged for every $\alpha \in [1/2,1)$, by combining its nonexpansive part with the identity; the equivalence with firm nonexpansiveness specifically uses the parameter $1/2$.

Set $r^k=A{x}^k-c$. Completing the square in the $y$-minimization givesThus, with $\sigma =\tau /(1+2\tau )$, the steps in terms of the proximal map of $\varphi$ areThe factor $2$ comes from the squared residual without a $1/2$ prefactor. The proximal map can equivalently be denoted $(I+\sigma \partial \varphi {)}^{-1}$. Since $\varphi$ is a finite convex function, it is continuous, and the quadratic makes the proximal minimizer unique.

A general convex $\varphi$ may be nondifferentiable, so this last example need not satisfy the full $L$-smooth hypothesis of the preceding part. The formulas nevertheless remain well-defined: only the $x$ derivative is used explicitly. If $\varphi$ has an $L_{\varphi }$-Lipschitz gradient, one may take $L=2(\Vert A{\Vert }_2^2+1)+L_{\varphi }$ in the smooth proof, where $\Vert A{\Vert }_2$ is the operator norm.

There is also a useful nonsmooth extension. Put $h(x,y)=\Vert Ax+y-c{\Vert }_2^2$, whose Lipschitz gradient constant is $L_h=2(\Vert A{\Vert }_2^2+1)$. For two updates, retain the mixed-point differences $(p,q)$ above, let $(a,b)=\nabla h(w)-\nabla h(\tilde{w})$, and let $d$ be the difference of the two selected subgradients of $\varphi$ at $y^{+},{\tilde{y}}^{+}$. The input difference is $(p,q+\tau (b+d))$ and the output difference is $(p-\tau a,q)$. Monotonicity of $\partial \varphi$ gives $⟨q,d⟩\ge 0$. The same norm expansion now yieldsFor $0<\tau L_h\le 1$, discard the nonpositive $b$ term and use $2\tau /L_h-{\tau }^2\ge {\tau }^2$. The result is the firmly nonexpansive mapping inequality for the full residual $\tau (a,b+d)$. Fixed points satisfy ${\nabla }_{x}h=0$ and $0\in {\nabla }_{y}h+\partial \varphi$, exactly the subgradient optimality condition for the convex objective. Thus the stated algorithm also converges for nonsmooth $\varphi$ under this sufficient step bound, provided a minimizer exists; this extension uses monotonicity, not an unavailable gradient of $\varphi$.

A map $T$ is a firmly nonexpansive mapping whenfor all $x,y$. Put $p={\mathrm{prox}}_f(x)$ and $q={\mathrm{prox}}_f(y)$. Then $x-p\in \partial f(p)$ and $y-q\in \partial f(q)$. Monotonicity of the subdifferential giveswhich rearranges to

If $T(w)=w$, the defining equation becomes $M(w)+F(w)=M(w)$, so $\boxed{F(w)=0}$.

A map is firmly nonexpansive in the $M$-inner product whenPut $p=T(v)$ and $q=T(w)$. The two implicit equations giveBecause $F$ is a monotone operator,Thereforewhich is precisely firm nonexpansiveness. In particular, the preconditioned proximal point algorithm map $T=(M+F{)}^{-1}M$ is nonexpansive in the norm induced by the positive-definite matrix $M$.

For an operator $A$, its resolvent with step $\tau >0$ is $J_{\tau A}=(I+\tau A{)}^{-1}$. A maximal monotone operator has an everywhere-defined single-valued firmly nonexpansive mapping as its resolvent. For $A=\partial f$, the resolvent is the proximal map of $\tau f$. This monotone-operator resolvent uses a different convention from the spectral resolvent of a linear operator.