Asymptotic Convergence Analysis of the Proximal Point Algorithm

Abstract

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