×

Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems. (English) Zbl 1468.90083

The authors solve a maximal monotone inclusion problem by the proximal point algorithm. The problem is to find \(w^*\) such that \(0 \in T(w^*)\), where \(T: \mathbb R^n \rightarrow \mathbb R^n\) is a maximum monotone operator. It can be shown that \( 0 \in T(w^*)\) i.e. \( w^* \in T^{-1}(0)\) if and only if \(w^*\) is the fixed point of the resolvent operator \((I + \lambda T)^{-1}\), where \(\lambda > 0\). The authors consider the following iteration scheme: \[ w^{k+1} = (I + \lambda T)^{-1}(w^k),~ k = 0,1,2, \dots, \] where \(w^0\) is any element of \(\mathbb R^n\). The sequence \(\{ w^k \}\) converges to the fixed point of the operator \((I + \lambda T)^{-1}\). The main result of the paper is etablishing the worst case sublinear convergence rate of the sequence and the proof that the the established convegence rate is tight.

MSC:

90C25 Convex programming
65K05 Numerical mathematical programming methods
65J22 Numerical solution to inverse problems in abstract spaces
90C22 Semidefinite programming
90C60 Abstract computational complexity for mathematical programming problems

Software:

PESTO; SeDuMi
Full Text: DOI

References:

[1] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., with a foreword by Hédy Attouch, CMS Books Math./Ouvrages Math. SMC, Springer, Cham, 2017, https://doi.org/10.1007/978-3-319-48311-5. · Zbl 1359.26003
[2] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183-202, https://doi.org/10.1137/080716542. · Zbl 1175.94009
[3] H. Brézis and P.-L. Lions, Produits infinis de résolvantes, Israel J. Math., 29 (1978), pp. 329-345, https://doi.org/10.1007/BF02761171. · Zbl 0387.47038
[4] D. Davis and W. Yin, Convergence rate analysis of several splitting schemes, in Splitting Methods in Communication, Imaging, Science, and Engineering, Sci. Comput., Springer, Cham, 2016, pp. 115-163. · Zbl 1372.65168
[5] D. Davis and W. Yin, Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions, Math. Oper. Res., 42 (2017), pp. 783-805, https://doi.org/10.1287/moor.2016.0827. · Zbl 1379.65035
[6] E. de Klerk, F. Glineur, and A. B. Taylor, On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions, Optim. Lett., 11 (2017), pp. 1185-1199, https://doi.org/10.1007/s11590-016-1087-4. · Zbl 1381.90067
[7] J. Douglas, Jr., and H. H. Rachford, Jr., On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., 82 (1956), pp. 421-439. · Zbl 0070.35401
[8] Y. Drori and M. Teboulle, Performance of first-order methods for smooth convex minimization: A novel approach, Math. Program., 145 (2014), pp. 451-482, https://doi.org/10.1007/s10107-013-0653-0. · Zbl 1300.90068
[9] Y. Drori and M. Teboulle, An optimal variant of Kelley’s cutting-plane method, Math. Program., 160 (2016), pp. 321-351, https://doi.org/10.1007/s10107-016-0985-7. · Zbl 1349.90880
[10] J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Programming, 55 (1992), pp. 293-318, https://doi.org/10.1007/BF01581204. · Zbl 0765.90073
[11] O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29 (1991), pp. 403-419, https://doi.org/10.1137/0329022. · Zbl 0737.90047
[12] O. Güler, New proximal point algorithms for convex minimization, SIAM J. Optim., 2 (1992), pp. 649-664, https://doi.org/10.1137/0802032. · Zbl 0778.90052
[13] E. V. Haynsworth, On the Schur Complement, Basel Mathematical Notes, BMN 20, 1968, University of Basel.
[14] B. He and X. Yuan, On the convergence rate of Douglas-Rachford operator splitting method, Math. Program., 153 (2015), pp. 715-722, https://doi.org/10.1007/s10107-014-0805-x. · Zbl 1327.90211
[15] M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl., 4 (1969), pp. 303-320. · Zbl 0174.20705
[16] D. Kim, Accelerated Proximal Point Method for Maximally Monotone Operators, preprint, https://arxiv.org/abs/1905.05149, 2019.
[17] D. Kim and J. A. Fessler, Optimized first-order methods for smooth convex minimization, Math. Program., 159 (2016), pp. 81-107, https://doi.org/10.1007/s10107-015-0949-3. · Zbl 1345.90113
[18] D. Kim and J. A. Fessler, On the convergence analysis of the optimized gradient method, J. Optim. Theory Appl., 172 (2017), pp. 187-205, https://doi.org/10.1007/s10957-016-1018-7. · Zbl 1360.90200
[19] D. Kim and J. A. Fessler, Another look at the fast iterative shrinkage/thresholding algorithm (FISTA), SIAM J. Optim., 28 (2018), pp. 223-250, https://doi.org/10.1137/16M108940X. · Zbl 1391.90476
[20] D. Kim and J. A. Fessler, Generalizing the optimized gradient method for smooth convex minimization, SIAM J. Optim., 28 (2018), pp. 1920-1950, https://doi.org/10.1137/17M112124X. · Zbl 1400.90245
[21] D. Kim and J. A. Fessler, Optimizing the Efficiency of First-order Methods for Decreasing the Gradient of Smooth Convex Functions, preprint, https://arxiv.org/abs/1803.06600, 2018.
[22] D. Leventhal, Metric subregularity and the proximal point method, J. Math. Anal. Appl., 360 (2009), pp. 681-688, https://doi.org/10.1016/j.jmaa.2009.07.012. · Zbl 1175.49028
[23] P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), pp. 964-979, https://doi.org/10.1137/0716071. · Zbl 0426.65050
[24] B. Martinet, Régularisation d’inéquations variationnelles par approximations successives, Rev. Fran\ccaise Informat. Recherche Opérationnelle, 4 (1970), pp. 154-158. · Zbl 0215.21103
[25] B. Martinet, Détermination approchée d’un point fixe d’une application pseudo-contractante. Cas de l’application prox, C. R. Acad. Sci. Paris Sér. A-B, 274 (1972), pp. A163-A165. · Zbl 0226.47032
[26] G. J. Minty, Monotone (nonlinear) operators in Hilbert space, Duke Math. J., 29 (1962), pp. 341-346. · Zbl 0111.31202
[27] J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, C. R. Acad. Sci. Paris, 255 (1962), pp. 2897-2899. · Zbl 0118.10502
[28] J.-J. Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93 (1965), pp. 273-299. · Zbl 0136.12101
[29] Y. E. Nesterov, A method for solving the convex programming problem with convergence rate \(O(1/k^2)\), Dokl. Akad. Nauk SSSR, 269 (1983), pp. 543-547.
[30] M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization (Sympos., Univ. Keele, Keele, 1968), Academic Press, London, 1969, pp. 283-298. · Zbl 0194.47701
[31] R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, No. 28, Princeton University Press, 1970. · Zbl 0193.18401
[32] R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1 (1976), pp. 97-116. · Zbl 0402.90076
[33] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), pp. 877-898, https://doi.org/10.1137/0314056. · Zbl 0358.90053
[34] E. K. Ryu, A. B. Taylor, C. Bergeling, and P. Giselsson, Operator Splitting Performance Estimation: Tight Contraction Factors and Optimal Parameter Selection, https://arxiv.org/abs/1812.00146, 2018.
[35] J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11/12 (1999), pp. 625-653. · Zbl 0973.90526
[36] A. B. Taylor and F. Bach, Stochastic first-order methods: Non-asymptotic and computer-aided analyses via potential functions, Proc. Mach. Learn. Res., 99 (2019), pp. 1-59.
[37] A. B. Taylor, J. M. Hendrickx, and F. Glineur, Exact worst-case performance of first-order methods for composite convex optimization, SIAM J. Optim., 27 (2017), pp. 1283-1313, https://doi.org/10.1137/16M108104X. · Zbl 1371.90108
[38] A. B. Taylor, J. M. Hendrickx, and F. Glineur, Smooth strongly convex interpolation and exact worst-case performance of first-order methods, Math. Program., 161 (2017), pp. 307-345, https://doi.org/10.1007/s10107-016-1009-3. · Zbl 1359.90098
[39] A. B. Taylor, J. M. Hendrickx, and F. Glineur, Exact worst-case convergence rates of the proximal gradient method for composite convex minimization, J. Optim. Theory Appl., 178 (2018), pp. 455-476, https://doi.org/10.1007/s10957-018-1298-1. · Zbl 1394.90464
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.