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 = +.