GPU Acceleration of ADMM for Large-Scale Quadratic Programming

Abstract

The alternating direction method of multipliers (ADMM) is a powerful operator splitting technique for solving structured convex optimization problems. Due to its relatively low per-iteration computational cost and ability to exploit sparsity in the problem data, it is particularly suitable for large-scale optimization. However, the method may still take prohibitively long to compute solutions to very large problem instances. Although ADMM is known to be parallelizable, this feature is rarely exploited in real implementations. In this paper we exploit the parallel computing architecture of a graphics processing unit (GPU) to accelerate ADMM. We build our solver on top of OSQP, a state-of-the-art implementation of ADMM for quadratic programming. Our open-source CUDA C implementation has been tested on many large-scale problems and was shown to be up to two orders of magnitude faster than the CPU implementation.

References in corpus (5)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• TensorFlow: A system for large-scale machine learning
• OSQP: An Operator Splitting Solver for Quadratic Programs
• ADMM Penalty Parameter Selection by Residual Balancing
• Two-Dimensional Batch Linear Programming on the GPU

Cited by in corpus (5)

• MPCGPU: Real-Time Nonlinear Model Predictive Control through Preconditioned Conjugate Gradient on the GPU
• Leveraging GPU batching for scalable nonlinear programming through massive Lagrangian decomposition
• Exploiting GPU/SIMD Architectures for Solving Linear-Quadratic MPC Problems
• Parallel and Flexible Dynamic Programming via the Randomized Mini-Batch Operator
• Multi-Objective Agent-Based Model Predictive Controller for Plug-and-Play Vehicle Control