Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem

DOI10.1007/S10898-015-0380-6MaRDI QIDQ288229zbMATH OpenOpenAlexFDO

Authors Francisco J. Aragón Artacho, Matthew K. Tam, Jonathan M. Borwein

Publication date 25 May 2016

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

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

zbMATH Keywords

global convergencehalf-spacefeasibility problemDouglas-Rachford algorithmnon-convex

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26)

Abstract: In recent times the Douglas-Rachford algorithm has been observed empirically to solve a variety of nonconvex feasibility problems including those of a combinatorial nature. For many of these problems current theory is not sufficient to explain this observed success and is mainly concerned with questions of local convergence. In this paper we analyze global behavior of the method for finding a point in the intersection of a half-space and a potentially non-convex set which is assumed to satisfy a well-quasi-ordering property or a property weaker than compactness. In particular, the special case in which the second set is finite is covered by our framework and provides a prototypical setting for combinatorial optimization problems.

Recommendations

• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting
• On the local convergence of the Douglas-Rachford algorithm
• Solving nonconvex feasibility problem on a sphere and a closed ball by Douglas-Rachford algorithm
• The Douglas-Rachford algorithm in the absence of convexity

Cites work

• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• A cyclic Douglas-Rachford iteration scheme
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• Douglas-Rachford feasibility methods for matrix completion problems
• Global convergence of a non-convex Douglas-Rachford iteration
• Linear convergence of the Douglas-Rachford method for two closed sets
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• On the local convergence of the Douglas-Rachford algorithm
• Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• Searching with iterated maps
• The Douglas-Rachford algorithm for the case of the sphere and the line
• The Douglas-Rachford algorithm in the absence of convexity
• The Douglas-Rachford algorithm in the affine-convex case
• The cyclic Douglas-Rachford method for inconsistent feasibility problems

Cited in

(25)

• Unrestricted Douglas-Rachford algorithms for solving convex feasibility problems in Hilbert space
• A unified Douglas-Rachford algorithm for generalized DC programming
• Comparing averaged relaxed cutters and projection methods: theory and examples
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Circumcentering the Douglas-Rachford method
• Solving graph coloring problems with the 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
• A new projection method for finding the closest point in the intersection of convex sets
• 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
• An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
• Recent results on Douglas-Rachford methods.
• Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems
• Matrix product constraints by projection methods
• Douglas-Rachford splitting and ADMM for pathological convex optimization
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• A remark on the convergence of the Douglas-Rachford iteration in a non-convex setting
• The cyclic Douglas-Rachford method for inconsistent feasibility problems
• A feasibility approach for constructing combinatorial designs of circulant type
• Convergence of an Inertial Shadow Douglas-Rachford Splitting Algorithm for Monotone Inclusions
• Solving nonconvex feasibility problem on a sphere and a closed ball by Douglas-Rachford algorithm
• Ergodic behaviour of a Douglas-Rachford operator away from the origin
• The cyclic Douglas–Rachford algorithm with r-sets-Douglas–Rachford operators

This page was built for publication: Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem

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