Resumen de Splitting algorithms for structured optimization: theory and applications

David Torregrosa Belén

• español

  Los avances actuales en tecnología y el incremento de información disponible hacen que los problemas de optimización aumenten progresivamente en tamaño y complejidad. Una correcta aproximación a su tratamiento numérico precisa de un estudio cuidadoso de los datos de partida. En otras palabras, es fundamental ser capaz de sacar provecho de la estructura matemática del problema. Siguiendo la estrategia de divide y vencerás, los algoritmos de desglose se especializan en abordar programas matemáticos a través de la resolución iterativa de tareas simples, las cuales se definen empleando partes del problema original de manera independiente. Esto ha hecho que esta clase de algoritmos se consolide como una de las más fructíferas en el área de la optimización numérica. Las aportaciones de esta tesis se presentan en dos partes claramente diferenciadas, pero que comparten un mismo objetivo común: mejorar la eficiencia de los procesos computacionales de los algoritmos de desglose. Cada uno de los programas matemáticos abordados a lo largo de la tesis requerirá de un enfoque específico para la consecución de dicha meta. Asimismo, la eficacia de nuestros desarrollos teóricos se ilustrará en experimentos numéricos en diversas aplicaciones, como planificación de tratamientos de radioterapia de intensidad modulada. En la primera parte de la tesis nos focalizamos en los algoritmos de desglose para operadores monótonos. Estos métodos se emplean para resolver inclusiones monótonas. En las últimas décadas, una anomalía común ha persistido en el diseño de algoritmos en esta familia: la dimensión del espacio subyacente, la cual denotaremos como lifting, al algoritmo crece atípicamente conforme aumenta el tamaño del problema. Esto afecta directamente al rendimiento del algoritmo. En este contexto, caracterizamos el lifting mínimo al que se debe atener un algoritmo de desglose adecuado para la resolución de ciertos casos generales de inclusiones monótonas. Más aún, proponemos nuevos algoritmos que tienen lifting mínimo, siendo los primeros métodos en la familia de algoritmos de desglose para operadores monótonos que satisfacen esta cota. El análisis desarrollado conduce a una nueva demostración de la convergencia del algoritmo de Davis-Yin, que permite duplicar el rango de valores admitidos para el parámetro de tamaño de paso del algoritmo. En la segunda parte introducimos dos avances independientes en la teoría de algoritmos de desglose. En el Capítulo 8 nos trasladamos al dominio no convexo. Aquí introducimos el algoritmo BDSA, un nuevo método de desglose diseñado para abordar programas matemáticos que involucran estructuras no convexas y no diferenciables. Mientras que BDSA engloba algoritmos ya existentes en la literatura, extiende su aplicación a configuraciones de problemas más diversas. Una de las características de BDSA, que lo diferencia de otros métodos previamente propuestos, es la integración de una búsqueda lineal para mejorar su rendimiento. Experimentos numéricos revelan que esta búsqueda lineal reduce considerablemente el número de iteraciones y el tiempo que BDSA necesita para converger, y aumenta la eficacia de BDSA para evitar puntos críticos no óptimos. Finalmente, en el Capítulo 9, consideramos el problema de minimización dividido que consta de dos subproblemas de minimización con restricciones en dos espacios distintos bajo un operador lineal que asigna un espacio al otro. Para afrontar este problema desarrollamos un enfoque de superiorización que permite obtener a un punto factible con valores de las funciones objetivo reducidos. El método de superiorización se basa en entrelazar los pasos de dos procesos iterativos separados e independientes, perturbando las iteraciones de un proceso de acuerdo con los pasos dictados por el otro proceso. Incluimos dos elementos novedosos. El primero es la posibilidad de reiniciar las perturbaciones en el algoritmo superiorizado, lo que resulta en una aceleración. El segundo, es la capacidad de superiorizar subvectores de forma independiente.

• English

  With modern advances in technologies and quantity of information, optimization problems become increasingly large in size and complexity. Successfully handling these ever evolving problems requires a careful processing of the available data, namely, taking advantage of the inherent mathematical structure of the problem. Following the divide-and-conquer paradigm, splitting algorithms specialize in tackling mathematical programs by iteratively solving simpler subtasks, which are defined by separately using some parts of the original problem. This has led this class of algorithms to emerge as one of the most fruitful among modern numerical optimization methods. This thesis contributes to the theory of splitting algorithms for both convex and nonconvex optimization. Our contributions are presented in two clearly differentiated parts, but which share a common core objective: to enhance the efficiency of the algorithms' computational processes. This goal is achieved through distinct approaches tailored to each specific mathematical program faced throughout the thesis. In addition, the effectiveness of our theoretical developments is validated in numerical experiments arising in multiple real-world applications, such as intensity-modulated radiation therapy treatment planning. In Part I, we concentrate on monotone operator splitting methods. These algorithms are employed for solving monotone inclusions. In the last decades, a common anomaly has persisted in the design of algorithms in this family: the dimension of the underlying space, which we denote as lifting, of the algorithms abnormally increases as the problem size grows. This has direct implications on the computational performance of the methods as a result of the escalation of memory requirements. In this framework, we characterize the minimal lifting that can be obtained by splitting algorithms adept at solving certain general monotone inclusions. Moreover, we pioneer the development of splitting methods matching these lifting bounds, and thus having minimal lifting. The analysis developed in this context also leads to a new proof of convergence of the popular Davis-Yin splitting algorithm which allows to double the range of admitted stepsize parameter values. Two independent advances to the family of splitting algorithms are presented in Part 2. In Chapter 8, we move to the nonconvex realm. The analysis of splitting methods for nonconvex problems has not been developed to the same extent as in the convex setting, with convergence guarantees only given for some restricted problem structures. We introduce the Boosted Double-proximal Subgradient Algorithm (BDSA), a novel splitting algorithm designed to address general structured nonsmooth and nonconvex mathematical programs. While BDSA encompasses existing schemes in the literature, it extends its applicability to more diverse problem domains. One of the features of BDSA is the integration of a linesearch procedure to enhance its performance. Numerical experience reveals that this linesearch considerably reduces both the number of iterations and the time that BDSA needs to converge in comparison with algorithms including inertial terms. In addition, we introduce two new families of test functions to illustrate BDSA's ability to effectively escape non-optimal critical points. Finally, in Chapter 9, we study the split minimization problem that consists of two constrained minimization problems in two separate spaces that are connected via a linear operator that maps one space into the other. To handle the data of such a problem, we develop a superiorization approach that can reach a feasible point with reduced objective function values. The superiorization methodology is based on interlacing the iterative steps of two separate and independent iterative processes by perturbing the iterates of one process according to the steps dictated by the other. We include two novel elements. The first one is the permission to restart the perturbations, which results in a significant acceleration. The second element is the ability to independently superiorize subvectors