The Splitting Algorithms by Ryu, by Malitsky–Tam, and by Campoy Applied to Normal Cones of Linear Subspaces Converge Strongly to the Projection onto the Intersection
From MaRDI portal
Publication:6158002
best approximationCampoy splittingHilbert spaceintersection of subspaceslinear convergenceMalitsky-Tam splittingmaximally monotone operatornonexpansive mappingresolventRyu splitting
Applications of generalized inverses (15A10) Best approximation, Chebyshev systems (41A50) Monotone operators and generalizations (47H05) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Decomposition methods (49M27) Numerical methods based on nonlinear programming (49M37) Numerical mathematical programming methods (65K05) Convex programming (90C25)
Abstract: Finding a zero of a sum of maximally monotone operators is a fundamental problem in modern optimization and nonsmooth analysis. Assuming that the resolvents of the operators are available, this problem can be tackled with the Douglas-Rachford algorithm. However, when dealing with three or more operators, one must work in a product space with as many factors as there are operators. In groundbreaking recent work by Ryu and by Malitsky and Tam, it was shown that the number of factors can be reduced by one. A similar reduction was achieved recently by Campoy through a clever reformulation originally proposed by Kruger. All three splitting methods guarantee weak convergence to some solution of the underlying sum problem; strong convergence holds in the presence of uniform monotonicity. In this paper, we provide a case study when the operators involved are normal cone operators of subspaces and the solution set is thus the intersection of the subspaces. Even though these operators lack strict convexity, we show that striking conclusions are available in this case: strong (instead of weak) convergence and the solution obtained is (not arbitrary but) the projection onto the intersection. Numerical experiments to illustrate our results are also provided.
Recommendations
- Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting
- Strong convergence of the modified projection and contraction methods for split feasibility problem
- The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
- Strong convergence of a splitting projection method for the sum of maximal monotone operators
- Convergence of splitting algorithms for the sum of two accretive operators with applications
Cites work
- A product space reformulation with reduced dimension for splitting algorithms
- Accelerating the convergence of the method of alternating projections
- Affine nonexpansive operators, Attouch-Théra duality and the Douglas-Rachford algorithm
- Best approximation in inner product spaces
- Convex analysis and monotone operator theory in Hilbert spaces
- Error bounds for the method of alternating projections
- Generalized differentials of nonsmooth functions, and necessary conditions for an extremum
- scientific article; zbMATH DE number 3535187 (Why is no real title available?)
- scientific article; zbMATH DE number 3558452 (Why is no real title available?)
- scientific article; zbMATH DE number 3595777 (Why is no real title available?)
- scientific article; zbMATH DE number 3615396 (Why is no real title available?)
- scientific article; zbMATH DE number 1460605 (Why is no real title available?)
- Iterative construction of the resolvent of a sum of maximal monotone operators
- Julia: a fresh approach to numerical computing
- On matrices having equal spectral radius and spectral norm
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces
- Series and parallel addition of matrices
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Strengthened splitting methods for computing resolvents
- The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces
- The rate of convergence in the method of alternating projections
- The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
- Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting
Cited in
(6)- Regularity of sets under a reformulation in a product space with reduced dimension
- Distributed forward-backward methods for ring networks
- On a result by Baillon, Bruck, and Reich
- On the Bredies-Chenchene-Lorenz-Naldi algorithm: linear relations and strong convergence
- Discrete convex subdifferentials and optimality
- Linear convergence of resolvent splitting with minimal lifting and its application to a primal–dual algorithm
This page was built for publication: The Splitting Algorithms by Ryu, by Malitsky–Tam, and by Campoy Applied to Normal Cones of Linear Subspaces Converge Strongly to the Projection onto the Intersection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6158002)
