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

DOI10.1137/15M1016989MaRDI QIDQ2804207zbMATH OpenOpenAlexFDO

Authors Heinz H. Bauschke, Walaa M. Moursi

Publication date 28 April 2016

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

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

zbMATH Keywords

affine subspaceAttouch-Théra dualityDouglas-Rachford splitting operatorfirmly nonexpansive mappingfixed pointgeneralized solutionlinear convergencemaximally monotone operatornormal cone operatornormal problemprojection operator

Mathematics Subject Classification ID

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

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.

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

Cites work

• Accelerating the convergence of the method of alternating projections
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• Asymptotic behavior of contractions in Hilbert space
• Attouch-Théra duality revisited: Paramonotonicity and operator splitting
• Convex Analysis
• Convex analysis and monotone operator theory in Hilbert spaces
• Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Fréchet-Legendre functions and reflexive Banach spaces
• From Hahn--Banach to monotonicity
• Generalized solutions for the sum of two maximally monotone operators
• scientific article; zbMATH DE number 42636 (Why is no real title available?)
• scientific article; zbMATH DE number 45061 (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 1268621 (Why is no real title available?)
• scientific article; zbMATH DE number 464662 (Why is no real title available?)
• scientific article; zbMATH DE number 1009689 (Why is no real title available?)
• scientific article; zbMATH DE number 3398324 (Why is no real title available?)
• scientific article; zbMATH DE number 967071 (Why is no real title available?)
• Minimax monotonicity
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the range of the Douglas-Rachford operator
• On weak convergence of the Douglas-Rachford method
• Optik mit GeoGebra
• Set-valued mappings and enlargement of monotone operators.
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Variational Analysis

Cited in

(32)

• Affine nonexpansive operators, Attouch-Théra duality and the Douglas-Rachford algorithm
• On sums and convex combinations of projectors onto convex sets
• The forward-backward algorithm and the normal problem
• The Douglas-Rachford algorithm in the affine-convex case
• The magnitude of the minimal displacement vector for compositions and convex combinations of firmly nonexpansive mappings
• General splitting methods with linearization for the split feasibility problem
• The strong convergence of Douglas-Rachford methods for the split feasibility problem
• The block-wise circumcentered-reflection method
• On the asymptotic behavior of the Douglas-Rachford and proximal-point algorithms for convex optimization
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator
• Infeasibility detection in the alternating direction method of multipliers for convex optimization
• Douglas-Rachford splitting and ADMM for pathological convex optimization
• A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
• On the Douglas-Rachford algorithm
• On the linear convergence of the circumcentered-reflection method
• The Douglas-Rachford algorithm for a hyperplane and a doubleton
• On the minimal displacement vector of the Douglas-Rachford operator
• On the circumcentered-reflection method for the convex feasibility problem
• On the order of the operators in the Douglas-Rachford algorithm
• On the Behavior of the Douglas--Rachford Algorithm for Minimizing a Convex Function Subject to a Linear Constraint
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Ergodic behaviour of a Douglas-Rachford operator away from the origin
• Convergence Analysis of the Relaxed Douglas--Rachford Algorithm
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• Convergence analysis of Douglas-Rachford splitting method for ``strongly + weakly convex programming
• On the Douglas–Rachford Algorithm for Solving Possibly Inconsistent Optimization Problems
• 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 with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
• Coordinate-update algorithms can efficiently detect infeasible optimization problems
• Linear convergence of resolvent splitting with minimal lifting and its application to a primal–dual algorithm
• On the minimal displacement vector of compositions and convex combinations of nonexpansive mappings

Describes a project that uses

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)