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

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 quest...

Full description

Saved in:
Bibliographic Details
Published in:Journal of global optimization 2016-06, Vol.65 (2), p.309-327
Main Authors: Aragón Artacho, Francisco J., Borwein, Jonathan M., Tam, Matthew K.
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Combinatorial analysis
Combinatorics
Computer Science
Convergence
Empirical analysis
Feasibility
Half spaces
Mathematical analysis
Mathematics
Mathematics and Statistics
Methods
Operations Research/Decision Theory
Optimization
Real Functions
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0925-5001
1573-2916
DOI:10.1007/s10898-015-0380-6