×

On the convergence of the proximal point algorithm for convex minmization. (English) Zbl 0737.90047

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\).

MSC:

90C25 Convex programming
65K05 Numerical mathematical programming methods
49M37 Numerical methods based on nonlinear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI