×

Asymptotic convergence analysis of the proximal point algorithm. (English) Zbl 0533.49028

This paper is an outstanding contribution to the analysis of the proximal point algorithm for the solution of the equation 0\(\in Tz\), T a maximal monotone mapping in a Hilbert space H. Let \(P_ k=(I+c_ kT)^{-1}\) be the ”proximal” mapping, \(c_ k>0\), then the algorithm generates the sequence \(Z^{k+1}=P_ kZ^ k\) starting from any \(Z^ 0\in H\). The \(Z^{k+1}\) is approximately computed by the criterion \[ | Z^{k+1}-P_ kZ^ k| \leq \epsilon_ k\min \{1,| Z^{k+1}- Z^ k|^ r\} \] where \(r\geq 0\), \(\epsilon_ k\geq 0\), \(\sum^{\infty}_{k=0}\epsilon_ k<+\infty\). If the set of solutions \(\bar Z=\{z\in H;0\in Tz\}\) is nonempty, the author gives sufficient conditions for linear, superlinear or sublinear convergence of the algorithm involving various assumptions on the coefficients \(c_ k\) and on the growth properties of \(T^{-1}\) around \(\bar Z\). The latter are in the form: There exist \(\delta>0\) such that for all \(w\in B(0,\delta)\) and all \(z\in T^{-1}w\) it follows that \(| z-\bar Z| \leq f(| w|)\) with \(f:[0,+\infty)\to [0,+\infty)\) continuous and \(f(0)=0\). The sharpness of the given convergence rate as well as comparison with previously obtained results and applications are discussed by means of several enlightening examples.
Reviewer: D.Tiba

MSC:

49M99 Numerical methods in optimal control
47J25 Iterative procedures involving nonlinear operators
65J15 Numerical solutions to equations with nonlinear operators
47H05 Monotone operators and generalizations
90C55 Methods of successive quadratic programming type
93B05 Controllability
90C25 Convex programming
49M29 Numerical methods involving duality