zbMATH — the first resource for mathematics

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 (do not use 65Hxx) 47H05 Monotone operators and generalizations 90C55 Methods of successive quadratic programming type 93B05 Controllability 90C25 Convex programming 49M29 Numerical methods involving duality
Full Text: