Iterative projection and reflection methods: theory and practice

This thesis investigates the family of so-called projection and reflection methods. These methods form the basis for a class of iterative algorithms which can be used to solve the feasibility problem which asks for a point in the intersection of a collection of constraint sets. Many optimisation and reconstruction problems can be profitably modelled within this framework, although the formulation is not always immediately obvious. In a typical feasibility problem the target intersection set is difficult to deal with directly. Projection and reflection algorithms overcome this difficulty by exploiting relatively simpler structure in each of the individual constraint sets from the collection. In recent times, a particular member of the projection method family, the Douglas-Rachford method, has received extra attention. This is, in part, due to its empirically observed ability to successfully solve a variety of difficult non-convex problems including those of a combinatorial nature. Furthermore, even in the classical setting of convexity, there is some divergence in the features of the Douglas-Rachford method as compared to other members of the projection method family such as the alternating projection method. Until the work of this thesis, it was only possible to apply the Douglas-Rachford algorithm to feasibility problems involving only two constraints whereas virtually every other projection-type algorithm exhibited a natural many-set extension. The organisation of this work is as follows: Chapter 1 introduces basic definitions, notation and background, before formally introducing the feasibility problem framework and fundamental projection-type algorithms. Chapter 2 focuses on theory in the presence of convex constraint sets, and introduces the recently developed cyclic Douglas-Rachford method which has since been referred to as the Borwein-Tam method in the literature. Chapter 3 focuses on theory in the absence of convexity. In this case, theoretical underpinnings are still in development and rather more cumbersome. Specific classes or instances of non-convex feasibility problems must be considered separately. Chapter 4 investigates applications, particularly of the Douglas-Rachford algorithm to settings without convexity. Chapter 5 summarises the contributions of this work as well as indicating open problems for future research.