Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems

DOI10.1007/S10898-018-0654-XzbMATH Open1499.90170arXiv1710.09814OpenAlexW2796899174WikidataQ129973878 ScholiaQ129973878MaRDI QIDQ1630271FDOQ1630271

Authors: Minh N. Dao, Hung M. Phan 

Publication date: 7 December 2018

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: In this paper, we study the generalized Douglas-Rachford algorithm and its cyclic variants which include many projection-type methods such as the classical Douglas-Rachford algorithm and the alternating projection algorithm. Specifically, we establish several local linear convergence results for the algorithm in solving feasibility problems with finitely many closed possibly nonconvex sets under different assumptions. Our findings not only relax some regularity conditions but also improve linear convergence rates in the literature. In the presence of convexity, the linear convergence is global.

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

Recommendations

• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
• A linearly convergent algorithm for solving a class of nonconvex/affine feasibility problems
• A convergent relaxation of the Douglas-Rachford algorithm
• On the Behavior of the Douglas--Rachford Algorithm for Minimizing a Convex Function Subject to a Linear Constraint
• On the finite termination of the Douglas-Rachford method for the convex feasibility problem
• Convergence of a General Class of Algorithms for Separated Continuous Linear Programs
• Unrestricted Douglas-Rachford algorithms for solving convex feasibility problems in Hilbert space
• Sulla convergenza di un algoritmo di direzioni ammissibili per problemi di ottimo a vincoli lineari con funzione oggetto convessa non differenziabile
• Approximate Douglas-Rachford algorithm for two-sets convex feasibility problems

zbMATH Keywords

cyclic algorithmlinear convergencesuperregularitystrong regularitylinear regularityaffine-hull regularitygeneralized Douglas-Rachford algorithmquasi coercivityquasi Fejér monotonicity

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Iterative procedures involving nonlinear operators (47J25) Decomposition methods (49M27)

Cites Work

• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Variational Analysis
• On Projection Algorithms for Solving Convex Feasibility Problems
• Some continuity properties of polyhedral multifunctions
• Title not available (Why is that?)
• Title not available (Why is that?)
• A cyclic Douglas-Rachford iteration scheme
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• About regularity of collections of sets
• Linear convergence of the Douglas-Rachford method for two closed sets
• On Slater's condition and finite convergence of the Douglas-Rachford algorithm for solving convex feasibility problems in Euclidean spaces
• Restricted normal cones and the method of alternating projections: applications
• Restricted normal cones and the method of alternating projections: theory
• Linear and strong convergence of algorithms involving averaged nonexpansive operators
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• Local linear convergence for alternating and averaged nonconvex projections
• The Douglas-Rachford algorithm in the affine-convex case
• Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study
• Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
• Searching with iterated maps
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Dykstra's alternating projection algorithm for two sets
• On weak convergence of the Douglas-Rachford method
• Convex analysis and monotone operator theory in Hilbert spaces
• Strong conical hull intersection property, bounded linear regularity, Jameson's property \((G)\), and error bounds in convex optimization
• Remarks on piecewise-linear algebra
• The method of alternating relaxed projections for two nonconvex sets
• Transversality and alternating projections for nonconvex sets
• On the Douglas-Rachford algorithm
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
• Norm convergence of realistic projection and reflection methods

Cited In (25)

• Primal necessary characterizations of transversality properties
• Generalized alternating projections on manifolds and convex sets
• Regularity of sets under a reformulation in a product space with reduced dimension
• 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
• Computing the resolvent of the sum of operators with application to best approximation problems
• On Slater's condition and finite convergence of the Douglas-Rachford algorithm for solving convex feasibility problems in Euclidean spaces
• Convergence Analysis of the Relaxed Douglas--Rachford Algorithm
• Union averaged operators with applications to proximal algorithms for MIN-convex functions
• A convergent relaxation of the Douglas-Rachford algorithm
• Adaptive Douglas-Rachford splitting algorithm for the sum of two operators
• A second-order adaptive Douglas-Rachford dynamic method for maximal \(\alpha\)-monotone operators
• Comparing averaged relaxed cutters and projection methods: theory and examples
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• Linear convergence of the Douglas-Rachford method for two closed sets
• Constraint reduction reformulations for projection algorithms with applications to wavelet construction
• The Douglas-Rachford algorithm for a hyperplane and a doubleton
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• A note on the finite convergence of alternating projections
• Asymptotic behaviour of a nonautonomous evolution equation governed by a quasi-nonexpansive operator
• Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study
• A Lyapunov function construction for a non-convex Douglas-Rachford iteration
• On the Behavior of the Douglas--Rachford Algorithm for Minimizing a Convex Function Subject to a Linear Constraint
• A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting
• Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency

This page was built for publication: Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems

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