Monotone Operators and the Proximal Point Algorithm

For the problem of minimizing a lower semicontinuous proper convex function f on a Hilbert space, the proximal point algorithm in exact form generates a sequence \ zᵏ \ by taking zk + 1 to be the minimizes of f(z) + (1 / 2cₖ )\| z - zᵏ \|², where cₖ > 0. This algorithm is of interest for several reasons, but especially because of its role in certain computational methods based on duality, such as the Hestenes-Powell method of multipliers in nonlinear programming. It is investigated here in a more general form where the requirement for exact minimization at each iteration is weakened, and the subdifferential ∂ f is replaced by an arbitrary maximal monotone operator T. Convergence is established under several criteria amenable to implementation. The rate of convergence is shown to be “typically” linear with an arbitrarily good modulus if cₖ stays large enough, in fact superlinear if cₖ → ∞. The case of T = ∂ f is treated in extra detail. Application is also made to a related case corresponding to minimax problems.