×

zbMATH — the first resource for mathematics

An inertial forward-backward algorithm for monotone inclusions. (English) Zbl 1327.47063
Summary: In this paper, we propose an inertial forward-backward splitting algorithm to compute a zero of the sum of two monotone operators, with one of the two operators being co-coercive. The algorithm is inspired by the accelerated gradient method of Nesterov, but can be applied to a much larger class of problems including convex-concave saddle point problems and general monotone inclusions. We prove convergence of the algorithm in a Hilbert space setting and show that several recently proposed first-order methods can be obtained as special cases of the general algorithm. Numerical results show that the proposed algorithm converges faster than existing methods, while keeping the computational cost of each iteration basically unchanged.

MSC:
47J25 Iterative procedures involving nonlinear operators
47J22 Variational and other types of inclusions
47N10 Applications of operator theory in optimization, convex analysis, mathematical programming, economics
47H05 Monotone operators and generalizations
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alvarez, F, Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space, SIAM J. Optim, 14, 773-782, (2003) · Zbl 1079.90096
[2] 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
[3] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011) · Zbl 1218.47001
[4] Beck, A; Teboulle, M, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202, (2009) · Zbl 1175.94009
[5] Becker, S; Fadili, J, A quasi-Newton proximal splitting method, Adv. Neural Info. Process. Sys., 25, 2627-2635, (2012)
[6] Bot, R.I., Csetnek, E.R.: An inertial alternating direction method of multipliers. Minimax Theory Appl., (2014). http://www.heldermann.de/MTA/MTA01/MTA011/mta01003.htm. · Zbl 1337.90082
[7] Bot, R.I., Csetnek, E.R., Hendrich, C.: Inertial Douglas-Rachford splitting for monotone inclusion problems. Technical report, arXiv:1403.3330, (2014) · Zbl 1338.65145
[8] Boyd, S; Parikh, N; Chu, E; Peleato, B; Eckstein, J, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1-122, (2011) · Zbl 1229.90122
[9] Bruck, R, On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space, J. Math. Anal. Appl., 61, 159-164, (1977) · Zbl 0423.47023
[10] Chambolle, A; Pock, T, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40, 120-145, (2011) · Zbl 1255.68217
[11] Chen, G; Rockafellar, R, Convergence rates in forward-backward splitting, SIAM J. Optim., 7, 421-444, (1997) · Zbl 0876.49009
[12] 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. 1-26 (2013) · Zbl 1318.90058
[13] Combettes, PL; Pesquet, J-C, Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued Variational Anal., 20, 307-330, (2012) · Zbl 1284.47043
[14] Combettes, P.L., Vũ, B.C.: Variable metric forward-backward splitting with applications to monotone inclusions in duality. Optimization, 63(9), 1289-1318 (2012) · Zbl 0991.65056
[15] Combettes, PL; Wajs, V, Signal recovery by proximal forward-backward splitting, SIAM Multiscale Model. Simul., 4, 1168-1200, (2005) · Zbl 1179.94031
[16] Condat, L, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158, 460-479, (2013) · Zbl 1272.90110
[17] Daubechies, I; Defrise, M; Mol, C, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math., 57, 1413-1457, (2004) · Zbl 1077.65055
[18] Douglas, J; Rachford, HH, On the numerical solution of heat conduction problems in two and three space variables, Trans. Am. Math. Soc., 82, 421-439, (1956) · Zbl 0070.35401
[19] Duchi, J; Singer, Y, Efficient online and batch learning using forward backward splitting, J. Mach. Learn. Res., 10, 2899-2934, (2009) · Zbl 1235.62151
[20] Eckstein, J.: Splitting methods for monotone operators with applications to parallel optimization. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA (1989) · Zbl 1255.68217
[21] Eckstein, J; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073
[22] Esser, E., Zhang, X., Chan, T.F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015-1046 (2010) · Zbl 1206.90117
[23] Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Fortin, M., Glowinski, R. (eds.) Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems. Chapter IX, pp. 299-340. North-Holland, Amsterdam (1983)
[24] Goldstein, AA, Convex programming in Hilbert spaces, Bull. Am. Math. Soc., 70, 709-710, (1964) · Zbl 0142.17101
[25] Goldstein, T; Osher, S, The split Bregman method for L1-regularized problems, SIAM J. Imaging Sci., 2, 323-343, (2009) · Zbl 1177.65088
[26] Güler, O, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29, 403-419, (1991) · Zbl 0737.90047
[27] He, B; Yuan, X, Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective, SIAM J. Imaging Sci., 5, 119-149, (2012) · Zbl 1250.90066
[28] Levitin, ES; Polyak, BT, Constrained minimization methods USSR, Comput. Math. Math. Phys., 6, 1-50, (1966)
[29] Lions, PL; Mercier, B, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979, (1979) · Zbl 0426.65050
[30] Martine, B.: Brève communication régularisation d’inéquations variationnelles par approximations successives. ESAIM: Mathematical Modelling and Numerical Analysis—Modélisation Mathématique et Analyse Numérique, 4(R3):154-158, (1970) · Zbl 1079.90096
[31] Minty, GJ, Monotone (nonlinear) operators in Hilbert space, Duke Math. J., 29, 341-346, (1962) · Zbl 0111.31202
[32] Moreau, JJ, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93, 273-299, (1965) · Zbl 0136.12101
[33] Moudafi, A; Oliny, M, Convergence of a splitting inertial proximal method for monotone operators, J. Comput. Appl. Math., 155, 447-454, (2003) · Zbl 1027.65077
[34] Nesterov, Yu, A method for solving the convex programming problem with convergence rate \(O(1/k^{2})\), Dokl. Akad. Nauk SSSR, 269, 543-547, (1983)
[35] Nesterov, Y.: Introductory lectures on convex optimization: a basic course. In: Applied Optimization, vol. 87. Kluwer Academic Publishers, Boston, MA (2004) · Zbl 1086.90045
[36] Nesterov, Yu, Smooth minimization of non-smooth functions, Math. Program., 103, 127-152, (2005) · Zbl 1079.90102
[37] Nesterov, Yu.: Gradient methods for minimizing composite functions. Math. Program. 140(1), 125-161 (2013) · Zbl 1287.90067
[38] Opial, Z, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Am. Math. Soc., 73, 591-597, (1967) · Zbl 0179.19902
[39] Passty, GB, Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Anal. Appl., 72, 383-390, (1979) · Zbl 0428.47039
[40] Peaceman, DW; Rachford, HH, The numerical solution of parabolic and elliptic differential equations, J. Soc. Ind. Appl. Math., 3, 28-41, (1955) · Zbl 0067.35801
[41] Pesquet, J-C; Pustelnik, N, A parallel inertial proximal optimization methods, Pac. J. Optim., 8, 273-305, (2012) · Zbl 1259.47080
[42] Pock, T., Chambolle, A.: Diagonal preconditioning for first order primal-dual algorithms. In: Proceedings of the International Conference of Computer Vision (ICCV 2011), pp. 1762-1769 (2011)
[43] Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the Mumford-Shah functional. In: Proceedings of the ICCV. Lecture Notes in Computer Science. Springer, Berlin (2009) · Zbl 1255.68217
[44] Polyak, B.T.: Some methods of speeding up the convergence of iteration methods. U.S.S.R. Comput. Math. Math. Phys. 4(5), 1-17 (1964) · Zbl 0876.49009
[45] Raguet, H; Fadili, J; Peyré, G, A generalized forward-backward splitting, SIAM J. Imaging Sci., 6, 1199-1226, (2013) · Zbl 1296.47109
[46] Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898, (1976) · Zbl 0358.90053
[47] Tseng, P, Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J. Control Optim., 29, 119-138, (1991) · Zbl 0737.90048
[48] Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. Technical report (2008)
[49] Vũ, B, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math., 38, 667-681, (2013) · Zbl 1284.47045
[50] Villa, S; Salzo, S; Baldassarre, L; Verri, A, Accelerated and inexact forward-backward algorithms, SIAM J. Optim., 23, 1607-1633, (2013) · Zbl 1295.90049
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.