Contribuciones a la teoría y a las aplicaciones de los algoritmos de proyección

Abstract

Esta tesis contribuye a la familia de los llamados algoritmos de proyección. Estos algoritmos se utilizan para resolver problemas de factibilidad, en los que se busca obtener un punto en la intersección de una familia de conjuntos en un espacio de Hilbert. En muchas ocasiones, abordar esta intersección en sí misma resulta una tarea complicada, mientras que la proyección sobre cada uno de los conjuntos se puede calcular de forma eficiente. Los algoritmos de proyección utilizan estas proyecciones de forma iterativa, definiendo una sucesión que converge a un punto que permite resolver el problema. Dos de los algoritmos de proyección más conocidos son el método de proyecciones alternadas y el algoritmo de Douglas–Rachford. La convergencia débil de estos algoritmos hacia un punto en la intersección está garantizada cuando los conjuntos son convexos. En el caso particular de que dichos conjuntos sean subespacios afines, estos métodos no solo encuentran un punto cualquiera en la intersección, sino que dicho punto es, de hecho, el más cercano al punto inicial. El problema de encontrar el punto en la intersección más próximo a cualquier otro punto dado se conoce como el problema de mejor aproximación. Existen métodos de proyección específicos para resolver este problema. Uno de ellos es el algoritmo de Dykstra, que surge como una modificación apropiada del método de proyecciones alternadas. En esta tesis proponemos una modificación del método de Douglas–Rachford, obteniendo un nuevo algoritmo que permite resolver problemas de mejor aproximación, en lugar de simplemente problemas de factibilidad. El método de Douglas–Rachford también es conocido como el algoritmo de reflexiones alternadas ponderadas, debido a la interpretación geométrica de la iteración que define. Nuestro enfoque consiste en modificar estas reflexiones sobre los conjuntos. Por eso, llamamos al nuevo algoritmo el método de reflexiones modificadas alternadas ponderadas (abreviado AAMR, del inglés averaged alternating modified reflections method). Bajo una cualificación de restricciones en el punto de interés, probamos la convergencia fuerte del algoritmo a la proyección de dicho punto sobre la intersección de los conjuntos. Comparamos el nuevo AAMR con otros métodos de proyección en problemas de mejor aproximación definidos por subespacios lineales de dimensión finita. Cuando los parámetros que definen la iteración del AAMR son elegidos de forma óptima, la tasa obtenida resulta ser la mejor entre las tasas conocidas de otros algoritmos de proyección clásicos. También extendemos el algoritmo a un contexto más general, donde puede aplicarse a operadores en lugar de conjuntos. Esto da lugar a un nuevo método de descomposición, que permite calcular el resolvente de la suma de operadores monótonos maximales, utilizando evaluaciones individuales de los resolventes de cada operador. En los últimos años el algoritmo de Douglas–Rachford ha despertado un gran interés, debido en parte a su buen comportamiento en escenarios no convexos. A pesar de la escasez de resultados teóricos que lo justifiquen, el algoritmo ha sido empleado con éxito en una amplia lista de problemas combinatorios. En esta tesis extendemos dicha lista, incorporando el problema de coloreado de grafos y la construcción de diseños combinatorios de tipo circular. Para el primero de éstos, presentamos dos problemas de factibilidad de naturaleza distinta que reformulan el problema. Además, mostramos mediante varios experimentos numéricos el buen funcionamiento del algoritmo cuando se aplica a estas formulaciones. En el caso de los diseños combinatorios, proponemos una formulación genérica que permite modelar diferentes clases. La aplicabilidad de esta formulación se ilustra con la construcción de matrices circulares de ponderación, matrices D-óptimas y matrices de Hadamard con dos núcleos circulares. Asimismo, construimos de forma explícita dos matrices circulares de ponderación cuya existencia estaba indicada como un problema abierto.

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.