Contributions to the theory and applications of projection algorithms

Resumen

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.