The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
From MaRDI portal
Publication:2189471
Abstract: The Douglas-Rachford method, a projection algorithm designed to solve continuous optimization problems, forms the basis of a useful heuristic for solving combinatorial optimization problems. In order to successfully use the method, it is necessary to formulate the problem at hand as a feasibility problem with constraint sets having efficiently computable nearest points. In this self-contained tutorial, we develop the convergence theory of projection algorithms within the framework of fixed point iterations, explain how to devise useful feasibility problem formulations, and demonstrate the application of the Douglas-Rachford method to said formulations. The paradigm is then illustrated on two concrete problems: a generalization of the "eight queens puzzle" known as the "(m,n)-queens problem", and the problem of constructing a probability distribution with prescribed moments.
The feasibility problem is to find a point contained in the intersection of a finite collection of constraint sets. This paper is a tutorial on the Douglas-Rachford algorithm for solving convex and nonconvex feasibility problems for the unacquainted. Several known projection algorithms, particularly the Douglas-Rachford method, are analyzed. The Douglas-Rachford method is applied to solve the combinatorial \((m, n)\)-queens problem as well as the problem of constructing a probability distribution with prescribed moments.
Recommendations
- On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
- On the local convergence of the Douglas-Rachford algorithm
- Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
- A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting
- SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
Cites work
- A convergent relaxation of the Douglas-Rachford algorithm
- A cyclic Douglas-Rachford iteration scheme
- A feasibility approach for constructing combinatorial designs of circulant type
- A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting
- A new projection method for finding the closest point in the intersection of convex sets
- Affine nonexpansive operators, Attouch-Théra duality and the Douglas-Rachford algorithm
- Algorithms based on unions of nonexpansive maps
- Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
- An alternating projection that does not converge in norm
- An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
- Application of projection algorithms to differential equations: boundary value problems
- Asymptotic behavior of contractions in Hilbert space
- Best approximation in inner product spaces
- Circumcentering the Douglas-Rachford method
- Convex analysis and monotone operator theory in Hilbert spaces
- Decomposition through formalization in a product space
- Douglas-Rachford feasibility methods for matrix completion problems
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- Dynamics of the Douglas-Rachford method for ellipses and p-spheres
- Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
- Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
- Functional Operators (AM-22), Volume 2
- Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
- Global convergence of a non-convex Douglas-Rachford iteration
- scientific article; zbMATH DE number 4212061 (Why is no real title available?)
- scientific article; zbMATH DE number 3912113 (Why is no real title available?)
- scientific article; zbMATH DE number 3615396 (Why is no real title available?)
- scientific article; zbMATH DE number 3229228 (Why is no real title available?)
- scientific article; zbMATH DE number 3230744 (Why is no real title available?)
- Iterative methods for fixed point problems in Hilbert spaces
- Linear and strong convergence of algorithms involving averaged nonexpansive operators
- Linear convergence of the Douglas-Rachford method for two closed sets
- Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
- New demiclosedness principles for (firmly) nonexpansive operators
- New Douglas-Rachford algorithmic structures and their convergence analyses
- Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
- Norm convergence of realistic projection and reflection methods
- On the asymptotic behaviour of the Aragón Artacho-Campoy algorithm
- On the Douglas-Rachford algorithm
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
- On the local convergence of the Douglas-Rachford algorithm
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- On weak convergence of the Douglas-Rachford method
- Projection methods: an annotated bibliography of books and reviews
- Proximity Maps for Convex Sets
- Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
- Recent results on Douglas-Rachford methods for combinatorial optimization problems
- Reflection Methods for Inverse Problems with Applications to Protein Conformation Determination
- Searching with iterated maps
- Solving graph coloring problems with the Douglas-Rachford algorithm
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- The Complexity of Bit Retrieval
- The cyclic Douglas-Rachford method for inconsistent feasibility problems
- The cyclic Douglas–Rachford algorithm with r-sets-Douglas–Rachford operators
- The Douglas-Rachford algorithm for a hyperplane and a doubleton
- The Douglas-Rachford algorithm for the case of the sphere and the line
- The Douglas-Rachford algorithm in the absence of convexity
- The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
- Union averaged operators with applications to proximal algorithms for MIN-convex functions
- Weak convergence of the sequence of successive approximations for nonexpansive mappings
Cited in
(37)- Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
- The circumcentered-reflection method achieves better rates than alternating projections
- Constraint reduction reformulations for projection algorithms with applications to wavelet construction
- Circumcentering reflection methods for nonconvex feasibility problems
- A product space reformulation with reduced dimension for splitting algorithms
- An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
- The block-wise circumcentered-reflection method
- Strengthened splitting methods for computing resolvents
- A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
- A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
- The Douglas-Rachford algorithm for a hyperplane and a doubleton
- On the local convergence of the Douglas-Rachford algorithm
- On the circumcentered-reflection method for the convex feasibility problem
- Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
- Douglas-Rachford feasibility methods for matrix completion problems
- Application of projection algorithms to differential equations: boundary value problems
- On the Behavior of the Douglas--Rachford Algorithm for Minimizing a Convex Function Subject to a Linear Constraint
- Fixed point algorithms for nonconvex feasibility with applications
- Recent results on Douglas-Rachford methods.
- The cyclic Douglas–Rachford algorithm with r-sets-Douglas–Rachford operators
- On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
- Multiscale hierarchical image decomposition and refinements: qualitative and quantitative results
- Circumcentric directions of cones
- Computable centering methods for spiraling algorithms and their duals, with motivations from the theory of Lyapunov functions
- On the centralization of the circumcentered-reflection method
- Regularity of sets under a reformulation in a product space with reduced dimension
- Approximate Douglas-Rachford algorithm for two-sets convex feasibility problems
- A successive centralized circumcentered-reflection method for the convex feasibility problem
- Strict pseudocontractions and demicontractions, their properties, and applications
- A finitely convergent circumcenter method for the convex feasibility problem
- Finite element approximation of data-driven problems in conductivity
- How to project onto the intersection of a closed affine subspace and a hyperplane
- Centralized circumcentered-reflection method for solving the convex feasibility problem in sparse signal recovery
- Quasioptimal alternating projections and their use in low-rank approximation of matrices and tensors
- The construction of multidimensional membership functions and its application to feasibility problems
- Circumcentered reflections method for wavelet feasibility problems
- A convergent relaxation of the Douglas-Rachford algorithm
This page was built for publication: The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189471)
