Asymptotic Convergence Analysis of the Forward-Backward Splitting Algorithm

The asymptotic convergence of the forward-backward splitting algorithm for solving equations of type 0 ∈ T(z) is analyzed, where T is a multivalued maximal monotone operator in the n-dimensional Euclidean space. When the problem has a nonempty solution set, and T is split in the form T = ℱ + h with ℱ being maximal monotone and h being co-coercive with modulus greater than ½, convergence rates are shown, under mild conditions, to be linear, superlinear or sublinear depending on how rapidly ℱ⁻¹ and h⁻¹ grow in the neighborhoods of certain specific points.

As a special case, when both ℱ and h are polyhedral functions, we get R-linear convergence and 2-step Q-linear convergence without any further assumptions on the strict monotonicity on T or on the uniqueness of the solution. As another special case when h = 0, the splitting algorithm reduces to the proximal point algorithm, and we get new results, which complement R. T. Rockafellar's and F. J. Luque's earlier results on the proximal point algorithm.