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

DOI10.1137/15M1016989MaRDI QIDQ2804207zbMATHOpenAlexFDO

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

fixed pointgeneralized solutionmaximally monotone operatoraffine subspaceDouglas-Rachford splitting operatornormal cone operatorprojection operatorfirmly nonexpansive mappinglinear convergencenormal problemAttouch-Théra duality

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)

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

• 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?)
• 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
• From Hahn--Banach to monotonicity
• Fréchet-Legendre functions and reflexive Banach spaces
• Generalized solutions for the sum of two maximally monotone operators
• 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

(30)

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

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)