On the Convergence of the Proximal Point Algorithm for Convex Minimization (Q3978027)

This paper studies convergence properties of the proximal point algorithm (PPA) for the convex minimization problem \(\min_{x\in H}f(x)\), where \(f: H\mapsto R\cup\{\infty\}\) is a proper, lower-semicontinuous (\(lsc\)) function in a Hilbert space \(H\). In the literature, the convergence properties of the PPA are studied only in the case where \(f\) has a minimizer, and the convergence rate of the algorithm is given only in the case where \(f\) is strongly convex. In this paper, the authors give convergence of the PPA under the weakest conditions, even in cases where \(f\) has no minimizer, or is unbounded from below. Convergence rate results are given in terms of the residual \(f(x_ k)-f(u)\) where \(u\) is an arbitrary point in \(H\) rather than in terms of the closeness of \(x_ k\) to a minimizer of \(f\). Under the minimal condition that \(f\) is proper, lower-semicontinuous, it is proved that the PPA, with positive parameters \(\{\lambda_ k\}_{k=1}^ \infty\), converges in general if and only if \(\sigma_ n=\sum_{k=1}^ n \lambda_ k\to \infty\). An open question of Rockafellar is settled by giving an example of a PPA for which \(x_ n\) converges weakly but not strongly to a minimizer of \(f\).