Proximal point algorithm

The proximal point algorithm seeks a zero of a monotone operator $F$ by repeatedly applying its resolvent:For $F=\partial f$, this is iteration of a proximal operator.

For two proximal maps $P_f,P_h$, define reflected maps $R_f=2P_f-I$ and $R_h=2P_h-I$. The Douglas--Rachford fixed-point map isBecause reflected proximal maps are nonexpansive, $T$ is firmly nonexpansive.

Finding a point in ${\bigcap }_{j=1}^{\ell }{C}_j$ is equivalent to intersecting the product $C_1\times \cdots \times C_{\ell }$ with the diagonal subspace in $({\mathbb{R}}^n{)}^{\ell }$. Projection onto the product is componentwise, while projection onto the diagonal replaces every component by their average.

Let $M$ be a real symmetric positive-definite matrix and $F$ a maximal monotone operator on a finite-dimensional Euclidean space, possibly set-valued. The preconditioned proximal point algorithm usesMaximal monotonicity guarantees that $T$ is defined everywhere. It is a firmly nonexpansive mapping in the weighted inner product $⟨x,y{⟩}_M=⟨x,My⟩$.

Indeed, if $x=Tu$ and $y=Tv$, operator monotonicity givesThis proves the firm bound and single-valuedness wherever the inverse exists; maximality supplies the full domain. With mere monotonicity, existence can fail. On $\mathbb{R}$, $F(x)=\mathrm{sign}x$ with $F(0)=0$ is monotone, but $x+F(x)=1/2$ has no solution. Its maximal monotone completion instead assigns the interval $[-1,1]$ at zero.