Existence, resolvent characterization, and firm nonexpansiveness of the proximal map

If $n=0$, [F10] gives ${\mathbb{R}}^0=\{0\}$. Properness [F1] forces $g(0)$ to be finite. Every input $v$, candidate $u$, competitor $z$ and subgradient vector $p$ is $0$. The objective in [F8] has only the candidate $0$, so ${\mathrm{prox}}_{tg}(0)=\{0\}$. The inequality in [F7] is $g(0)\ge g(0)+0$, so $\mathrm{\partial }g(0)=\{0\}$ and $(v-u)\mathrm{/}t=0\in \mathrm{\partial }g(0)$; both directions of the resolvent equivalence hold. Firm nonexpansiveness and nonexpansiveness both reduce to $0\le 0$. This proves every conclusion for $n=0$ without compactness or an affine-minorant argument. For the remainder assume $n\ge 1$.

Define $H(x)=g(x)+\mathrm{\parallel }x-v{\mathrm{\parallel }}_2^2\mathrm{/}(2t)$. The quadratic is finite and continuous, and the identity $\mathrm{\parallel }(1-\theta )x+\theta y-v{\mathrm{\parallel }}_2^2=(1-\theta )\mathrm{\parallel }x-v{\mathrm{\parallel }}_2^2+\theta \mathrm{\parallel }y-v{\mathrm{\parallel }}_2^2-\theta (1-\theta )\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2$ shows it is convex. Thus [F3] makes $H$ proper, closed and convex. Choose $x_0\in \mathrm{dom}g$ and put $c=H(x_0)$. Then $S=\{x:H(x)\le c\}$ is nonempty and closed: it is the inverse image of $\mathrm{epi}H$ under the continuous map $x\mapsto (x,c)$.

By [F2], completing the square gives $H(x)\ge b+⟨a,x⟩+\frac{\mathrm{\parallel }x-v{\mathrm{\parallel }}_2^2}{2t}=b+⟨a,v⟩-\frac{t}{2}\mathrm{\parallel }a{\mathrm{\parallel }}_2^2+\frac{1}{2t}\mathrm{\parallel }x-(v-ta){\mathrm{\parallel }}_2^2\mathrm{.}$ Thus $H(x)\le c$ forces $x$ into a fixed-radius ball, so $S$ is bounded and hence compact by [F4]. The restriction $H{\mathrm{\mid }}_S$ is real-valued; each weak sublevel set is the intersection of $S$ with the inverse image of $\mathrm{epi}H$ under $x\mapsto (x,r)$ for its level $r$, hence closed in $S$. By [F6] it is lower semicontinuous, so [F5] gives a minimizer on $S$. Every point outside $S$ has value greater than $c$, while the minimum on $S$ is at most $c$, so this minimizer is global.

The quadratic satisfies $\mathrm{\parallel }\frac{x+y}{2}-v{\mathrm{\parallel }}_2^2=\frac{1}{2}\mathrm{\parallel }x-v{\mathrm{\parallel }}_2^2+\frac{1}{2}\mathrm{\parallel }y-v{\mathrm{\parallel }}_2^2-\frac{1}{4}\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2$. If two distinct points minimized $H$, convexity of $g$ and this identity would make their midpoint have strictly smaller value, a contradiction. Hence the global minimizer is unique, proving the singleton claim.

Suppose $u$ minimizes $H$ and fix $z\in \mathrm{dom}g$. For $0<\alpha <1$, convexity gives $g(u+\alpha (z-u))\le (1-\alpha )g(u)+\alpha g(z)$. Minimality and expansion of the quadratic therefore imply $0\le H(u+\alpha (z-u))-H(u)\le \alpha (g(z)-g(u)+\frac{⟨u-v,z-u⟩}{t})+\frac{{\alpha }^2}{2t}\mathrm{\parallel }z-u{\mathrm{\parallel }}_2^2\mathrm{.}$ Divide by $\alpha$ and let $\alpha \downarrow 0$; the parenthesized term is nonnegative. The same subgradient inequality is automatic for $z\mathrm{\notin }\mathrm{dom}g$, so $(v-u)\mathrm{/}t\in \mathrm{\partial }g(u)$.

Conversely, if $(v-u)\mathrm{/}t\in \mathrm{\partial }g(u)$, then for every finite-valued $g(z)$ the subgradient inequality and $\mathrm{\parallel }z-v{\mathrm{\parallel }}_2^2-\mathrm{\parallel }u-v{\mathrm{\parallel }}_2^2=\mathrm{\parallel }z-u{\mathrm{\parallel }}_2^2+2⟨u-v,z-u⟩$ give $H(z)-H(u)\ge \mathrm{\parallel }z-u{\mathrm{\parallel }}_2^2\mathrm{/}(2t)\ge 0$. Infinite-valued competitors cannot lower $H$, so $u$ is the unique minimizer from step 2.2. This proves the reverse implication.

Let $u_i={\mathrm{prox}}_{tg}(v_i)$ and $p_i=(v_i-u_i)\mathrm{/}t$. From step 3.1, $p_i\in \mathrm{\partial }g(u_i)$. Applying the two subgradient inequalities with $(u_1,u_2)$ and $(u_2,u_1)$ and adding yields $⟨p_1-p_2,u_1-u_2⟩\ge 0$. Substitution and multiplication by $t>0$ give $\mathrm{\parallel }{u}_1-u_2{\mathrm{\parallel }}_2^2\le ⟨u_1-u_2,v_1-v_2⟩$. By [F9] the right side is at most $\mathrm{\parallel }{u}_1-u_2{\mathrm{\parallel }}_2\mathrm{\parallel }{v}_1-v_2{\mathrm{\parallel }}_2$; if $u_1=u_2$ nonexpansiveness is immediate, and otherwise division gives it.