Métodos de descomposición para problemas de optimización separable con restricciones lineales

Abstract

En esta tesis construiremos un algoritmo de descomposición asociado a un problema de optimización convexa separable con restricciones lineales, en particular lo aplicaremos a problemas de programación lineal. Este algoritmo aprovecha la estructura separable de la función objetivo del problema original considerando en cada iteración subproblemas de optimización para cada componente de la función objetivo, siendo estas de menor tamaño que el problema original e independientes entre sí, lo cual permite resolverlos de forma paralela, disminuyendo el costo computacional.

In this thesis, we will construct a decomposition algorithm associated with a separable convex optimization problem with linear constraints, particularly applying it to linear programming problems. This algorithm takes advantage of the separable structure of the objective function of the original problem by considering optimization subproblems for each component of the objective function at each iteration. These subproblems are smaller in size than the original problem and are independent of each other, which allows solving them in parallel, decreasing the computational cost.