Inertial variable metric techniques for the inexact forward-backward algorithm. (English) Zbl 1401.65062
Summary: One of the most popular approaches for the minimization of a convex functional given by the sum of a differentiable term and a nondifferentiable one is the forward-backward method with extrapolation. The main reason making this method very appealing for a wide range of applications is that it achieves a \(\mathcal{O}(1/k^2)\) convergence rate in the objective function values, which is optimal for a first order method. Recent contributions on this topic are related to the convergence of the iterates to a minimizer and the possibility of adopting a variable metric in the proximal step. Moreover, it has been also proved that the objective function convergence rate is actually \({o}(1/k^2)\). However, these results are obtained under the assumption that the minimization subproblem involved in the backward step is computed exactly, which is clearly not realistic in a variety of relevant applications. In this paper, we analyze the convergence properties when both variable metric and inexact computation of the backward step are allowed. To do this, we adopt a suitable inexactness criterion and we devise implementable conditions on both the accuracy of the inexact backward step computation and the variable metric selection, so that the \({o}(1/k^2)\) rate and the convergence of the iterates are preserved. The effectiveness of the proposed approach is also validated with a numerical experience showing the effects of the combination of inexactness with variable metric techniques.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C25 | Convex programming |
| 90C30 | Nonlinear programming |
Keywords:
convex optimization; inertial forward-backward algorithms; inexact proximal operator; variable metric; image restorationReferences:
| [1] | H. Attouch and J. Peypouquet, The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than \(1/k^2\), SIAM J. Optim., 26 (2016), pp. 1824–1834. · Zbl 1346.49048 |
| [2] | H. H. Bauschke, J. Bolte, and M. Teboulle, A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications, Math. Oper. Res., 4 (2016), pp. 330–348. · Zbl 1364.90251 |
| [3] | H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books Math., Springer, New York, 2011. · Zbl 1218.47001 |
| [4] | A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process., 18 (2009), pp. 2419–2434. · Zbl 1371.94049 |
| [5] | A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183–202. · Zbl 1175.94009 |
| [6] | M. Bertero, P. Boccacci, G. Desiderà, and G. Vicidomini, Image deblurring with Poisson data: From cells to galaxies, Inverse Problems, 25 (2009), 123006. · Zbl 1186.85001 |
| [7] | M. Bertero, P. Boccacci, G. Talenti, R. Zanella, and L. Zanni, A discrepancy principle for Poisson data, Inverse Problems, 26 (2010), 105004. · Zbl 1200.62067 |
| [8] | D. Bertsekas, Convex Optimization Algorithms, in Convex Optimization Theory, Athena Scientific, 2012, pp. 251–489. |
| [9] | D. Bertsekas, Nonlinear Programming, Athena Scientific, Nashua, NH, 1999. · Zbl 1015.90077 |
| [10] | S. Bonettini, I. Loris, F. Porta, and M. Prato, Variable metric inexact line-search based methods for nonsmooth optimization, SIAM J. Optim., 26 (2016), pp. 891–921. · Zbl 1338.65157 |
| [11] | S. Bonettini, F. Porta, and V. Ruggiero, A variable metric forward-backward method with extrapolation, SIAM J. Sci. Comput., 38 (2016), pp. A2558–A2584. · Zbl 1348.65092 |
| [12] | A. Chambolle and Ch. Dossal, On the convergence of the iterates of the “fast iterative shrinkage/thresholding algorithm,” J. Optim. Theory Appl., 166 (2015), pp. 968–982. · Zbl 1371.65047 |
| [13] | A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), pp. 120–145. · Zbl 1255.68217 |
| [14] | P. L. Combettes and J.-C. Pesquet, Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, eds., Springer Optim. Appl., Springer, New York, 2011, pp. 185–212. · Zbl 1242.90160 |
| [15] | P. L. Combettes and B. C. Vu͂, Variable metric quasi-Féjer monotonicity, Nonlinear Anal. Theory Methods Appl., 78 (2013), pp. 17–31. · Zbl 1266.65087 |
| [16] | L. Debnath and P. Mikusiński, Introduction to Hilbert Spaces with Applications, Academic Press, Boston, 1990. · Zbl 0715.46009 |
| [17] | F.-X. Dupè, M. J. Fadili, and J.-L. Starck, Inverse problems with Poisson noise: Primal and primal-dual splitting, in Proceedings of the 18th IEEE International Conference on Image Processing (ICIP), Brussels, 2011, pp. 1901–1904. |
| [18] | M. A. T. Figueiredo and J. M. Bioucas-Dias, Restoration of Poissonian images using alternating direction optimization, IEEE Trans. Image Process., 19 (2010), pp. 3133–3145. · Zbl 1371.94128 |
| [19] | P. C. Hansen, J. G. Nagy, and D. P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering, SIAM, Philadelphia, 2005. |
| [20] | Z. T. Harmany, R. F. Marcia, and R. M. Willett, This Is SPIRAL-TAP: Sparse Poisson Intensity Reconstruction ALgorithms—Theory and Practice, IEEE Trans. Image Process., 21 (2012), pp. 1084–1096. · Zbl 1372.94381 |
| [21] | J. B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms. II, Springer, New York, 1993. · Zbl 0795.49001 |
| [22] | L. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), pp. 259–268. · Zbl 0780.49028 |
| [23] | H. Lantéri, M. Roche, O. Cuevas, and C. Aime, 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 |
| [24] | D. Lorentz and T. Pock, An inertial forward-backward algorithm for monotone inclusion, J. Math. Imaging Vision, (2014), pp. 311–325. · Zbl 1327.47063 |
| [25] | I. Loris and C. Verhoeven, On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty, Inverse Problems, 27 (2011), 125007. · Zbl 1233.65039 |
| [26] | J. J. Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93 (1965), pp. 273–299. · Zbl 0136.12101 |
| [27] | Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Appl. Optim., Springer, New York, 2004. · Zbl 1086.90045 |
| [28] | P. Ochs, Y. Chen, T. Brox, and T. Pock, iPiano: Inertial proximal algorithm for non-convex optimization, SIAM J. Imaging Sci., 7 (2014), pp. 1388–1419. · Zbl 1296.90094 |
| [29] | T. Pock and A. Chambolle, Diagonal preconditioning for first order primal-dual algorithms in convex optimization, in Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2011, pp. 1762–1769. |
| [30] | B. T. Polyak, Some methods of speeding up the convergence of iteration methods, Comput. Math. Math. Phys., 4 (1964), pp. 1–17. · Zbl 0147.35301 |
| [31] | B. Polyak, Introduction to Optimization, Optimization Software, New York, 1987. · Zbl 0625.62093 |
| [32] | F. Porta and I. Loris, On some steplength approaches for proximal algorithms, Appl. Math. Comput., 253 (2015), pp. 345–362. · Zbl 1338.90464 |
| [33] | S. Salzo and S. Villa, Inexact and accelerated proximal point algorithms, J. Convex Anal., 19 (2012), pp. 1167–1192. · Zbl 1283.90030 |
| [34] | M. Schmidt, N. Le Roux, and F. Bach, Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization, preprint, arXiv:1109.2415v2, 2011. |
| [35] | S. Setzer, Operator splittings, Bregman methods and frame shrinkage in image processing, Int. J. Comput. Vis., 92 (2010), pp. 265–280. · Zbl 1235.68314 |
| [36] | S. Villa, S. Salzo, L. Baldassarre, and A. Verri, Accelerated and inexact forward-backward algorithms, SIAM J. Optim., 23 (2013), pp. 1607–1633. · Zbl 1295.90049 |
| [37] | R. M. Willett and R. D. Nowak, Platelets: A multiscale approach for recovering edges and surfaces in photon limited medical imaging, IEEE Trans. Med. Imaging, 22 (2003), pp. 332–350. |
| [38] | A. Zalinescu, Convex Analysis in General Vector Spaces, World Scientific, River Edge, NJ, 2002. · Zbl 1023.46003 |
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.
