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

DOI10.1007/S10898-018-0654-XMaRDI QIDQ1630271zbMATH OpenOpenAlexWikidataFDO

Authors Minh N. Dao, Hung M. Phan

Publication date 7 December 2018

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

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

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)

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.

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

Cites work

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

Cited in

(25)

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

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)