Contributions to the theory and applications of projection algorithms

Résumé

This thesis focuses on the family of the so-called projection algorithms. These algorithms are employed for solving feasibility problems, whose goal is to find a point in the intersection of a collection of sets in a Hilbert space. Often, the intersection set is hard to deal with, while the projection mappings onto the individual sets are readily computable. Projection algorithms iterate by making use of these projections, to generate a convergent sequence whose limit solves the problem. Two of the most well-known algorithms within this class are the method of alternating projections and the Douglas-Rachford algorithm. The weak convergence of these algorithms to a point in the intersection is guaranteed, provided that the involved sets are convex. In the special case where these sets are closed affine subspaces, the aforementioned methods not only find a point in the intersection, but they converge to the closest one to the initial point. However, this is not the case for arbitrary convex sets. The problem of finding the closest point in the intersection to any given point in the space is known as the best approximation problem. There are specific projection methods for solving this type of problems. For instance, Dykstra's algorithm is an appropriate modification of the method of alternating projections that forces the strong convergence to the projection of the initial point onto the intersection. In this dissertation, we propose a modification of the Douglas-Rachford method that allow us to solve best approximation problems, rather than just feasibility ones. Due to the geometry of the iteration, the Douglas-Rachford algorithm is also referred to as the averaged alternating reflections (AAR) method. Our approach consists in altering the reflection steps at each iterate. For this reason, the new iterative projection method is termed AAMR for averaged alternating modified reflections method. Under a constraint qualification at the point of interest, we show strong convergence of the method. We compare the performance of AAMR against other projection methods for finding the closest point in the intersection of pairs of finite dimensional subspaces, first numerically, and then analytically by studying the rate of linear convergence of the algorithm within this context. When the parameters defining the scheme are optimally selected, the obtained rate becomes the best among all known rates of other projection algorithms. We also extend the algorithm so that it can deal with operators instead of sets. This gives rise to a new splitting algorithm for computing the resolvent of the sum of maximally monotone operators. In the last years, the Douglas-Rachford algorithm has received much attention, due in part to the good performance of the method in nonconvex scenarios. Despite a lack of convergence results, the algorithm has been successfully employed in a wide list of combinatorial problems. In this thesis we extend that list of applications, by incorporating the graph coloring problem and the construction of combinatorial designs of circulant type. For the former, we present two feasibility problems of different nature which model the problem. The good performance of the algorithm when it is applied to these formulations is demonstrated through various computational experiments. For the case of combinatorial designs, we propose a general feasibility problem which models different classes of them. We illustrate the applicability of the formulation to the construction of circulant weighing matrices, D-optimal matrices, and Hadamard matrices with two circulant cores. Furthermore, we derive explicit constructions of two circulant weighing matrices whose existence was previously marked as an open question.