Abstract

We present inexact accelerated proximal point algorithms for minimizing a proper lower semicontinuous and convex function. We carry on a convergence analysis under different types of errors in the evaluation of the proximity operator, and we provide corresponding convergence rates for the objective function values. The proof relies on a generalization of the strategy proposed by O. Güler ["New proximal point algorithms for convex minimization", SIAM J. Optimization 2(4) (1992) 649–664] for generating estimate sequences according to the definition of Nesterov, and is based on the concept of ε-subdifferential. We show that the convergence rate of the exact accelerated algorithm 1/k21/k^2 can be recovered by constraining the errors to be of a certain type.

Author information

Contact details are reproduced from the original publication and may be historical.

Silvia Villa

Istituto Italiano di Tecnologia, Via Morego 30, 16163 Genova, Italy

silvia.villa@ut.it

Keywords

  • Accelerated proximal point algorithms
  • global convergence rates
  • approximation criteria

Mathematics Subject Classification

90C25, 49D37, 65K10

References

  1. A. Auslender: Numerical methods for nondifferentiable convex optimization, Math. Program. Study 30 (1987) 102–126.https://doi.org/10.1007/BFb0121157Google Scholar
  2. A. Beck, M. Teboulle: Fast gradient-based algorithms for constrained total variation image denoising and deblurring, IEEE Trans. Image Process 18(11) (2009) 2419–2434.https://doi.org/10.1109/TIP.2009.2028250Google Scholar
  3. A. Beck, M. Teboulle: A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2(1) (2009) 183–202.https://doi.org/10.1137/080716542Google Scholar
  4. S. Becker, J. Bobin, E. Candes: NESTA: A fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci. 4(1) (2011) 1–39.https://doi.org/10.1137/090756855Google Scholar
  5. J. Bect, L. Blanc-Féraud, G. Aubert, A. Chambolle: A ℓ1 -unified variational framework for image restoration, in: Computer Vision – ECCV 2004 (Prague, 2004), Part IV, T. Pajdla, J. Matas (eds.), Lecture Notes in Computer Science 3024, Springer, Berlin (2004) 1–13.https://doi.org/10.1007/978-3-540-24673-2_1Google Scholar
  6. J. R. Birge, L. Qi, Z. Wei: Convergence analysis of some methods for minimizing a nonsmooth convex function, J. Optim. Theory Appl. 97(2) (1998) 357–383.https://doi.org/10.1023/A:1022630801549Google Scholar
  7. R. S. Burachik, A. N. Iusem, B. F. Svaiter: Enlargement of monotone operators with applications to variational inequalities, Set-Valued Anal. 5(2) (1997) 159–180.https://doi.org/10.1023/A:1008615624787Google Scholar
  8. R. S. Burachik, B. F. Svaiter: A relative error tolerance for a family of generalized proximal point methods, Math. Oper. Res. 26(4) (2001) 816–831.https://doi.org/10.1287/moor.26.4.816.10011Google Scholar
  9. A. Chambolle: An algorithm for total variation minimization and applications, J. Math. Imaging Vis. 20(1–2) (2004) 89–97.https://doi.org/10.1023/B:JMIV.0000011325.36760.1eGoogle Scholar
  10. P. L. Combettes, J.-C. Pesquet: Proximal splitting methods in signal processing, in: Fixed-Point Algorithms for Inverse Problems in Science and Engineering (Banff, 2009), H. H. Bauschke, R. Burachik, P. L. Combettes, V. Elser, D. R. Luke, H. Wolkowicz (eds.), Springer, New York (2010) 185–212.https://doi.org/10.1007/978-1-4419-9569-8_10Google Scholar
  11. P. L. Combettes, V. R. Wajs: Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4(4) (2005) 1168–1200.https://doi.org/10.1137/050626090Google Scholar
  12. R. Cominetti: Coupling the proximal point algorithm with approximation methods, J. Optim. Theory Appl. 95(3) (1997) 581–600.https://doi.org/10.1023/A:1022621905645Google Scholar
  13. R. Correa, C. Lemaréchal: Convergence of some algorithms for convex minimization, Math. Program., Ser. B 62(2) (1993) 261–275.https://doi.org/10.1007/BF01585170Google Scholar
  14. M. Fornasier (ed.): Theoretical Foundations and Numerical Methods for Sparse Recovery (Vienna, 2009), Radon Series on Computational and Applied Mathematics 9, De Gruyter, Berlin (2010).https://doi.org/10.1515/9783110226157.93Google Scholar
  15. O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim. 29(2) (1991) 403–419.https://doi.org/10.1137/0329022Google Scholar
  16. O. Güler: New proximal point algorithms for convex minimization, SIAM J. Optim. 2(4) (1992) 649–664.https://doi.org/10.1137/0802032Google Scholar
  17. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms II, Grundlehren der Mathematischen Wissenschaften 306, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  18. L. Jacob, G. Obozinski, J.-P. Vert: Group lasso with overlap and graph lasso, in: ICML 2009 (Montréal, 2009), L. Bottou et al. (ed.), ACM, New York (2009) 433–440.https://doi.org/10.1145/1553374.1553431Google Scholar
  19. B. Lemaire. About the convergence of the proximal method, in: Advances in Optimization (Lambrecht, 1991), W. Oettli et al. (ed.), Lecture Notes in Econom. and Math. Systems 382, Springer, Berlin (1992) 39–51.https://doi.org/10.1007/978-3-642-51682-5_4Google Scholar
  20. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér. 4 (R-3) (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  21. R. D. C. Monteiro, B. F. Svaiter: Convergence rate of inexact proximal point methods with relative error criteria for convex optimization, preprint (2010).Google Scholar
  22. J.-J. Moreau: Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. Fr. 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  23. S. Mosci, L. Rosasco, M. Santoro, A. Verri, S. Villa: Solving structured sparsity regularization with proximal methods, in: Machine Learning and Knowledge Discovery in Databases (Barcelona, 2010), Part II, J. Balcázar, F. Bonchi, A. Gionis, M. Sebag (eds.), Lecture Notes in Computer Science 6322, Springer, Berlin (2010) 418–433.https://doi.org/10.1007/978-3-642-15883-4_27Google Scholar
  24. A. S. Nemirovsky, D. B. Yudin: Problem Complexity and Method Efficiency in Optimization, Wiley, New York (1983).Google Scholar
  25. Y. Nesterov: Introductory Lectures on Convex Optimization. A Basic Course, Applied Optimization 87, Kluwer, Boston (2004).https://doi.org/10.1007/978-1-4419-8853-9Google Scholar
  26. Y. E. Nesterov: On an approach to the construction of optimal methods for minimizing smooth convex functions, Ehkon. Mat. Metody 24(3) (1988) 509–517.Google Scholar
  27. R. T. Rockafellar: Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1(2) (1976) 97–116.https://doi.org/10.1287/moor.1.2.97Google Scholar
  28. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14(5) (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  29. M. V. Solodov, B. F. Svaiter: A comparison of rates of convergence of two inexact proximal point algorithms, in: Nonlinear Optimization and Related Topics (Erice, 1998), G. Di Pillo et al. (ed.), Appl. Optim. 36, Kluwer, Dordrecht (2000) 415–427.https://doi.org/10.1007/978-1-4757-3226-9_22Google Scholar
  30. M. V. Solodov, B. F. Svaiter: Error bounds for proximal point subproblems and associated inexact proximal point algorithms, Math. Program., Ser. B 88(2) (2000) 371–389.https://doi.org/10.1007/s101070050022Google Scholar
  31. M. V. Solodov, B. F. Svaiter: An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions, Math. Oper. Res. 25(2) (2000) 214–230.https://doi.org/10.1287/moor.25.2.214.12222Google Scholar
  32. M. V. Solodov, B. F. Svaiter: A unified framework for some inexact proximal point algorithms, Numer. Funct. Anal. Optim. 22(7–8) (2001) 1013–1035.https://doi.org/10.1081/NFA-100108320Google Scholar
  33. P. Tseng: On accelerated proximal gradient methods for convex-concave optimization, Technical Report (2008), SIAM J. Optim., submitted.Google Scholar
  34. C. Zălinescu: Convex Analysis in General Vector Spaces, World Scientific, River Edge (2002).https://doi.org/10.1142/5021Google Scholar
  35. A. Zaslavski: Convergence of a proximal point method in the presence of computational errors in Hilbert spaces, SIAM J. Optim. 20(5) (2010) 2413–2421.https://doi.org/10.1137/090766930Google Scholar

Suggested citation

S. Salzo, S. Villa. “Inexact and Accelerated Proximal Point Algorithms.” Journal of Convex Analysis 19 (2012), No. 4, 1167–1192. https://doi.org/10.68381/jca19062

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2012. Rights now held by Banach Press LLC.