Numerical Explorations of Feasibility Algorithms for Finding Points in the Intersection of Finite Sets

Heinz H. Bauschke (), Sylvain Gretchko () and Walaa M. Moursi ()
Additional contact information
Heinz H. Bauschke: University of British Columbia, Department of Mathematics
Sylvain Gretchko: Mathematics, UBCO
Walaa M. Moursi: Stanford University, Electrical Engineering

Chapter Chapter 3 in Splitting Algorithms, Modern Operator Theory, and Applications, 2019, pp 69-90 from Springer

Abstract: Abstract Projection methods are popular algorithms for iteratively solving feasibility problems in Euclidean or even Hilbert spaces. They employ (selections of) nearest point mappings to generate sequences that are designed to approximate a point in the intersection of a collection of constraint sets. Theoretical properties of projection methods are fairly well understood when the underlying constraint sets are convex; however, convergence results for the nonconvex case are more complicated and typically only local. In this paper, we explore the perhaps simplest instance of a feasibility algorithm, namely when each constraint set consists of only finitely many points. We numerically investigate four constellations: either few or many constraint sets, with either few or many points. Each constellation is tackled by four popular projection methods each of which features a tuning parameter. We examine the behaviour for a single and for a multitude of orbits, and we also consider local and global behaviour. Our findings demonstrate the importance of the choice of the algorithm and that of the tuning parameter.

Keywords: Cyclic Douglas–Rachford algorithm; Douglas–Rachford algorithm; Extrapolated parallel projection method; Method of cyclic projections; Nonconvex feasibility problem; Optimization algorithm; Projection; 49M20; 49M27; 49M37; 65K05; 65K10; 90C25; 90C26; 90C30 (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:sprchp:978-3-030-25939-6_3

Ordering information: This item can be ordered from
http://www.springer.com/9783030259396

DOI: 10.1007/978-3-030-25939-6_3

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().