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

Francisco J. Aragón Artacho (), Jonathan M. Borwein () and Matthew K. Tam ()
Additional contact information
Francisco J. Aragón Artacho: University of Alicante
Jonathan M. Borwein: University of Newcastle
Matthew K. Tam: University of Newcastle

Journal of Global Optimization, 2016, vol. 65, issue 2, No 7, 309-327

Abstract: 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.

Keywords: Douglas–Rachford algorithm; Global convergence; Feasibility problem; Half-space; Non-convex; 90C26; 65K05 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-015-0380-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:65:y:2016:i:2:d:10.1007_s10898-015-0380-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-015-0380-6

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().