Monotone Operators and the Proximal Point Algorithm

TLDR

The proximal point algorithm is important for duality‑based computational methods, notably the Hestenes‑Powell multiplier method in nonlinear programming. The study generalizes the proximal point algorithm by replacing exact minimization with an arbitrary maximal monotone operator and establishes convergence under implementable criteria. The algorithm iteratively minimizes \(f(z)+\frac{1}{2c_k}\|z-z^k\|^2\) with step sizes \(c_k>0\), extends to the case \(T=\partial f\), and is applied to related minimax problems. Convergence is proven under practical criteria, with a typically linear rate that can become superlinear as the step sizes grow.

Abstract

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^k \} $ by taking $z^{k + 1} $ to be the minimizes of $f(z) + ({1 / {2c_k }})\| {z - z^k } \|^2 $, where $c_k > 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 $\partial 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_k $ stays large enough, in fact superlinear if $c_k \to \infty $. The case of $T = \partial f$ is treated in extra detail. Application is also made to a related case corresponding to minimax problems.