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 |