×

Convergence analysis of the relaxed Douglas-Rachford algorithm. (English) Zbl 07173421

Summary: Motivated by nonconvex, inconsistent feasibility problems in imaging, the relaxed alternating averaged reflections algorithm, or relaxed Douglas-Rachford algorithm (DR\(\lambda\)), was first proposed over a decade ago. Convergence results for this algorithm are limited to either convex feasibility or consistent nonconvex feasibility with strong assumptions on the regularity of the underlying sets. Using an analytical framework depending only on metric subregularity and pointwise almost averagedness, we analyze the convergence behavior of DR \(\lambda\) for feasibility problems that are both nonconvex and inconsistent. We introduce a new type of regularity of sets, called superregular at a distance, to establish sufficient conditions for local linear convergence of the corresponding sequence. These results subsume and extend existing results for this algorithm.

MSC:

65K10 Numerical optimization and variational techniques
49K40 Sensitivity, stability, well-posedness
49M05 Numerical methods based on necessary conditions
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
49M20 Numerical methods of relaxation type
49J53 Set-valued and variational analysis
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J.-B. Baillon, P. L. Combettes, and R. Cominetti, There is no variational characterization of the cycles in the method of periodic projections, J. Funct. Anal., 262 (2012), pp. 400-408. · Zbl 1241.46015
[2] A. Bakan, F. Deutsch, and W. Li, Strong CHIP, normality, and linear regularity of convex sets, Trans. Amer. Math. Soc., 357 (2005), pp. 3831-3863. · Zbl 1094.90030
[3] H. Bauschke and D. Noll, On the local convergence of the Douglas-Rachford algorithm, Arch. Math. (Basel), 102 (2014), pp. 589-600. · Zbl 1344.47044
[4] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., Springer, Cham, Switzerland, 2017. · Zbl 1359.26003
[5] H. H. Bauschke, P. L. Combettes, and D. R. Luke, Finding best approximation pairs relative to two closed convex sets in Hilbert spaces, J. Approx. Theory, 127 (2004), pp. 178-192. · Zbl 1050.46021
[6] H. H. Bauschke and W. M. Moursi, The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces, SIAM J. Optim., 26 (2016), pp. 968-985. · Zbl 1341.47064
[7] F. E. Browder, Existence and approximation of solutions of nonlinear variational inequalities, Proc. Natl. Acad. Sci., 56 (1966), pp. 1080-1086, https://doi.org/10.1073/pnas.56.4.1080. · Zbl 0148.13502
[8] A. Daniilidis, D. R. Luke, and M. K. Tam, Characterizations of super-regularity and its variants, in Splitting Algorithms, Modern Operator Theory, and Applications, Springer, 2019, Heinz H. Bauschke, Regina S. Burachil, and D. Russell Luke, eds., Springer, Cham, Switzerland, 2019, https://doi.org/10.1007/978-3-030-25939-6.
[9] M. N. Dao and H. M. Phan, Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems, J. Global Optim., 72 (2018), pp. 443-474. · Zbl 1499.90170
[10] F. Deutsch, Best Approximation in Inner Product Spaces, CMS Books Math./Ouvrages Math. SMC, Springer, New York, 2001. · Zbl 0980.41025
[11] A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings, 2nd ed., Springer-Verlag, Dordrecht, 2014. · Zbl 1337.26003
[12] J. Douglas, Jr., and H. H. Rachford, Jr., On the numerical solution of heat conduction problems in two or three space variables, Trans. Amer. Math. Soc., 82 (1956), pp. 421-439. · Zbl 0070.35401
[13] J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), pp. 293-318. · Zbl 0765.90073
[14] R. Hesse and D. R. Luke, Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems, SIAM J. Optim., 23 (2013), pp. 2397-2419. · Zbl 1288.65094
[15] A. Y. Kruger, D. R. Luke, and N. H. Thao, Set regularities and feasibility problems, Math. Program., 168 (2018), pp. 279-311, https://doi.org/10.1007/s10107-016-1039-x. · Zbl 1390.49012
[16] A. S. Lewis, D. R. Luke, and J. Malick, Local linear convergence of alternating and averaged projections, Found. Comput. Math., 9 (2009), pp. 485-513. · Zbl 1169.49030
[17] G. Li and T. K. Pong, Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems, Math. Program., 159 (2016), pp. 371-401. · Zbl 1346.90584
[18] P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), pp. 964-979. · Zbl 0426.65050
[19] D. R. Luke, Relaxed averaged alternating reflections for diffraction imaging, Inverse Problems, 21 (2005), pp. 37-50. · Zbl 1146.78008
[20] D. R. Luke, Finding best approximation pairs relative to a convex and a prox-regular set in Hilbert space, SIAM J. Optim., 19 (2008), pp. 714-739. · Zbl 1169.65056
[21] D. R. Luke, S. Sabach, and M. Teboulle, Optimization on spheres: Models and proximal algorithms with computational performance comparisons, SIAM J. Math. Data Sci., 1(3) (2019), pp. 408-445. · Zbl 1499.90175
[22] D. R. Luke, M. Teboulle, and N. H. Thao, Necessary conditions for linear convergence of iterated expansive, set-valued mappings, Math. Program., (2018), pp. 1-31, https://doi.org/10.1007/s10107-018-1343-8. · Zbl 1439.49032
[23] D. R. Luke, N. H. Thao, and M. K. Tam, Quantitative convergence analysis of iterated expansive, set-valued mappings, Math. Oper. Res., 43 (2018), pp. 1143-1176, https://doi.org/10.1287/moor.2017.0898. · Zbl 1434.49012
[24] Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc. (N.S.), 73 (1967), pp. 591-597. · Zbl 0179.19902
[25] H. Phan, Linear convergence of the Douglas-Rachford method for two closed sets, Optimization, 65 (2016), pp. 369-385. · Zbl 1334.49089
[26] J. von Neumann, Functional Operators, Vol II. The Geometry of Orthogonal Spaces, Ann. of Math Stud. 22, Princeton University Press, Princeton, NJ, 1950; reprint of mimeographed lecture notes first distributed in 1933. · Zbl 0039.11701
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.