×

zbMATH — the first resource for mathematics

A three-operator splitting scheme and its optimization applications. (English) Zbl 06834688
It is well known that many optimization problems and inclusion problems could be reformulated as fixed point iteration schemes. These, in turn, may be solved by several of the standard solution techniques. In the work under review, the authors propose a fixed-point iterative scheme for solving a class of monotone inclusion problems, defined in terms of three possibly nonlinear operators on a given Hilbert space. It is shown that standard iterative schemes employed in these situations also converge, as in the linear case. Two new accelerated methods are also proposed, which apply when at least one of the operators is strongly monotone. It is demonstrated how some of the theoretical results could be developed into algorithmic procedures.

MSC:
47J26 Fixed-point iterations
47J22 Variational and other types of inclusions
47H05 Monotone operators and generalizations
65K05 Numerical mathematical programming methods
65K15 Numerical methods for variational inequalities and related problems
90C25 Convex programming
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Attouch, H., Peypouquet, J., Redont, P.: Backward-forward algorithms for structured monotone inclusions in Hilbert spaces. J. Math. Anal. Appl. (2016) · Zbl 1375.65081
[2] Bauschke, HH; Bello Cruz, JY; Nghia, TTA; Phan, HM; Wang, X, The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle, Journal of Approximation Theory, 185, 63-79, (2014) · Zbl 1307.49030
[3] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 1st edn. Springer Publishing Company Incorporated, Berlin (2011) · Zbl 1218.47001
[4] Boṫ, RI; Csetnek, ER; Heinrich, A; Hendrich, C, On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems, Math. Program., 150, 251-279, (2015) · Zbl 1312.47081
[5] Boṫ, RI; Hendrich, C, A Douglas-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators, SIAM J. Optim., 23, 2541-2565, (2013) · Zbl 1295.47066
[6] Candes, E; Plan, Y, Matrix completion with noise, Proc. IEEE, 98, 925-936, (2010)
[7] Cesàro, E, Sur la convergence des séries, Nouvelles annales de mathé,matiques, 3, 49-59, (1888) · JFM 20.0242.01
[8] 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
[9] Combettes, PL, Systems of structured monotone inclusions: duality, algorithms, and applications, SIAM J. Optim., 23, 2420-2447, (2013) · Zbl 1314.47105
[10] Combettes, P.L., Condat, L., Pesquet, J.C., Vũ, B.C.: A Forward-Backward View of Some Primal-Dual Optimization Methods in Image Recovery. In: IEEE International Conference on Image Processing. Paris, France (2014) · Zbl 1314.47105
[11] Combettes, PL; Pesquet, JC, Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued and Variational Analysis, 20, 307-330, (2012) · Zbl 1284.47043
[12] Combettes, PL; Yamada, I, Compositions and convex combinations of averaged nonexpansive operators, J. Math. Anal. Appl., 425, 55-70, (2015) · Zbl 1322.47051
[13] 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
[14] Davis, D.: Convergence rate analysis of the forward-Douglas-Rachford splitting scheme. SIAM J. Optim. 25(3), 1760-1786 (2014). arXiv:1410.2654v3 · Zbl 1325.65081
[15] Davis, D, Convergence rate analysis of primal-dual splitting schemes, SIAM J. Optim., 25, 1912-1943, (2015) · Zbl 1323.47069
[16] Davis, D, Convergence rate analysis of the forward-Douglas-Rachford splitting scheme, SIAM J. Optim., 25, 1760-1786, (2015) · Zbl 1325.65081
[17] Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. arXiv:1406.4834v2 (2014) · Zbl 1372.65168
[18] Davis, D., Yin, W.: A Three-Operator Splitting Scheme and Its Optimization Applications. Tech. Rep CAM 15-13. University of California, Los Angeles (2015)
[19] Davis, D., Yin, W.: Convergence Rate Analysis of Several Splitting Schemes. In: Glowinski, R., Osher, S., Yin, W. (eds.) Splitting Methods in Communication and Imaging, Science and Engineering, p. Chapter 4, pp. 115-163. Springer, Berlin (2016) · Zbl 1372.65168
[20] Gabay, D; Mercier, B, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers & Mathematics with Applications, 2, 17-40, (1976) · Zbl 0352.65034
[21] Glowinski, R; Marroco, A, On the approximation by finite elements of order one, and resolution, penalisation-duality for a class of nonlinear Dirichlet problems, ESAIM: Mathematical Modelling and Numerical Analysis - Mathematical Modelling and Numerical Analysis, 9, 41-76, (1975) · Zbl 0368.65053
[22] Krasnosel’skii, MA, Two remarks on the method of successive approximations, Uspekhi Matematicheskikh Nauk, 10, 123-127, (1955)
[23] Lions, PL; Mercier, B, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979, (1979) · Zbl 0426.65050
[24] Liu, J; Musialski, P; Wonka, P; Ye, J, Tensor completion for estimating missing values in visual data, IEEE Trans. Pattern Anal. Mach. Intell., 35, 208-220, (2013)
[25] Mann, WR, Mean value methods in iteration, Proc. Am. Math. Soc., 4, 506-510, (1953) · Zbl 0050.11603
[26] 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
[27] Peng, Z; Wu, T; Xu, Y; Yan, M; Yin, W, Coordinate friendly structures, algorithms and applications, Ann. Mater. Sci. Appl., 1, 57-119, (2016) · Zbl 1432.65076
[28] Stolz, O.: Vorlesungen ü Ber Allgemeine Arithmetik: Nach Den Neueren Ansichten. Leipzig, Teubners (1885) · JFM 17.0116.01
[29] Svaiter, BF, On weak convergence of the Douglas-Rachford method, SIAM J. Control. Optim., 49, 280-287, (2011) · Zbl 1220.47064
[30] 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
[31] Tseng, P, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control. Optim., 38, 431-446, (2000) · Zbl 0997.90062
[32] Vũ, BC, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math., 38, 667-681, (2013) · Zbl 1284.47045
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.