×

zbMATH — the first resource for mathematics

On the Douglas-Rachford algorithm. (English) Zbl 06751028
Summary: The Douglas-Rachford algorithm is a very popular splitting technique for finding a zero of the sum of two maximally monotone operators. The behaviour of the algorithm remains mysterious in the general inconsistent case, i.e., when the sum problem has no zeros. However, more than a decade ago, it was shown that in the (possibly inconsistent) convex feasibility setting, the shadow sequence remains bounded and its weak cluster points solve a best approximation problem. In this paper, we advance the understanding of the inconsistent case significantly by providing a complete proof of the full weak convergence in the convex feasibility setting. In fact, a more general sufficient condition for the weak convergence in the general case is presented. Our proof relies on a new convergence principle for Fejér monotone sequences. Numerous examples illustrate our results.

MSC:
47H05 Monotone operators and generalizations
47H09 Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc.
49M27 Decomposition methods
49M29 Numerical methods involving duality
49N15 Duality theory (optimization)
90C25 Convex programming
Software:
GeoGebra
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Recent results on Douglas-Rachford methods for combinatorial optimization problems. J. Global Optim. 163, 1-30 (2014) · Zbl 1305.90341
[2] Aragón Artacho, F.J., Borwein, J.M.: Global convergence of a non-convex Douglas-Rachford iteration. J. Global Optim. 57, 753-769 (2013) · Zbl 1286.90114
[3] Attouch, H; Théra, M, A general duality principle for the sum of two operators, J. Convex Anal., 3, 1-24, (1996) · Zbl 0861.47028
[4] Baillon, JB; Bruck, RE; Reich, S, On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces, Houst. J. Math., 4, 1-9, (1978) · Zbl 0431.47034
[5] Bauschke, H.H.: Projection algorithms and monotone operators. PhD thesis, Simon Fraser University, Burnaby, B.C., Canada (August 1996)
[6] Bauschke, HH, A note on the paper by eckstein and svaiter on ‘general projective splitting for sums of maximal monotone operators’, SIAM J. Control Optim., 48, 2513-2515, (2009) · Zbl 1197.47065
[7] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011) · Zbl 1218.47001
[8] Bauschke, HH; Moursi, WM, The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces, SIAM J. Optim., 26, 968-985, (2016) · Zbl 1341.47064
[9] Bauschke, H.H., Lukens, B., Moursi, W.M.: Affine nonexpansive operators, Attouch-Théra duality and the Douglas-Rachford algorithm. arXiv:1603.09418 [math.OC] · Zbl 06804490
[10] Bauschke, HH; Combettes, PL; Luke, DR, Phase retrieval, error reduction algorithm, and fienup variants: a view from convex optimization, J. Opt. Soc. Am., 19, 1334-1345, (2002)
[11] Bauschke, HH; Combettes, PL; Luke, DR, Finding best approximation pairs relative to two closed convex sets in Hilbert spaces, J. Approx. Theory, 127, 178-192, (2004) · Zbl 1050.46021
[12] Bauschke, HH; Wang, X; Yao, L, Examples of discontinuous maximal monotone linear operators and the solution to a recent problem posed by B.F. svaiter, J. Math. Anal. Appl., 370, 224-241, (2010) · Zbl 1197.47009
[13] Bauschke, HH; Moffat, SM; Wang, X, Firmly nonexpansive mappings and maximally monotone operators: correspondence and duality, Set-Valued Var. Anal., 20, 131-153, (2012) · Zbl 1263.47066
[14] Bauschke, HH; Boţ, RI; Hare, WL; Moursi, WM, Attouch-théra duality revisited: paramonotonicity and operator splitting, J. Approx. Theory, 164, 1065-1084, (2012) · Zbl 1254.47031
[15] Bauschke, H.H., Bello Cruz, J.Y., Nghia, T.T.A., Phan, H.M., Wang, X.: The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle. J. Approx. Theory 185, 63-79 (2014) · Zbl 1307.49030
[16] Bauschke, HH; Hare, WL; Moursi, WM, Generalized solutions for the sum of two maximally monotone operators, SIAM J. Control Optim., 52, 1034-1047, (2014) · Zbl 1297.47055
[17] Bauschke, HH; Dao, MN; Moursi, WM, On Fejér monotone sequences and nonexpansive mappings, Linear Nonlinear Anal., 1, 287-295, (2015) · Zbl 1338.47060
[18] Bauschke, HH; Hare, WL; Moursi, WM, On the range of the Douglas-Rachford operator, Math. Oper. Res., 41, 884-897, (2016) · Zbl 1350.47035
[19] Borwein, JM, Fifty years of maximal monotonicity, Optim. Lett., 4, 473-490, (2010) · Zbl 1214.47043
[20] Borwein, J.M., Sims, B.: The Douglas-Rachford Algorithm in the Absence of Convexity, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Optimization and Applications 49. Springer, New York (2011)
[21] Borwein, JM; Tam, MK, The cyclic Douglas-Rachford method for inconsistent feasibility problems, J. Nonlinear Convex Anal., 16, 537-584, (2015) · Zbl 1315.47061
[22] Brezis, H.: Operateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert, North-Holland/Elsevier (1973) · Zbl 0252.47055
[23] Brezis, H; Haraux, A, Image d’une somme d’opérateurs monotones et applications, Isr. J. Math., 23, 165-186, (1976) · Zbl 0323.47041
[24] Bruck, RE; Reich, S, Nonexpansive projections and resolvents of accretive operators in Banach spaces, Houst. J. Math., 3, 459-470, (1977) · Zbl 0383.47035
[25] Burachik, R.S., Iusem, A.N.: Set-Valued Mappings and Enlargements of Monotone Operators. Springer, Berlin (2008) · Zbl 1154.49001
[26] Combettes, PL, Inconsistent signal feasibility problems: least-squares solutions in a product space, IEEE Trans. Signal Process., 42, 2955-2966, (1994)
[27] Combettes, PL, The convex feasibility problem in image recovery, Adv. Imaging Electron Phys., 25, 155-270, (1995)
[28] Combettes, PL, Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization, 53, 475-504, (2004) · Zbl 1153.47305
[29] Combettes, PL, Iterative construction of the resolvent of a sum of maximal monotone operators, J. Convex Anal., 16, 727-748, (2009) · Zbl 1193.47067
[30] Combettes, PL; Pesquet, J-C, A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery, IEEE J. Sel. Top. Signal Process., 1, 564-574, (2007)
[31] Combettes, P.L., Pesquet, J.-C.: A proximal decomposition method for solving convex variational inverse problems. Inverse Probl. 24, 065014 (2008) · Zbl 1154.49025
[32] Combettes, PL; Pesquet, J-C, Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping, SIAM J. Optim., 25, 1221-1248, (2015) · Zbl 1317.65135
[33] Douglas, J; Rachford, HH, On the numerical solution of the heat conduction problem in 2 and 3 space variables, Trans. AMS, 82, 421-439, (1956) · Zbl 0070.35401
[34] Drusvyatskiy, D; Li, C-K; Pelejo, DC; Voronin, Y-L; Wolkowicz, H, Projection methods for quantum channel construction, Quantum Inf. Process., 14, 3075-3095, (2015) · Zbl 1327.81083
[35] Eckstein, J.: Splitting methods for monotone operators with applications to parallel optimization. Ph.D. thesis, MIT (1989)
[36] Eckstein, J; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program. Ser. A., 55, 293-318, (1992) · Zbl 0765.90073
[37] Eckstein, J; Svaiter, BF, A family of projective splitting methods for the sum of two maximal monotone operators, Math. Program. Ser. B, 111, 173-199, (2008) · Zbl 1134.47048
[38] Elser, V; Rankenburg, I, Deconstructing the energy landscape: constraint-based algorithm for folding heteropolymers, Phys. Rev. E, 73, 026702, (2006)
[39] Elser, V; Rankenburg, I; Thibault, P, Searching with iterated maps, Proc. Natl. Acad. Sci. USA, 102, 418-423, (2007) · Zbl 1160.90495
[40] GeoGebra. http://www.geogebra.org · Zbl 1341.47064
[41] Hesse, R; Luke, DR, Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems, SIAM J. Optim., 23, 2397-2419, (2013) · Zbl 1288.65094
[42] Hesse, R; Luke, DR; Neumann, P, Alternating projections and Douglas-Rachford for sparse affine feasibility, IEEE Trans. Signal Process., 62, 4868, (2014) · Zbl 1394.94227
[43] Iusem, AN, On some properties of paramonotone operators, J. Convex Anal., 5, 269-278, (1998) · Zbl 0914.90216
[44] Lieutaud, J.: Approximations d’opérateurs monotones par des méthodes de splitting, doctoral thesis, University of Paris (1969) · Zbl 0914.90216
[45] Li, G; Pong, TK, Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems, Math. Prog. Ser. A, 159, 371-401, (2016) · Zbl 1346.90584
[46] Lions, PL; Mercier, B, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979, (1979) · Zbl 0426.65050
[47] Mercier, B.: Inéquations Variationnelles de la Mécanique (Publications Mathématiques d’Orsay, no. 80.01), Orsay, France: Université de Paris-XI (1980). http://portail.mathdoc.fr/PMO/PDF/M_MERCIER-87 · Zbl 1341.47064
[48] Minty, GJ, Monotone (nonlinear) operators in Hilbert spaces, Duke Math. J., 29, 341-346, (1962) · Zbl 0111.31202
[49] Pazy, A, Asymptotic behavior of contractions in Hilbert space, Isr. J. Math., 9, 235-240, (1971) · Zbl 0225.54032
[50] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin (2009). (Corrected 3rd printing) · Zbl 0888.49001
[51] Simons, S.: Minimax and Monotonicity. Springer, Berlin (1998) · Zbl 0922.47047
[52] Simons, S.: From Hahn-Banach to Monotonicity. Springer, Berlin (2008) · Zbl 1131.47050
[53] Svaiter, BF, On weak convergence of the Douglas-Rachford method, SIAM J. Control Optim., 49, 280-287, (2011) · Zbl 1220.47064
[54] Zarantonello, EH; Zarantonello, EH (ed.), Projections on convex sets in Hilbert space and spectral theory, 237-424, (1971), New York
[55] Zeidler, E.: Nonlinear Functional Analysis and Its Applications II/A: Linear Monotone Operators. Springer, Berlin (1990) · Zbl 0684.47028
[56] Zeidler, E.: Nonlinear Functional Analysis and Its Applications II/B: Nonlinear Monotone Operators. Springer, Berlin (1990) · Zbl 0684.47029
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.