×

Convergence of inexact forward-backward algorithms using the forward-backward envelope. (English) Zbl 1452.65105

Summary: This paper deals with a general framework for inexact forward-backward algorithms aimed at minimizing the sum of an analytic function and a lower semicontinuous, subanalytic, convex term. Such a framework relies on an implementable inexactness condition for the computation of the proximal operator and on a linesearch procedure, which is possibly performed whenever a variable metric is allowed into the forward-backward step. The main focus of this work is the convergence of the considered scheme without additional convexity assumptions on the objective function. Toward this aim, we employ the recent concept of forward-backward envelope to define a continuously differentiable surrogate function, which coincides with the objective at its stationary points and satisfies the so-called Kurdyka-Łojasiewicz (KL) property on its domain. We adapt the abstract convergence scheme usually exploited in the KL framework to our inexact forward-backward scheme, prove the convergence of the iterates to a stationary point of the problem, and prove the convergence rates for the function values. Finally, we show the effectiveness and the flexibility of the proposed framework on a large-scale image restoration test problem.

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

iPiano; UNLocBoX; SPIRAL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H. Attouch and J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 116 (2009), pp. 5-16. · Zbl 1165.90018
[2] H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35 (2010), pp. 438-457. · Zbl 1214.65036
[3] H. Attouch, J. Bolte, and B. F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137 (2013), pp. 91-129. · Zbl 1260.49048
[4] G. R. Ayers and J. C. Dainty, Iterative blind deconvolution method and its applications, Opt. Lett., 13 (1988), pp. 547-549.
[5] F. Bach, R. Jenatton, J. Mairal, and G. Obozinski, Structured sparsity through convex optimization, Stat. Sci., 27 (2012), pp. 450-468. · Zbl 1331.90050
[6] J. Barzilai and J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), pp. 141-148. · Zbl 0638.65055
[7] S. Becker, J. Fadili, and P. Ochs, On quasi-Newton forward-backward splitting: Proximal calculus and convergence, SIAM J. Optim., 29 (2019), pp. 2445-2481, https://doi.org/10.1137/18M1167152. · Zbl 1461.65128
[8] M. Benning, L. Gladden, D. Holland, C.-B. Schönlieb, and T. Valkonen, Phase reconstruction from velocity-encoded MRI measurements-a survey of sparsity-promoting variational approaches, J. Magn. Reson., 238 (2014), pp. 26-43.
[9] M. Bertero, P. Boccacci, and V. Ruggiero, Inverse Imaging with Poisson Data, IOP Publishing, 2018.
[10] E. G. Birgin, J. M. Martinez, and M. Raydan, Inexact spectral projected gradient methods on convex sets, IMA J. Numer. Anal., 23 (2003), pp. 539-559. · Zbl 1047.65042
[11] J. Bolte, A. Daniilidis, and A. Lewis, The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17 (2007), pp. 1205-1223, https://doi.org/10.1137/050644641. · Zbl 1129.26012
[12] J. Bolte, A. Daniilidis, O. Ley, and L. Mazet, Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity, Trans. Amer. Math. Soc., 362 (2010), pp. 3319-3363. · Zbl 1202.26026
[13] J. Bolte, S. Sabach, and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146 (2014), pp. 459-494. · Zbl 1297.90125
[14] 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, https://doi.org/10.1137/15M1019325. · Zbl 1338.65157
[15] S. Bonettini, I. Loris, F. Porta, M. Prato, and S. Rebegoldi, On the convergence of a linesearch based proximal-gradient method for nonconvex optimization, Inverse Problems, 33 (2017), 055005. · Zbl 1373.65040
[16] S. Bonettini, M. Prato, and S. Rebegoldi, A block coordinate variable metric linesearch based proximal gradient method, Comput. Optim. Appl., 71 (2018), pp. 5-52. · Zbl 1405.90123
[17] S. Bonettini, S. Rebegoldi, and V. Ruggiero, Inertial variable metric techniques for the inexact forward-backward algorithm, SIAM J. Sci. Comput., 40 (2018), pp. A3180-A3210, https://doi.org/10.1137/17M116001X. · Zbl 1401.65062
[18] R. H. Byrd, S. L. Hansen, J. Nocedal, and Y. Singer, A stochastic Quasi-Newton method for large-scale optimization, SIAM J. Optim., 26 (2016), pp. 1008-1031, https://doi.org/10.1137/140954362. · Zbl 1382.65166
[19] 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
[20] A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40 (2011), pp. 120-145. · Zbl 1255.68217
[21] A. Chambolle and T. Pock, On the ergodic convergence rates of a first-order primal-dual algorithm, Math. Program., 159 (2016), pp. 253-287. · Zbl 1350.49035
[22] E. Chouzenoux, J.-C. Pesquet, and A. Repetti, 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. 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
[24] P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4 (2005), pp. 1168-1200, https://doi.org/10.1137/050626090. · Zbl 1179.94031
[25] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. · Zbl 1062.90001
[26] R. Fletcher, A limited memory steepest descent method, Math. Program., 135 (2012), pp. 413-436. · Zbl 1254.90113
[27] P. Frankel, G. Garrigos, and J. Peypouquet, Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates, J. Optim. Theory Appl., 165 (2015), pp. 874-900. · Zbl 1316.49039
[28] G. Frassoldati, G. Zanghirati, and L. Zanni, New adaptive stepsize selections in gradient methods, J. Ind. Manag. Optim., 4 (2008), pp. 299-312. · Zbl 1161.90524
[29] M. Girolami and C. He, Probability density estimation from optimally condensed data samples, IEEE Trans. Pattern Anal. Mach. Intell., 25 (2003), pp. 1253-1264.
[30] R. Glowinski, S. J. Osher, and W. Yin, Splitting Methods in Communication, Imaging, Science, and Engineering, Springer, New York, 2016. · Zbl 1362.65002
[31] Z. Harmany, R. Marcia, and R. 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
[32] B. Horn and B. Schunck, Determining optical flow, Artif. Intell., 17 (1981), pp. 185-203. · Zbl 1497.68488
[33] H. Lantéri, M. Roche, and C. Aime, Penalized maximum likelihood image restoration with positivity constraints: Multiplicative algorithms, Inverse Problems, 18 (2002), pp. 1397-1419. · Zbl 1023.62099
[34] 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
[35] C. Lee and S. J. Wright, Inexact successive quadratic approximation for regularized optimization, Comput. Optim. Appl., 72 (2019), pp. 641-674. · Zbl 1420.90045
[36] T. Liu and T. K. Pong, Further properties of the forward-backward envelope with applications to difference-of-convex programming, Comput. Optim. Appl., 67 (2017), pp. 489-520. · Zbl 1400.90279
[37] S. Łojasiewicz, Une propriété topologique des sous-ensembles analytiques réels, in Les Équations aux Dérivées Partielles, Éditions du Centre National de la Recherche Scientifique, Paris, 1963, pp. 87-89. · Zbl 0234.57007
[38] 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
[39] 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, https://doi.org/10.1137/130942954. · Zbl 1296.90094
[40] F. Porta, M. Prato, and L. Zanni, A new steplength selection for scaled gradient methods with application to image deblurring, J. Sci. Comput., 65 (2015), pp. 895-919. · Zbl 1328.65138
[41] M. Prato, A. L. Camera, S. Bonettini, and M. Bertero, A convergent blind deconvolution method for post-adaptive-optics astronomical imaging, Inverse Problems, 29 (2013), 065017. · Zbl 1286.68477
[42] M. Raginsky, R. Willett, Z. Harmany, and R. Marcia, Compressed sensing performance bounds under Poisson noise, IEEE Trans. Signal Process., 58 (2010), pp. 3990-4002. · Zbl 1392.94417
[43] S. Rebegoldi, L. Bautista, L. B. Fèraud, M. Prato, L. Zanni, and A. Plata, A comparison of edge-preserving approaches for DIC microscopy, Inverse Problems, 33 (2017), 085009. · Zbl 1397.78047
[44] R. T. Rockafellar, R. J.-B. Wets, and M. Wets, Variational Analysis, Springer, Berlin, 1998. · Zbl 0888.49001
[45] L. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, J. Phys. D, 60 (1992), pp. 259-268. · Zbl 0780.49028
[46] M. Schmidt, N. Le Roux, and F. Bach, Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization, preprint, https://arxiv.org/abs/1109.2415v2, 2011.
[47] F. Sciacchitano, Y. Dong, and T. Zeng, Variational approach for restoring blurred images with Cauchy noise, SIAM J. Imaging Sci., 8 (2015), pp. 1894-1922, https://doi.org/10.1137/140997816. · Zbl 1343.94014
[48] L. Stella, A. Themelis, and P. Patrinos, Forward-backward quasi-Newton methods for nonsmooth optimization problems, Comput. Optim. Appl., 30 (2017), pp. 1-45. · Zbl 1401.90226
[49] S. Villa, S. Salzo, L. Baldassarre, and A. Verri, Accelerated and inexact forward-backward algorithms, SIAM J. Optim., 23 (2013), pp. 1607-1633, https://doi.org/10.1137/110844805. · Zbl 1295.90049
[50] Y. Xu and W. Yin, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., 6 (2013), pp. 1758-1789, https://doi.org/10.1137/120887795. · Zbl 1280.49042
[51] 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.