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

DOI10.1007/S10898-015-0380-6zbMATH Open1338.90310arXiv1506.09026OpenAlexW3123298964MaRDI QIDQ288229FDOQ288229

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)

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.

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

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

zbMATH Keywords

global convergencehalf-spacefeasibility problemDouglas-Rachford algorithmnon-convex

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A cyclic Douglas-Rachford iteration scheme
• Global convergence of a non-convex Douglas-Rachford iteration
• On the local convergence of the Douglas-Rachford algorithm
• Linear convergence of the Douglas–Rachford method for two closed sets
• The Douglas-Rachford algorithm in the absence of convexity
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• The Cyclic Douglas-Rachford Method for Inconsistent Feasibility Problems
• Nonconvex Notions of Regularity and Convergence of Fundamental Algorithms for Feasibility Problems
• The Douglas-Rachford algorithm in the affine-convex case
• Douglas-Rachford feasibility methods for matrix completion problems
• Projection Methods: Swiss Army Knives for Solving Feasibility and Best Approximation Problems with Halfspaces
• Searching with iterated maps
• The Douglas-Rachford algorithm for the case of the sphere and the line

Cited In (23)

• Adaptive Douglas--Rachford Splitting Algorithm for the Sum of Two Operators
• Douglas-Rachford splitting and ADMM for pathological convex optimization
• A new projection method for finding the closest point in the intersection of convex sets
• A remark on the convergence of the Douglas-Rachford iteration in a non-convex setting
• Unrestricted Douglas-Rachford algorithms for solving convex feasibility problems in Hilbert space
• The cyclic Douglas–Rachford algorithm with r-sets-Douglas–Rachford operators
• A unified Douglas-Rachford algorithm for generalized DC programming
• A feasibility approach for constructing combinatorial designs of circulant type
• Ergodic behaviour of a Douglas-Rachford operator away from the origin
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems
• Solving Nonconvex Feasibility Problem on a Sphere and a Closed Ball by Douglas–Rachford Algorithm
• Circumcentering the Douglas-Rachford method
• Solving graph coloring problems with the Douglas-Rachford algorithm
• An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
• The Douglas-Rachford algorithm for a hyperplane and a doubleton
• Matrix product constraints by projection methods
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• Convergence of an Inertial Shadow Douglas-Rachford Splitting Algorithm for Monotone Inclusions
• Comparing Averaged Relaxed Cutters and Projection Methods: Theory and Examples
• On the Finite Convergence of the Douglas--Rachford Algorithm for Solving (Not Necessarily Convex) Feasibility Problems in Euclidean Spaces
• A Lyapunov function construction for a non-convex Douglas-Rachford iteration
• A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting

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)