The Douglas–Rachford algorithm for convex and nonconvex feasibility problems

Francisco J. Aragón Artacho (), Rubén Campoy () and Matthew K. Tam ()
Additional contact information
Francisco J. Aragón Artacho: University of Alicante
Rubén Campoy: University of Alicante
Matthew K. Tam: University of Göttingen

Mathematical Methods of Operations Research, 2020, vol. 91, issue 2, No 3, 240 pages

Abstract: Abstract The Douglas–Rachford algorithm is an optimization method that can be used for solving feasibility problems. To apply the method, it is necessary that the problem at hand is prescribed in terms of constraint sets having efficiently computable nearest points. Although the convergence of the algorithm is guaranteed in the convex setting, the scheme has demonstrated to be a successful heuristic for solving combinatorial problems of different type. In this self-contained tutorial, we develop the convergence theory of projection algorithms within the framework of fixed point iterations, explain how to devise useful feasibility problem formulations, and demonstrate the application of the Douglas–Rachford method to said formulations. The paradigm is then illustrated on two concrete problems: a generalization of the “eight queens puzzle” known as the “(m, n)-queens problem”, and the problem of constructing a probability distribution with prescribed moments.

Keywords: Projection methods; Douglas–Rachford; Feasibility problem; Eight queens problem; 65K05; 90C27; 90-01; 65-01 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00186-019-00691-9 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:mathme:v:91:y:2020:i:2:d:10.1007_s00186-019-00691-9

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-019-00691-9

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().