SOLVING QUADRATIC PROGRAMMING PROBLEMS ON GRAPHICS PROCESSING UNIT

Abstract

Quadratic Programming (QP) problems frequently appear as core component when solving constrained optimal control or estimation problems. The focus of this paper is on accelerating an existing Interior Point Method (IPM) for solving QP problems by exploiting the parallel computing characteristics of GPU. We compare the so-called data-parallel and the problem-parallel approaches to achieve speed up for solving QP problems. The data-parallel approach achieves speed up by parallelizing the vector and matrix computations such as the dot-product, while the problem-parallel approach solves multiple QP problems in parallel using one GPU. Our results show that solving several QP problems in parallel could lead to better utilization of the GPU resources. This problemparallel approach is well-suited for implementing a new type of Model Predictive Control algorithm characterized by solving multiple copies of MPC in parallel to improve closedloop performance.