Splitting algorithms for distributionally robust optimization

Abstract

En esta tesis, se demuestran algunas propiedades variacionales de la función supremo y se proponen diferentes algoritmos de separación para resolver problemas que involucran funciones supremo, enfocándose en el problema de optimización distribucionalmente robusto (DRO). Se calcula la regularizada de Moreau y el operador proximal de un supremo de funciones débilmente convexas. Adicionalmente, se prueban algunos resultados que relacionan el problema de optimización robusta con su versión regularizada, generalizando resultados obtenidos en la literatura. Además, usando la regularizada de Goebel, se prueba que no hay salto de dualidad para el problema de programación infinita regularizado y se propone un método que converge a la solución del problema dual, el cual es explicito en un caso importante. Por otro lado, se introduce la noción de función localmente débilmente convexa y se calcula localmente la regularizada de Moreau del supremo de dicha clase de funciones. Además, se propone un algoritmo de separación para resolver un problema con funciones supremo sin restricciones el cual satisface que cada punto de acumulación de la sucesión del algoritmo es un punto crítico. También se propone un método inexacto para encontrar puntos críticos de funciones que son el máximo de funciones que satisfacen la propiedad KL. Con respecto al problema DRO en el caso convexo, se propone un algoritmo de separación para resolver el DRO en el caso discreto en algunos casos importantes, el cual esta basado en calcular el operador proximal de la función supremo que aparece en el DRO. Además, se reformula el DRO como una inclusión monótona y se calculan las resolventes de los operadores monótonos involucrados en dicha inclusión. Finalmente, en el caso débilmente convexo, se propone un algoritmo tipo 'variable smoothing' proyectado para resolver un problema de optimización débilmente convexo con restricciones, donde la restricción es un subespacio vectorial cerrado, generalizando un problema estudiado en la literatura. También se calcula el operador proximal de un supremo de funciones débilmente convexas en algunos casos importantes.

In this thesis, we prove some variational properties of the supremum function and we propose different splitting algorithms for solving problems involving supremum functions, focusing in the distributionally robust optimization (DRO) problem. We compute the Moreau envelope and the proximity operator of a supremum of weakly convex functions. Additionally, we prove some results that relate the robust optimization problem with its regularized version, generalizing the results obtained in the literature. Furthermore, using the regularized of Goebel, we prove that there is no duality gap for the regularized infinite programming problem and we provide a method that converges to the solution of the dual problem, which is explicit in an important case. On the other hand, we introduce the notion of locally weakly convex function and we calculate locally the Moreau envelope of the supremum of said class of functions. In addition, we propose a splitting algorithm to solve a problem with supremum functions without constraints which satisfies that every cluster point of the sequence of the algorithm is a critical point. Moreover, we propose an inexact method to find critical points of functions that are the maximum of functions that satisfy the KL property. With respect to the DRO problem in the convex case, we propose a splitting method for solving the DRO in the discrete case in some important cases, which is based in computing the proximity of the supremum function appearing in the DRO. In addition, we reformulate the DRO as a monotone inclusion and we compute the resolvents of the monotone operators involved in said inclusion. Finally, in the weakly convex case, we propose a projected variable smoothing algorithm for solving a constrained weakly convex optimization problem, where the constraint is a closed vector subspace, generalizing a problem studied in the literature. Also, we compute the proximity of a supremum of weakly convex functions in some important cases.