Primal-dual splitting algorithms for constrained monotone inclusions

Abstract

En esta tesis proponemos un algoritmo eficiente de separación primal-dual para resolver inclusiones monótonas restrictas que incluyen un cono normal a un subespacio vectorial cerrado. Nuestro algoritmo incorpora una proyección adicional sobre un conjunto de restricciones, el cual representa información a priori en la solución. Este trabajo se divide en dos partes. En la primera parte, estudiamos el caso en que el subespacio vectorial es todo el espacio, demostrando convergencia débil de nuestro método, como también convergencia acelerada y convergencia lineal bajo correspondientes hipótesis adicionales sobre los operadores y parámetros del algoritmo. En la segunda parte, consideramos el caso general y demostramos convergencia débil de nuestro método mediante la caracterización de soluciones de la inclusión, usando la técnica de la inversa parcial de un operador. La eficiencia de nuestro método se ve reflejada en el contexto de optimización convexa con restricciones lineales afines y de subespacio vectorial. El uso de la información a priori permite la factibilidad de las iteraciones primales en un subconjunto de restricciones y el uso de la inversa parcial de un operador permite explotar la estructura del subespacio vectorial. Estas dos características de nuestro método mejoran la eficiencia con respecto a varios métodos clásicos en la literatura. Finalmente, también aplicamos nuestro método al problema de asignación de trafico en redes de transporte con expansión de capacidad de arco bajo incertidumbre, en el cual mostramos la ventaja de usar la estructura del subespacio vectorial del problema.

In this thesis we propose an efficient splitting algorithm for solving constrained primal-dual monotone inclusions with a normal cone to a closed vector subspace. Our algorithm incorporates an additional projection onto a set of constraints, which represents a priori information on the solutions. This work is divided in two parts. In the first part, we study the case when the vector subspace is the whole space, in which we provide weak convergence of our method, as well as accelerated convergence and linear convergence under corresponding additional hypotheses on the operators and step sizes of the algorithm. In the second part, we consider the general case and we demonstrate weak convergence of our method by characterizing the solutions to the inclusión using the partial inverse operator. The efficiency of our method is illustrated in the context of convex optimization with affine linear constraints and vector subspace constraints. The use of the a priori information allows the feasibility of primal iterations in a subset of constraints and the use of the partial inverse operator allows to exploit the vector subspace structure. These two features of our method improve the efficiency with respect to several methods in the literature. Finally, we also apply our method to solve the traffic assignment problem with arc-capacity expansion on a network with minimal cost under uncertainty, in which we show the advantage of using the vector subspace structure of the problem.