A new proximal heavy ball inexact line-search algorithm. (English) Zbl 07850973
Summary: We study a novel inertial proximal-gradient method for composite optimization. The proposed method alternates between a variable metric proximal-gradient iteration with momentum and an Armijo-like linesearch based on the sufficient decrease of a suitable merit function. The linesearch procedure allows for a major flexibility on the choice of the algorithm parameters. We prove the convergence of the iterates sequence towards a stationary point of the problem, in a Kurdyka-Łojasiewicz framework. Numerical experiments on a variety of convex and nonconvex problems highlight the superiority of our proposal with respect to several standard methods, especially when the inertial parameter is selected by mimicking the Conjugate Gradient updating rule.
MSC:
| 90C30 | Nonlinear programming |
References:
| [1] | Abbas, B.; Attouch, H., Dynamical systems and forward-backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator, Optimization, 64, 10, 2223-2252, 2015 · Zbl 1345.34115 |
| [2] | Attouch, H.; Bolte, J.; Redont, P.; Soubeyran, A., Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35, 2, 438-457, 2010 · Zbl 1214.65036 |
| [3] | Attouch, H.; Bolte, J.; Svaiter, BF, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137, 1-2, 91-129, 2013 · Zbl 1260.49048 |
| [4] | Attouch, H.; Peypouquet, J., The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than \(1/k^2\), SIAM J. Optim., 26, 3, 1824-1834, 2016 · Zbl 1346.49048 |
| [5] | Attouch, H.; Peypouquet, J.; Redont, P., A dynamical approach to an inertial forward-backward algorithm for convex minimization, SIAM J. Optim., 24, 1, 232-256, 2014 · Zbl 1295.90044 |
| [6] | Aujol, J-F; Dossal, Ch; Rondepierre, A., Convergence rates of the Heavy Ball method for quasi-strongly convex optimization, SIAM J. Optim., 32, 3, 1817-1842, 2022 · Zbl 1508.65061 |
| [7] | Aujol, J-F; Dossal, Ch; Rondepierre, A., FISTA is an automatic geometrically optimized algorithm for strongly convex functions, Math. Program., 34, 3, 307-327, 2023 |
| [8] | Barzilai, J.; Borwein, JM, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 1, 141-148, 1988 · Zbl 0638.65055 |
| [9] | Beck, A.; Teboulle, M., Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process., 18, 11, 2419-2434, 2009 · Zbl 1371.94049 |
| [10] | Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202, 2009 · Zbl 1175.94009 |
| [11] | Birgin, EG; Martinez, JM, A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43, 117-128, 2001 · Zbl 0990.90134 |
| [12] | Birgin, EG; Martinez, JM; Raydan, M., Inexact spectral projected gradient methods on convex sets, IMA J. Numer. Anal., 23, 4, 539-559, 2003 · Zbl 1047.65042 |
| [13] | Bolte, J.; Danilidis, A.; Lewis, A., The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 4, 1205-1223, 2007 · Zbl 1129.26012 |
| [14] | Bolte, J.; Sabach, S.; Teboulle, M., Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 1-2, 459-494, 2014 · Zbl 1297.90125 |
| [15] | Bonettini, S.; Franchini, G.; Pezzi, D.; Prato, M., Explainable bilevel optimization: An application to the Helsinki deblur challenge, Inverse Probl. Imaging, 17, 925-950, 2023 · Zbl 1515.94013 |
| [16] | Bonettini, S.; Loris, I.; Porta, F.; Prato, M., Variable metric inexact line-search based methods for nonsmooth optimization, SIAM J. Optim., 26, 2, 891-921, 2016 · Zbl 1338.65157 |
| [17] | Bonettini, S.; Loris, I.; Porta, F.; Prato, M.; Rebegoldi, S., On the convergence of a linesearch based proximal-gradient method for nonconvex optimization, Inverse Probl., 33, 5, 2017 · Zbl 1373.65040 |
| [18] | Bonettini, S.; Ochs, P.; Prato, M.; Rebegoldi, S., An abstract convergence framework with application to inertial inexact forward-backward methods, Comput. Optim. Appl., 84, 319-362, 2023 · Zbl 1516.90095 |
| [19] | Bonettini, S.; Prato, M.; Rebegoldi, S., New convergence results for the inexact variable metric forward-backward method, Appl. Math. Comput., 392, 2021 · Zbl 1474.65161 |
| [20] | Bonettini, S.; Rebegoldi, S.; Ruggiero, V., Inertial variable metric techniques for the inexact forward-backward algorithm, SIAM J. Sci. Comput., 40, 5, A3180-A3210, 2018 · Zbl 1401.65062 |
| [21] | Chambolle, A., An algorithm for Total Variation minimization and applications, J. Math. Imaging Vis., 20, 1-2, 89-97, 2004 · Zbl 1366.94048 |
| [22] | Chambolle, A.; Caselles, V.; Cremers, D.; Novaga, M.; Pock, T.; Fornasier, M., An Introduction to Total Variation for Image Analysis, Theoretical Foundations and Numerical Methods for Sparse Recovery, 263-340, 2010, Berlin, New York: De Gruyter, Berlin, New York · Zbl 1209.94004 |
| [23] | Chambolle, A.; Dossal, Ch, On the convergence of the iterates of the “Fast Iterative Shrinkage/Thresholding Algorithm”, J. Optim. Theory Appl., 166, 3, 968-982, 2015 · Zbl 1371.65047 |
| [24] | Chouzenoux, E.; Pesquet, J-C, A stochastic majorize-minimize subspace algorithm for online penalized least squares estimation, IEEE Trans. Signal Process., 65, 18, 4770-4783, 2017 · Zbl 1414.94135 |
| [25] | Chouzenoux, E.; Pesquet, J-C; Repetti, A., Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function, J. Optim. Theory Appl., 162, 1, 107-132, 2014 · Zbl 1318.90058 |
| [26] | Combettes, PL; Pesquet, J-C; Bauschke, HH; Burachik, RS; Combettes, PL; Elser, V.; Luke, DR; Wolkowicz, H., Proximal splitting methods in signal processing, Fixed-Point Algorithms for Inverse Problems in Science and Engineering, 185-212, 2011, New York, NY: Springer, New York, NY · Zbl 1242.90160 |
| [27] | Combettes, PL; Vũ, BC, Variable metric forward-backward splitting with applications to monotone inclusions in duality, Optimization, 63, 9, 1289-1318, 2014 · Zbl 1309.90109 |
| [28] | Combettes, PL; Wajs, VR, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 4, 1168-1200, 2005 · Zbl 1179.94031 |
| [29] | Crisci, S.; Porta, F.; Ruggiero, V.; Zanni, L., Hybrid limited memory gradient projection methods for box-constrained optimization problems, Comput. Optim. Appl., 84, 151-189, 2023 · Zbl 1510.90260 |
| [30] | Crisci, S., Rebegoldi, S., Toraldo, G., Viola, M.: Barzilai-Borwein-like rules in proximal gradient schemes for \(\ell_1\) regularized problems. Optim. Method Soft., in press. doi:10.1080/10556788.2023.2285489 |
| [31] | Ghadimi, E., Feyzmahdavian, H. R., Johansson, M.: Global convergence of the Heavy-ball method for convex optimization. In: 2015 European Control Conference (ECC), pp. 310-315 (2015) |
| [32] | Hager, WW; Zhang, H., A survey of nonlinear conjugate gradient methods, Pac. J. Optim., 2, 1, 35-58, 2006 · Zbl 1117.90048 |
| [33] | Lee, C-P; Wright, SJ, Inexact successive quadratic approximation for regularized optimization, Comput. Optim. Appl., 72, 3, 641-674, 2019 · Zbl 1420.90045 |
| [34] | Li, H., Lin, Z.: Accelerated proximal gradient methods for nonconvex programming. In: Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 28. Curran Associates Inc. (2015) |
| [35] | Liang, J., Fadili, J., Peyré, G.: A multi-step inertial forward-backward splitting method for non-convex optimization. In: Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 29. Curran Associates Inc. (2016) |
| [36] | Luo, H.; Chen, L., From differential equation solvers to accelerated first-order methods for convex optimization, Math. Program., 195, 1-2, 735-781, 2022 · Zbl 1515.65157 |
| [37] | Nesterov, Y., Smooth minimization of non-smooth functions, Math. Program., 103, 1, 127-152, 2005 · Zbl 1079.90102 |
| [38] | Ochs, P., Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano, SIAM J. Optim., 29, 1, 541-570, 2019 · Zbl 1411.32009 |
| [39] | Ochs, P.; Brox, T.; Pock, T., iPiasco: inertial proximal algorithm for strongly convex optimization, J. Math. Imaging Vis., 53, 171-181, 2015 · Zbl 1327.90219 |
| [40] | Ochs, P.; Chen, Y.; Brox, T.; Pock, T., iPiano: inertial proximal algorithm for non-convex optimization, SIAM J. Imaging Sci., 7, 2, 1388-1419, 2014 · Zbl 1296.90094 |
| [41] | Pock, T.; Sabach, S., Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems, SIAM J. Imaging Sci., 9, 4, 1756-1787, 2016 · Zbl 1358.90109 |
| [42] | Polyak, B., Introduction to Optimization, 1987, New York: Optimization Software - Inc., Publication Division, New York · Zbl 0625.62093 |
| [43] | Polyak, BT, Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys., 4, 1-17, 1964 · Zbl 0147.35301 |
| [44] | Porta, F.; Prato, M.; Zanni, L., A new steplength selection for scaled gradient methods with application to image deblurring, J. Sci. Comput., 65, 895-919, 2015 · Zbl 1328.65138 |
| [45] | Rebegoldi, S.; Calatroni, L., Scaled, inexact and adaptive generalized FISTA for strongly convex optimization, SIAM J. Optim., 32, 3, 2428-2459, 2022 · Zbl 1506.65078 |
| [46] | Repetti, A., Chouzenoux, E.: RestoVMFB Lab: Matlab Toolbox for image restoration with the variable metric forward-backward algorithm. http://www-syscom.univ-mlv.fr/ chouzeno/Logiciel.html (2013) |
| [47] | Rockafellar, RT, Convex Analysis, 1970, Princeton, NJ: Princeton University Press, Princeton, NJ · Zbl 0193.18401 |
| [48] | Rockafellar, RT; Wets, RJ-B; Wets, M., Variational Analysis, Grundlehren der Mathematischen Wissenschaften, 1998, Berlin: Springer, Berlin · Zbl 0888.49001 |
| [49] | Salzo, S., The variable metric forward-backward splitting algorithm under mild differentiability assumptions, SIAM J. Optim., 27, 4, 2153-2181, 2017 · Zbl 1375.65085 |
| [50] | Salzo, S.; Villa, S., Inexact and accelerated proximal point algorithms, J. Convex Anal., 19, 4, 1167-1192, 2012 · Zbl 1283.90030 |
| [51] | Tseng, P.; Yun, S., A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117, 1-2, 387-423, 2009 · Zbl 1166.90016 |
| [52] | Villa, S.; Salzo, S.; Baldassarre, L.; Verri, A., Accelerated and inexact forward-backward algorithms, SIAM J. Optim., 23, 3, 1607-1633, 2013 · Zbl 1295.90049 |
| [53] | Vollebregt, EAH, The bound-constrained conjugate gradient method for non-negative matrices, J. Optim. Theory Appl., 162, 931-953, 2014 · Zbl 1304.90153 |
| [54] | Wu, Z.; Li, C.; Li, M.; Lim, A., Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems, J. Glob. Optim., 79, 617-644, 2021 · Zbl 1466.90081 |
| [55] | Yang, L.: Proximal gradient method with extrapolation and line search for a class of nonconvex and nonsmooth problems. arXiv:1711.06831 (2021) |
| [56] | Yang, L., Toh, K.-C.: An inexact Bregman proximal gradient method and its inertial variants. arXiv:2109.05690 (2022) |
| [57] | Zalinescu, A.: Convex Analysis in General Vector Spaces. World Scientific Publishing, Singapore (2002) · Zbl 1023.46003 |
| [58] | Zanella, R.; Boccacci, P.; Zanni, L.; Bertero, M., Efficient gradient projection methods for edge-preserving removal of Poisson noise, Inverse Probl., 25, 4, 2009 · 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.
