GPU Acceleration of ADMM for Large-Scale Convex Optimization

Abstract

Large-scale convex optimization problems arise in various practical applications. Even though there exist many ecient methods for solving these problems, such as the alternating direction method of multipliers (ADMM), they may take minutes or even hours to compute solutions of very large problem instances. In this thesis we explore the possibilities of using a graphics processing unit (GPU) to accelerate ADMM. We use OSQP as a state-of-the-art implementation of ADMM to analyze the potential to parallelize the algorithm. We identify several parts of the implementation that could be accelerated by using a GPU, such as the direct linear system solver, which we replace with an iterative conjugate gradient (CG) method implemented on a GPU. Our implementation written in CUDA C has been tested on many medium- to large-scale problems in applications ranging from engineering to statistics and nance. The GPU-accelerated algorithm outperforms OSQP by up to 2 orders of magnitude for problems that take more than 15 minutes to solve by the standard OSQP implementation.