A forward-backward algorithm with different inertial terms for structured non-convex minimization problems. (English) Zbl 1522.90131
Summary: We investigate an inertial forward-backward algorithm in connection with the minimization of the sum of a non-smooth and possibly non-convex and a non-convex differentiable function. The algorithm is formulated in the spirit of the famous FISTA method; however, the setting is non-convex and we allow different inertial terms. Moreover, the inertial parameters in our algorithm can take negative values too. We also treat the case when the non-smooth function is convex, and we show that in this case a better step size can be allowed. Further, we show that our numerical schemes can successfully be used in DC-programming. We prove some abstract convergence results which applied to our numerical schemes allow us to show that the generated sequences converge to a critical point of the objective function, provided a regularization of the objective function satisfies the Kurdyka-Łojasiewicz property. Further, we obtain a general result that applied to our numerical schemes ensures convergence rates for the generated sequences and for the objective function values formulated in terms of the KL exponent of a regularization of the objective function. Finally, we apply our results to image restoration.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C30 | Nonlinear programming |
| 65K10 | Numerical optimization and variational techniques |
Keywords:
global optimization; inertial proximal-gradient algorithm; non-convex optimization; abstract convergence theorem; Kurdyka-Łojasiewicz inequality; KL exponent; convergence rateSoftware:
iPianoReferences:
| [1] | Alecsa, CD; László, SC; Pinţa, T., An extension of the second order dynamical system that models Nesterov’s convex gradient method, Appl Math Optim, 84, 1687-1716 (2021) · Zbl 1486.34050 |
| [2] | Alecsa, CD; László, SC; Viorel, A., A gradient-type algorithm with backward inertial steps associated to a nonconvex minimization problem, Numer Algor, 84, 485-512 (2020) · Zbl 1443.90277 |
| [3] | Alvarez, F.; Attouch, H., An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Anal., 9, 3-11 (2001) · Zbl 0991.65056 |
| [4] | Apidopoulos, V.; Aujol, JF; Dossal, C., Convergence rate of inertial Forward-Backward algorithm beyond Nesterov’s rule, Math. Program., 180, 137-156 (2020) · Zbl 1439.90055 |
| [5] | Attouch, H.; Bolte, J., On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 116, 5-16 (2009) · Zbl 1165.90018 |
| [6] | 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. Operat. Res., 35, 438-457 (2010) · Zbl 1214.65036 |
| [7] | 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, 91-129 (2013) · Zbl 1260.49048 |
| [8] | Attouch, H.; Peypouquet, J.; Redont, P., A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization, SIAM J. Optimiz., 24, 232-256 (2014) · Zbl 1295.90044 |
| [9] | Bauschke, HH; Combettes, PL, Convex Analysis and Monotone Operator Theory inHilbert Spaces (2011), New York: Springer, New York · Zbl 1218.47001 |
| [10] | Beck, A.: First-Order Methods in Optimization. SIAM, Philadelphia (2017) · Zbl 1384.65033 |
| [11] | Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., 2, 183-202 (2009) · Zbl 1175.94009 |
| [12] | Bégout, P.; Bolte, J.; Jendoubi, MA, On damped second-order gradient systems, J. Diff. Eq., 259, 3115-3143 (2015) · Zbl 1347.34082 |
| [13] | Bolte, J.; Daniilidis, A.; Lewis, A., The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optimiz., 17, 1205-1223 (2006) · Zbl 1129.26012 |
| [14] | Bolte, J.; Daniilidis, A.; Lewis, A.; Shiota, M., Clarke subgradients of stratifiable functions, SIAM J. Optimiz., 18, 556-572 (2007) · Zbl 1142.49006 |
| [15] | Bolte, J.; Daniilidis, A.; Ley, O.; Mazet, L., Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity, Trans. Am. Math. Soci., 362, 3319-3363 (2010) · Zbl 1202.26026 |
| [16] | Bolte, J.; Sabach, S.; Teboulle, M., Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 459-494 (2014) · Zbl 1297.90125 |
| [17] | Boţ, RI; Csetnek, ER, A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function, ESAIM: Contr. Optimis. Calc. Variat., 24, 463-477 (2018) · Zbl 1428.90128 |
| [18] | Boţ, RI; Csetnek, ER; Hendrich, C., Inertial Douglas-Rachford splitting for monotone inclusion problems, Appl. Math. Comput., 256, 472-487 (2015) · Zbl 1338.65145 |
| [19] | Boţ, RI; Csetnek, ER; László, SC, An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions, EURO J. Comput. Optimiz., 4, 3-25 (2016) · Zbl 1338.90311 |
| [20] | Boţ, RI; Nguyen, DK, The proximal alternating direction method of multipliers in the non-convex setting: convergence analysis and rates, Math. Operat. Res., 45, 682-712 (2020) · Zbl 1480.90198 |
| [21] | Chambolle, A.; Dossal, C., On the convergence of the iterates of the fast iterative shrinkage/thresholding algorithm, J. Optim. Theory Appl., 166, 968-982 (2015) · Zbl 1371.65047 |
| [22] | Chouzenoux, E.; Pesquet, JC; Repetti, A., Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function, J. Optim. Theory Appl., 162, 107-132 (2014) · Zbl 1318.90058 |
| [23] | Combettes, PL, Solving monotone inclusions via compositions of nonexpansive aver-aged operators, Optimization, 53, 475-504 (2004) · Zbl 1153.47305 |
| [24] | Combettes, PL; Glaudin, LE, Quasinonexpansive iterations on the affine hull of orbits: from mann’s mean value algorithm to inertial methods, SIAM J. Optimiz., 27, 2356-2380 (2017) · Zbl 1378.65119 |
| [25] | Cruz Neto, JX; Oliveira, PR; Soubeyran, A.; Souza, JCO, A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem, Ann. Oper. Res., 289, 313-339 (2020) · Zbl 1496.90065 |
| [26] | Frankel, P.; Garrigos, G.; Peypouquet, J., Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates, J. Optim. Theory Appl., 165, 874-900 (2015) · Zbl 1316.49039 |
| [27] | Garrigos, G.; Rosasco, L.; Villa, S., Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry, Math. Program. (2022) · Zbl 1512.90166 · doi:10.1007/s10107-022-01809-4 |
| [28] | Ghadimi, E., Feyzmahdavian, H.R., Johansson, M.: Global convergence of the heavy-ball method for convex optimization. 2015 European control conference (ECC), IEEE, pp. 310-315 (2015) |
| [29] | Hu, YH; Li, C.; Meng, KW; Qin, J.; Yang, XQ, Group sparse optimization via \(l_{p, q}\) regularization, J. Mach. Learn. Res., 30, 52 (2017) · Zbl 1433.90202 |
| [30] | Hu, Y.; Li, C.; Meng, K.; Yang, X., Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems, J. Glob. Optim., 79, 853-883 (2021) · Zbl 1465.90097 |
| [31] | Johnstone, PR; Moulin, P., Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions, Comput. Optim. Appl., 67, 259-292 (2017) · Zbl 1376.90046 |
| [32] | Johnstone, P.R., Moulin, P.: Convergence rates of inertial splitting schemes for nonconvex composite optimization. 2017 IEEE International conference on acoustics, speech and signal processing (ICASSP), pp. 4716-4720 (2017) |
| [33] | Kurdyka, K., On gradients of functions definable in o-minimal structures, Annales de l’institut Fourier (Grenoble), 48, 769-783 (1998) · Zbl 0934.32009 |
| [34] | László, SC, Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization, Math. Program., 190, 285-329 (2021) · Zbl 1478.90097 |
| [35] | Lessard, L.; Recht, B.; Packard, A., Analysis and design of optimization algorithms via integral quadratic constraints, SIAM J. Optimiz., 26, 57-95 (2016) · Zbl 1329.90103 |
| [36] | Liang, J.; Fadili, J.; Peyré, G., Activity identification and local linear convergence of inertial forward- backward splitting, SIAM J. Optimiz., 27, 408-437 (2017) · Zbl 1357.49064 |
| [37] | 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, (2016) |
| [38] | Li, G.; Pong, TK, Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods, Found. Comput. Math., 18, 1199-1232 (2018) · Zbl 1405.90076 |
| [39] | Łojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels, Les Équations aux Dérivées Partielles. Éditions du Centre National de la Recherche Scientifique Paris, 87-89 (1963) |
| [40] | Lorenz, DA; Pock, T., An inertial forward-backward algorithm for monotone inclusions, J. Math. Imaging Vis., 51, 311-325 (2015) · Zbl 1327.47063 |
| [41] | Mordukhovich, B., Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications. (2006), Berlin: Springer, Berlin |
| [42] | Moudafi, A.; Oliny, M., Convergence of a splitting inertial proximal method for monotone operators, J. Comp. Appl. Math., 155, 447-454 (2003) · Zbl 1027.65077 |
| [43] | Nesterov, Y., A method for solving the convex programming problem with convergence rate \(O(1/k^2)\), (Russian), Dokl. Akad. Nauk SSSR, 269, 3, 543-547 (1983) |
| [44] | Nesterov, Y., Introductory Lectures on Convex Optimization: a Basic Course (2004), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 1086.90045 |
| [45] | Ochs, P., Local convergence of the heavy-ball method and iPiano for non-convex optimization, J. Optim. Theory Appl., 177, 153-180 (2018) · Zbl 1404.90105 |
| [46] | Ochs, P.; Chen, Y.; Brox, T.; Pock, T., iPiano: inertial proximal algorithm for non-convex optimization, SIAM J. Imag. Sci., 7, 1388-1419 (2014) · Zbl 1296.90094 |
| [47] | Polyak, BT, Some methods of speeding up the convergence of iteration methods, U.S.S.R. Comput. Math. Math. Phys., 4, 1-17 (1964) · Zbl 0147.35301 |
| [48] | Rockafellar, RT; Wets, RJ-B, Variational Analysis, Fundamental Principles of Mathematical Sciences, 317 (1998), Berlin: Springer, Berlin · Zbl 0888.49001 |
| [49] | Su, W.; Boyd, S.; Candès, EJ, A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights, J. Mach. Learn. Res., 17, 1-43 (2016) · Zbl 1391.90667 |
| [50] | Sun, T., Yin, P., Li, D., Huang, C., Guan, L., Jiang, H.: Non-ergodic convergence analysis of heavy-ball algorithms, The Thirty-Third AAAI conference on artificial intelligence, (2019) |
| [51] | Wu, Z.; Li, M., General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems, Comput. Optimiz. Appl., 73, 129-158 (2019) · Zbl 1420.90054 |
| [52] | 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 |
| [53] | Zavriev, SK; Kostyuk, FV, Heavy-ball method in non-convex optimization problems, Comput. Math. Model., 4, 336-341 (1993) · Zbl 1331.90056 |
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.
