An alternating direction method of multipliers algorithm for symmetric model predictive control

This article presents an alternating direction method of multipliers (ADMM) algorithm for solving large-scale model predictive control (MPC) problems that are invariant under the symmetric-group. Symmetry was used to find transformations of the inputs, states, and constraints of the MPC problem that decompose the dynamics and cost. We prove an important property of the symmetric decomposition for the symmetric-group that allows us to efficiently transform between the original and decomposed symmetric domains. This allows us to solve different subproblems of a baseline ADMM algorithm in different domains where the computations are less expensive. This reduces the computational cost of each iteration from quadratic to linear in the number of repetitions in the system. In addition, we show that the memory complexity for our ADMM algorithm is also linear in number of repetitions in the system, rather than the typical quadratic complexity. We demonstrate our algorithm for two case studies; battery balancing and heating, ventilation, and air conditioning. In both case studies, the symmetric algorithm reduced the computation-time from minutes to seconds and memory usage from tens of megabytes to tens or hundreds of kilobytes, allowing the previously nonviable MPCs to be implemented in real time on embedded computers with limited computational and memory resources.

Automated summary

This article presents an ADMM algorithm for solving large-scale MPC problems, reducing computational cost and memory usage through symmetry decomposition. In practical case studies, the symmetric algorithm significantly reduced computation time and memory usage, enabling previously unviable MPCs to run in real time on resource-limited embedded computers.