Optimization Online


The Proximal Point Algorithm Is $\mathcal{O}(1/\epsilon)$

dong Yunda(ydong***at***zzu.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/2012
Entry Accepted: 01/11/2012
Entry Last Modified: 01/11/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society