ALTERNATING AND RANDOMIZED PROJECTIONS ON CONVEX OPTIMIZATION

Abstract

En este trabajo, proponemos dos enfoques numéricos para resolver problemas primales-duales de optimización convexa con restricciones. Las restricciones del problema están representadas por la intersección de un número finito de conjuntos convexos cerrados sobre los cuales los algoritmos propuestos proyectan de manera alternada y/o aleatoria. El primer algoritmo incluye un paso de activación aleatorio sobre un esquema de proyección cíclico, mientras que el segundo elige un elemento aleatorio del conjunto de operadores de proyección. La convergencia casi segura de ambos algoritmos se deriva de las propiedades de las sucesiones estocásticas Quasi-Fejér. Como casos especiales de los algoritmos propuestos, recuperamos varios algoritmos primales-duales en la literatura y algoritmos clásicos para resolver problemas de factibilidad de conjuntos convexos, como proyecciones cíclicas, Kaczmarz y Kaczmarz aleatorio. Finalmente, probamos ambos algoritmos en un problema de expansión de capacidad de arco en una red de transporte. El problema puede formularse como un problema primal-dual de optimización convexa con restricciones. Luego comparamos la eficiencia de diferentes esquemas de proyección alternada / aleatoria propuestos en este trabajo con el algoritmo primal-dual sin ninguna proyección. Todos los algoritmos propuestos que incluyen una proyección mejoran considerablemente el tiempo de ejecución y el número de iteraciones. En el caso de los algoritmos que incluyen proyecciones aleatorias y alternada obtenemos hasta un 31% y 35% de mejora en el tiempo de ejecución promedio, respectivamente, en los ejemplos de dimensiones superiores.