- The Proximal Point Algorithm Is $\mathcal{O}(1/\epsilon)$ dong Yunda(ydongzzu.edu.cn) Abstract: In this paper, we give two new results on the proximal point algorithm for finding a zero point of any given maximal monotone operator. First, we prove that if the sequence of regularization parameters is non-increasing then so is that of residual norms. Then, we use it to show that the proximal point algorithm can find an approximate zero point (assume the existence of such zero point) in at most $\mathcal{O}(1/\epsilon)$ outer iterations, where $\epsilon>0$ is the accuracy parameter described in the stopping criterion. Keywords: Monotone operator $\cdot$ Proximal point algorithm $\cdot$ Residual norm Category 1: Convex and Nonsmooth Optimization Citation: \bibitem{ma70} Martinet B.: Regularisation d'in\'{e}quations variationelles par approximations successives. Revue Francaise d'Informatique et de Recherche Operationelle. {\bf 4}, 154-158 (1970) \bibitem{ro76} Rockafellar R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. {\bf 14}, 877-898 (1976) \bibitem{more65} Moreau J.J.: Proximit\'{e} et dualit\'{e} dans un espace Hilbertien. Bulletin de la Soci\'{e}t\'{e} Math\'{e}matique de France. {\bf 93}, 273-299 (1965) \bibitem{mi62} Minty G.J.: Monotone (nonlinear) operators in Hilbert space. Duke Math. J. {\bf 29}, 341-346 (1962) \bibitem{za11} Zaslavski A.J.: Maximal monotone operators and the proximal point algorithm in the presence of computational errors, J. Optim. Theory Appl. {\bf 150}, 20-32 (2011) \bibitem{lu84} Luque F.J.: Asymptotic convergence analysis of the proximal point algorithm. SIAM J. Control Optim. {\bf 22}, 277-293, (1984) \bibitem{pe02} Pennanen T.: Local convergence of the proximal point algorithm and multiplier methods without monotonicity. Math. Oper. Res. {\bf 27}, 193-202 (2002) \bibitem{do06} Dong Y.D.: A new relative error criterion for the proximal point algorithm. Nonlinear Anal. {\bf 64}, 2143-2148 (2006) \bibitem{gu91} G\"{u}ler O.: On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. {\bf 29}, 403-419 (1991) Download: [PDF]Entry Submitted: 01/11/2012Entry Accepted: 01/11/2012Entry Last Modified: 01/11/2012Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.