Asymptotic Convergence Analysis of the Proximal Point Algorithm

The asymptotic convergence of the proximal point algorithm (PPA), for the solution of equations of type 0 ∈ Tz, where T is a multivalued maximal monotone operator in a real Hilbert space, is analyzed. When 0 ∈ Tz has a nonempty solution set Z, convergence rates are shown to depend on how rapidly T- 1 grows away from Z in a neighbourhood of 0. When this growth is bounded by a power function with exponent s, then for a sequence \ zᵏ \ generated by the PPA, \ | zᵏ - Z |\ converges to zero, like o(k^ - s / 2 ), linearly, superlinearly, or in a finite number of steps according to whether, s ∈ (0,1), $s = 1$, s ∈ (1, + ∞ ), or s = + ∞.