Splitting algorithms for structured optimizationtheory and applications

Resumen

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.