On Slater’s condition and finite convergence of the Douglas–Rachford algorithm for solving convex feasibility problems in Euclidean spaces

Heinz H. Bauschke (), Minh N. Dao (), Dominikus Noll () and Hung M. Phan ()
Additional contact information
Heinz H. Bauschke: University of British Columbia
Minh N. Dao: University of British Columbia
Dominikus Noll: Université de Toulouse
Hung M. Phan: University of Massachusetts Lowell

Journal of Global Optimization, 2016, vol. 65, issue 2, No 8, 329-349

Abstract: Abstract The Douglas–Rachford algorithm is a classical and very successful method for solving optimization and feasibility problems. In this paper, we provide novel conditions sufficient for finite convergence in the context of convex feasibility problems. Our analysis builds upon, and considerably extends, pioneering work by Spingarn. Specifically, we obtain finite convergence in the presence of Slater’s condition in the affine-polyhedral and in a hyperplanar-epigraphical case. Various examples illustrate our results. Numerical experiments demonstrate the competitiveness of the Douglas–Rachford algorithm for solving linear equations with a positivity constraint when compared to the method of alternating projections and the method of reflection–projection.

Keywords: Alternating projections; Convex feasibility problem; Convex set; Douglas–Rachford algorithm; Epigraph; Finite convergence; Method of reflection–projection; Monotone operator; Partial inverse; Polyhedral set; Projector; Slater’s condition; Primary 47H09; 90C25; Secondary 47H05; 49M27; 65F10; 65K05; 65K10 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-015-0373-5 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-0373-5

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

DOI: 10.1007/s10898-015-0373-5

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 ().