×

zbMATH — the first resource for mathematics

On the convergence of the iterates of the “fast iterative shrinkage/thresholding algorithm”. (English) Zbl 1371.65047
Summary: We discuss here the convergence of the iterates of the “Fast Iterative Shrinkage/Thresholding Algorithm”, which is an algorithm proposed by A. Beck and M. Teboulle [SIAM J. Imaging Sci. 2, No. 1, 183–202 (2009; Zbl 1175.94009)] for minimizing the sum of two convex, lower-semicontinuous, and proper functions (defined in a Euclidean or Hilbert space), such that one is differentiable with Lipschitz gradient, and the proximity operator of the second is easy to compute. It builds a sequence of iterates for which the objective is controlled, up to a (nearly optimal) constant, by the inverse of the square of the iteration number. However, the convergence of the iterates themselves is not known. We show here that with a small modification, we can ensure the same upper bound for the decay of the energy, as well as the convergence of the iterates to a minimizer.

MSC:
65J15 Numerical solutions to equations with nonlinear operators
65Y20 Complexity and performance of numerical algorithms
90C25 Convex programming
Software:
UNLocBoX
PDF BibTeX Cite
Full Text: DOI
References:
[1] Combettes, PL; Wajs, VR, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 1168-1200, (2005) · Zbl 1179.94031
[2] Lions, P-L; Mercier, B, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979, (1979) · Zbl 0426.65050
[3] 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
[4] Gabay, D; Mercier, B, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 17-40, (1976) · Zbl 0352.65034
[5] Combettes, P.L., Pesquet, J.-C.: Proximal splitting methods in signal processing. In: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Volume 49 of Springer Optim. Appl, pp. 185-212. Springer, New York (2011) · Zbl 1242.90160
[6] 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
[7] Nesterov, Y, A method for solving the convex programming problem with convergence rate \(O(1/k^{2})\), Dokl. Akad. Nauk SSSR, 269, 543-547, (1983)
[8] Güler, O, New proximal point algorithms for convex minimization, SIAM J. Optim., 2, 649-664, (1992) · Zbl 0778.90052
[9] Nesterov, Y, Smooth minimization of non-smooth functions, Math. Program., 103, 127-152, (2005) · Zbl 1079.90102
[10] Nemirovski, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. A Wiley-Interscience Publication. Wiley, New York (1983). Translated from the Russian and with a preface by E. R. Dawson, Wiley-Interscience Series in Discrete Mathematics · Zbl 0352.65034
[11] Lorenz, D.A., Pock, T.: An inertial forward-backward algorithm for monotone inclusions. J. Math. Imaging Vis. 1-15 (2014). (online) · Zbl 1327.47063
[12] 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
[13] 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
[14] Nesterov, Y.: Introductory Lectures on Convex Optimization, Volume 87 of Applied Optimization. Kluwer, Boston (2004). A basic course · Zbl 1086.90045
[15] Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. SIAM J. Optim (submitted) (2008) · Zbl 1179.94031
[16] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York (2011). With a foreword by Hédy Attouch · Zbl 1218.47001
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.