The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces

DOI10.1137/15M1016989zbMATH Open1341.47064arXiv1504.03721OpenAlexW2592535213MaRDI QIDQ2804207FDOQ2804207

Walaa M. Moursi, Heinz H. Bauschke

Publication date: 28 April 2016

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: The Douglas--Rachford algorithm is a classical and very successful splitting method for finding the zeros of the sums of monotone operators. When the underlying operators are normal cone operators, the algorithm solves a convex feasibility problem. In this paper, we provide a detailed study of the Douglas--Rachford iterates and the corresponding {shadow sequence} when the sets are affine subspaces that do not necessarily intersect. We prove strong convergence of the shadows to the nearest generalized solution. Our results extend recent work from the consistent to the inconsistent case. Various examples are provided to illustrates the results.

Full work available at URL: https://arxiv.org/abs/1504.03721

Recommendations

• The Douglas-Rachford algorithm in the affine-convex case
• On the local convergence of the Douglas-Rachford algorithm
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• A convergent relaxation of the Douglas-Rachford algorithm
• The Douglas-Rachford algorithm for a hyperplane and a doubleton

zbMATH Keywords

fixed pointgeneralized solutionmaximally monotone operatoraffine subspace[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Attouch-Th%EF%BF%BD%EF%BF%BDra+duality&go=Go Attouch-Th��ra duality]Douglas-Rachford splitting operatornormal cone operatorprojection operatorfirmly nonexpansive mappinglinear convergencenormal problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Monotone operators and generalizations (47H05) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Decomposition methods (49M27) Numerical methods involving duality (49M29) Duality theory (optimization) (49N15) Perturbations of nonlinear operators (47H14)

Cites Work

• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Variational Analysis
• Convex analysis and monotone operator theory in Hilbert spaces
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Convex Analysis
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Set-valued mappings and enlargement of monotone operators.
• From Hahn--Banach to monotonicity
• Asymptotic behavior of contractions in Hilbert space
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Title not available (Why is that?)
• Accelerating the convergence of the method of alternating projections
• Attouch-Théra duality revisited: Paramonotonicity and operator splitting
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• Nonconvex Notions of Regularity and Convergence of Fundamental Algorithms for Feasibility Problems
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Optik mit GeoGebra
• On Weak Convergence of the Douglas–Rachford Method
• Minimax monotonicity
• Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
• Title not available (Why is that?)
• Generalized Solutions for the Sum of Two Maximally Monotone Operators
• Title not available (Why is that?)
• On the Range of the Douglas–Rachford Operator

Cited In (24)

• On the minimal displacement vector of compositions and convex combinations of nonexpansive mappings
• Douglas-Rachford splitting and ADMM for pathological convex optimization
• 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
• Infeasibility detection in the alternating direction method of multipliers for convex optimization
• On the asymptotic behavior of the Douglas-Rachford and proximal-point algorithms for convex optimization
• The forward-backward algorithm and the normal problem
• Convergence Analysis of the Relaxed Douglas--Rachford Algorithm
• The magnitude of the minimal displacement vector for compositions and convex combinations of firmly nonexpansive mappings
• On sums and convex combinations of projectors onto convex sets
• On the Douglas-Rachford algorithm
• Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator
• General splitting methods with linearization for the split feasibility problem
• The block-wise circumcentered-reflection method
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Affine nonexpansive operators, Attouch-Théra duality and the Douglas-Rachford algorithm
• On the linear convergence of the circumcentered-reflection method
• On the circumcentered-reflection method for the convex feasibility problem
• A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
• On the minimal displacement vector of the Douglas-Rachford operator
• On the Behavior of the Douglas--Rachford Algorithm for Minimizing a Convex Function Subject to a Linear Constraint
• Convergence Analysis of Douglas--Rachford Splitting Method for “Strongly + Weakly” Convex Programming

Uses Software

• GeoGebra

This page was built for publication: The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804207)