qpBAMM: a parallelizable ADMM approach for block-structured quadratic programs

Block-structured quadratic programs (QPs) frequently arise in the context of the direct approach to solving optimal control problems. For successful application of direct optimal control algorithms to many real-world problems it is paramount that these QPs can be solved efficiently and reliably. Besides interior-point methods and active-set methods, ADMM-based quadratic programming approaches have gained popularity. Existing ADMM-based QP solvers typically split the problem into an equality-constrained QP and a projection problem onto, for example, a box-shaped feasible region. While this is a proven and widely used method, splitting the optimal control QP in this way does not easily allow to utilize and exploit the block structure of optimal control QPs to the fullest extent. In this paper, we address this situation by splitting the QP into a box-constrained QP, and a projection onto the linearized dynamics. Restricting the QP constraint set to a box, the solution becomes possible through an embarrassingly parallel gradient projection method. The projection step can be parallelized only partially, but benefits from the invariance of the constraint set to be projected on. With the proposed splitting, we are hence able to utilize the optimal control block structure, and solve relevant parts of the problem in parallel. We offer an implementation in Julia, present numerical results on random problems as well as on a popular benchmark problem, and demonstrate significant advantages over four recent Augmented Lagrangian method based solvers when applied to instances of optimal control problems with many state variables.

Article

Download

View PDF