Scaling techniques for \(\epsilon\)-subgradient methods. (English) Zbl 1347.65106
Summary: The recent literature on first order methods for smooth optimization shows that significant improvements on the practical convergence behavior can be achieved with variable step size and scaling for the gradient, making this class of algorithms attractive for a variety of relevant applications. In this paper we introduce a variable metric in the context of the \(\epsilon\)-subgradient methods for nonsmooth, convex problems, in combination with two different step size selection strategies. We develop the theoretical convergence analysis of the proposed approach in the general framework of forward-backward \(\epsilon\)-subgradient splitting methods and we also discuss practical implementation issues. In order to illustrate the effectiveness of the method, we consider a specific problem in the image restoration framework and we numerically evaluate the effects of a variable scaling and of the step length selection strategy on the convergence behavior.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C25 | Convex programming |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
Keywords:
forward-backward \(\epsilon\)-subgradient method; variable metric; step size selection rules; scaled primal-dual hybrid gradient algorithm; TV restoration; convergence; nonsmooth convex problems; image restorationReferences:
| [1] | Y. I. Alber, A. N. Iusem, and M. V. Solodov, {\it On the projected subgradient method for nonsmooth convex optimization in a Hilbert space}, Math. Program., 81 (1998), pp. 23-35. · Zbl 0919.90122 |
| [2] | R. D. Asmundis, D. D. Serafino, F. Riccio, and G. Toraldo, {\it On spectral properties of steepest descent methods}, IMA J. Numer. Anal., 33 (2013), pp. 1416-1435. · Zbl 1321.65095 |
| [3] | A. Auslender and M. Teboulle, {\it Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational equalities}, Math. Program. Ser. B, 120 (2009), pp. 27-48. · Zbl 1190.90118 |
| [4] | J. M. Bardsley and A. Luttman, {\it Total variation-penalized Poisson likelihood estimation for ill-posed problems}, Adv. Comput. Math., 31 (2009), pp. 35-59. · Zbl 1171.94001 |
| [5] | J. M. Bardsley and J. G. Nagy, {\it Covariance-preconditioned iterative methods for nonnegatively constrained astronomical imaging}, SIAM J. Matrix Anal. A., 27 (2006), pp. 1184-1197. · Zbl 1102.65044 |
| [6] | J. Barzilai and J. M. Borwein, {\it Two-point step size gradient methods}, IMA J. Numer. Anal., 8 (1988), pp. 141-148. · Zbl 0638.65055 |
| [7] | H. H. Bauschke and P. L. Combettes, {\it Convex Analysis and Monotone Operator Theory in Hilbert Spaces}, CMS Books Math. Ouvrages Math. SMC, Springer, New York, 2011. · Zbl 1218.47001 |
| [8] | M. Bertero, P. Boccacci, G. Desiderà, and G. Vicidomini, {\it Image deblurring with Poisson data: From cells to galaxies}, Inverse Problems, 25 (2009), 123006. · Zbl 1186.85001 |
| [9] | M. Bertero, H. Lantéri, and L. Zanni, {\it Iterative image reconstruction: A point of view}, in Mathematical Methods in Biomedical Imaging and Intensity-Modulated Radiation Therapy (IMRT), Y. Censor, M. Jiang, and A. K. Louis, eds., Birkhäuser-Verlag, Pisa, Italy, 2008, pp. 37-63. |
| [10] | D. Bertsekas, {\it Convex optimization algorithms}, supplementary online chapter of Convex Optimization Theory, Athena Scientific, Nashua, NH, 2009, pp. 251-489; available online at http://www.athenasc.com/convexdualitychapter.pdf (accessed November 5, 2012). · Zbl 1242.90001 |
| [11] | S. Bonettini, A. Chiuso, and M. Prato, {\it A scaled gradient projection method for Bayesian learning in dynamical systems}, SIAM J. Sci. Comput., 37 (2015), pp. A1297-A1318. · Zbl 1461.65133 |
| [12] | S. Bonettini, G. Landi, E. L. Piccolomini, and L. Zanni, {\it Scaling techniques for gradient projection-type methods in astronomical image deblurring}, Int. J. Comput. Math., 90 (2013), pp. 9-29. · Zbl 1278.68326 |
| [13] | S. Bonettini, I. Loris, F. Porta, and M. Prato, {\it Variable metric inexact line-search-based methods for nonsmooth optimization}, SIAM J. Optim., 26 (2016), pp. 891-921. · Zbl 1338.65157 |
| [14] | S. Bonettini and M. Prato, {\it Nonnegative image reconstruction from sparse Fourier data: A new deconvolution algorithm}, Inverse Problems, 26 (2010), 095001. · Zbl 1201.94010 |
| [15] | S. Bonettini and V. Ruggiero, {\it An alternating extragradient method for total variation based image restoration from Poisson data}, Inverse Problems, 27 (2011), 095001. · Zbl 1252.94008 |
| [16] | S. Bonettini and V. Ruggiero, {\it On the convergence of primal-dual hybrid gradient algorithms for total variation image restoration}, J. Math. Imaging Vision, 44 (2012), pp. 236-253. · Zbl 1255.68210 |
| [17] | S. Bonettini and T. Serafini, {\it Non-negatively constrained image deblurring with an inexact interior point method}, J. Comput. Appl. Math., 231 (2009), pp. 236-248. · Zbl 1167.94003 |
| [18] | S. Bonettini, R. Zanella, and L. Zanni, {\it A scaled gradient projection method for constrained image deblurring}, Inverse Problems, 25 (2009), 015002. · Zbl 1155.94011 |
| [19] | U. Brännlund, K. C. Kiwiel, and P. O. Lindberg, {\it A descent proximal level bundle method for convex nondifferentiable optimization}, Oper. Res. Lett., 17 (1995), pp. 121-126. · Zbl 0843.90093 |
| [20] | K. Bredies and D. A. Lorentz, {\it Linear convergence of iterative soft-thresholding}, J. Fourier Anal. Appl., 14 (2008), pp. 813-837. · Zbl 1175.65061 |
| [21] | Y. Chen, W. W. Hager, M. Yashtini, X. Ye, and H. Zhang, {\it Bregman operator splitting with variable stepsize for total variation image reconstruction}, Comput. Optim. Appl., 54 (2012), pp. 317-342. · Zbl 1290.90071 |
| [22] | E. Chouzenoux, J.-C. Pesquet, and A. Repetti, {\it Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function}, J. Optim. Theory Appl., 162 (2014), pp. 107-132. · Zbl 1318.90058 |
| [23] | P. L. Combettes, {\it Quasi-Féjerian analysis of some optimization algorithms}, Stud. Comput. Math., 8 (2001), pp. 115-152. · Zbl 0992.65065 |
| [24] | P. L. Combettes and B. C. Vu͂, {\it Variable metric quasi-Féjer monotonicity}, Nonlinear Anal., 78 (2013), pp. 17-31. · Zbl 1266.65087 |
| [25] | P. L. Combettes and B. C. Vu͂, {\it Variable metric forward-backward splitting with applications to monotone inclusions in duality}, Optimization, 63 (2014), pp. 1289-1318. · Zbl 1309.90109 |
| [26] | L. Condat, {\it A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms}, J. Optim. Theory Appl., 158 (2013), pp. 460-479. · Zbl 1272.90110 |
| [27] | R. Correa and C. Lemaréchal, {\it Convergence of some algorithms for convex minimization}, Math. Program., 62 (1993), pp. 261-275. · Zbl 0805.90083 |
| [28] | J. Y. B. Cruz, {\it On proximal subgradient splitting method for minimizing the sum of two nonsmooth convex functions}, Set-Valued Var. Anal., in press, http://dx.doi.org/10.1007/s11228-016-0376-5 doi:10.1007/s11228-016-0376-5. · Zbl 1365.65160 |
| [29] | J. Y. B. Cruz and T. T. A. Nghia, {\it On the convergence of the forward-backward splitting method with linesearches}, Optim. Method Softw., in press, http://dx.doi.org/10.1080/10556788.2016.1214959 doi:10.1080/10556788.2016.1214959. · Zbl 1354.65116 |
| [30] | Y. H. Dai, W. W. Hager, K. Schittkowski, and H. Zhang, {\it The cyclic Barzilai-Borwein method for unconstrained optimization}, IMA J. Numer. Anal., 26 (2006), pp. 604-627. · Zbl 1147.65315 |
| [31] | G. d’Antonio and A. Frangioni, {\it Convergence analysis of detected conditional approximate subgradient methods}, SIAM J. Optim., 20 (2009), pp. 357-386. · Zbl 1187.90222 |
| [32] | F.-X. Dupé, M. Fadili, and J.-L. Starck, {\it Inverse problems with Poisson noise: Primal and primal-dual splitting}, in 18th IEEE International Conference on Image Processing (ICIP), Brussels, 2011, IEEE, Piscataway, NJ, 2011, pp. 1901-1904. |
| [33] | F.-X. Dupé, M. Fadili, and J.-L. Starck, {\it Linear inverse problems with various noise models and mixed regularizations}, in Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools, Brussels, 2011, Springer, Berlin, 2011, pp. 621-626. |
| [34] | Y. M. Ermoliev, {\it Stochastic quasigradient methods and their application to system optimization}, Stochastics, 9 (1983), pp. 1-36. · Zbl 0512.90079 |
| [35] | E. Esser, X. Zhang, and T. F. Chan, {\it A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science}, SIAM J. Imaging Sci., 3 (2010), pp. 1015-1046. · Zbl 1206.90117 |
| [36] | M. A. T. Figueiredo and J. M. Bioucas-Dias, {\it Restoration of Poissonian images using alternating direction optimization}, IEEE Trans. Image Process., 19 (2010), pp. 3133-3145. · Zbl 1371.94128 |
| [37] | R. Fletcher, {\it A limited memory steepest descent method}, Math. Program., 135 (2012), pp. 413-436. · Zbl 1254.90113 |
| [38] | G. Frassoldati, G. Zanghirati, and L. Zanni, {\it New adaptive stepsize selections in gradient methods}, J. Ind. Manag. Optim., 4 (2008), pp. 299-312. · Zbl 1161.90524 |
| [39] | J. L. Goffin, {\it On convergence rates of subgradient optimization methods}, Math. Program., 13 (1977), pp. 329-347. · Zbl 0368.90119 |
| [40] | J. L. Goffin and K. C. Kiwiel, {\it Convergence of a simple subgradient level method}, Math. Program., 85 (1999), pp. 207-211. · Zbl 0956.90032 |
| [41] | W. W. Hager, B. A. Mair, and H. Zhang, {\it An affine-scaling interior-point CBB method for box-constrained optimization}, Math. Program., 119 (2009), pp. 1-32. · Zbl 1168.90007 |
| [42] | W. W. Hager, M. Yashtini, and H. Zhang, {\it An O(1/k) convergence rate for the variable stepsize Bregman operator splitting algorithm}, SIAM J. Numer. Anal., 54 (2016), pp. 1535-1556. · Zbl 1381.49009 |
| [43] | B. He, Y. You, and X. Yuan, {\it On the convergence of primal-dual hybrid gradient algorithm}, SIAM J. Imaging Sci., 7 (2014), pp. 2526-2537. · Zbl 1308.90129 |
| [44] | J.-B. Hiriart-Urruty and C. Lemaréchal, {\it Convex Analysis and Minimization Algorithms}, Springer-Verlag, New York, 1993. · Zbl 0795.49001 |
| [45] | K. C. Kiwiel, {\it The effciency of subgradient projection methods for convex optimization, Part I: General level methods}, SIAM J. Control Optim., 34 (1996), pp. 660-676. · Zbl 0846.90084 |
| [46] | K. C. Kiwiel, {\it Effciency of subgradient projection methods for convex optimization, Part II: Implications and Extensions}, SIAM J. Control Optim., 34 (1996), pp. 677-697. · Zbl 0846.90085 |
| [47] | K. C. Kiwiel, {\it Convergence of approximate and incremental subgradient methods for convex optimization}, SIAM J. Optim., 14 (2004), pp. 807-840. · Zbl 1063.90039 |
| [48] | H. Lantéri, M. Roche, and C. Aime, {\it Penalized maximum likelihood image restoration with positivity constraints: Multiplicative algorithms}, Inverse Problems, 18 (2002), pp. 1397-1419. · Zbl 1023.62099 |
| [49] | H. Lantéri, M. Roche, O. Cuevas, and C. Aime, {\it A general method to devise maximum likelihood signal restoration multiplicative algorithms with non-negativity constraints}, Signal Process., 81 (2001), pp. 945-974. · Zbl 1080.94512 |
| [50] | T. Larsson, M. Patriksson, and A.-B. Strömberg, {\it On the convergence of conditional \(ϵ\)-subgradient methods for convex programs and convex-concave saddle-point problems}, European J. Oper. Res., 151 (2003), pp. 461-473. · Zbl 1053.90107 |
| [51] | D. A. Lorenz and T. Pock, {\it An inertial forward-backward algorithm for monotone inclusions}, J. Math. Imaging Vision, 51 (2015), pp. 311-325. · Zbl 1327.47063 |
| [52] | A. Nedić, {\it Subgradient Methods for Convex Minimization}, Ph.D. thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, Cambridge, MA, 2002, ŭlhttp://hdl.handle.net/1721.1/16843. |
| [53] | A. Nedic and D. P. Bertsekas, {\it Incremental subgradient methods for nondifferentiable optimization}, SIAM J. Optim., 12 (2001), pp. 109-138. · Zbl 0991.90099 |
| [54] | Y. Nesterov, {\it Introductory Lectures on Convex Optimization: A Basic Course}, Kluwer, Boston, 2004. · Zbl 1086.90045 |
| [55] | E. S. H. Neto and A. R. D. Pierro, {\it Incremental subgradients for constrained convex optimization: A unified framework and new methods}, Math. Program., 103 (2005), pp. 127-152. |
| [56] | B. Polyak, {\it Introduction to Optimization}, Optimization Software, NY, 1987. |
| [57] | M. Prato, A. L. Camera, S. Bonettini, and M. Bertero, {\it A convergent blind deconvolution method for post-adaptive-optics astronomical imaging}, Inverse Problems, 29 (2013), 065017. · Zbl 1286.68477 |
| [58] | S. M. Robinson, {\it Linear convergence of epsilon-subgradient descent methods for a class of convex functions}, Math. Program., Ser. A, 86 (1999), pp. 41-50. · Zbl 1029.90056 |
| [59] | R. T. Rockafellar, {\it Convex Analysis}, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401 |
| [60] | L. I. Rudin, S. Osher, and E. Fatemi, {\it Nonlinear total variation based noise removal algorithms}, J. Phys. D., 60 (1992), pp. 259-268. · Zbl 0780.49028 |
| [61] | S. Setzer, G. Steidl, and T. Teuber, {\it Deblurring Poissonian images by split Bregman techniques}, J. Vis. Commun. Image Represent., 21 (2010), pp. 193-199. |
| [62] | S. Shalev-Shwartz, {\it Online learning and online convex optimization}, Found. Trends Mach. Learn., 4 (2011), pp. 107-194. · Zbl 1253.68190 |
| [63] | N. Z. Shor, {\it Minimization Methods for Nondifferentiable Functions}, Springer-Verlag, Berlin, 1985. · Zbl 0561.90058 |
| [64] | M. V. Solodov and S. K. Zaviev, {\it Error stability properties of generalized gradient-type algorithms}, J. Optim. Theory Appl., 98 (1998), pp. 663-680. · Zbl 0913.90245 |
| [65] | C. Theys, N. Dobigeon, J.-Y. Tourneret, and H. Lantéri, {\it Linear unmixing of hyperspectral images using a scaled gradient method}, in Proceedings of the IEEE/SP 15th Workshop on Statistical Signal Processing, IEEE, Piscataway, NJ, 2009, pp. 729-732. |
| [66] | S. Villa, S. Salzo, L. Baldassarre, and A. Verri, {\it Accelerated and inexact forward-backward algorithms}, SIAM J. Optim., 23 (2013), pp. 1607-1633. · Zbl 1295.90049 |
| [67] | R. M. Willett and R. D. Nowak, {\it Platelets: A multiscale approach for recovering edges and surfaces in photon limited medical imaging}, IEEE Trans. Med. Imaging, 22 (2003), pp. 332-350. |
| [68] | R. Zanella, P. Boccacci, L. Zanni, and M. Bertero, {\it Efficient gradient projection methods for edge-preserving removal of Poisson noise}, Inverse Problems, 25 (2009), 045010. · Zbl 1163.65042 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
