Numerical explorations of feasibility algorithms for finding points in the intersection of finite sets

arXiv1901.08183MaRDI QIDQ6312965FDOQ6312965

Sylvain Gretchko, Walaa M. Moursi, Heinz H. Bauschke

Publication date: 23 January 2019

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.

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) Decomposition methods (49M27) Numerical methods of relaxation type (49M20)

This page was built for publication: Numerical explorations of feasibility algorithms for finding points in the intersection of finite sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312965)