TR2018-118

An Alternating Direction Method of Multipliers Algorithm for Symmetric MPC



This paper presents an alternating-direction method of multipliers (admm) algorithm for solving large-scale symmetric model predictive control (mpc) problems in real-time on embedded computers with limited computational and memory resources. Symmetry was used to find transformations of the states, inputs, and constraints of the mpc problem that decompose the dynamics and cost. We prove a key-property of the symmetric group that allows us to efficiently transform between the original and decomposed symmetric domains. This allows us to solve different sub-problems of a baseline admm algorithm in different domains where the computations are less expensive. This reduces the computational cost of each iteration from quadratic in problem size to linear. In addition, we show that our admm algorithm requires a constant amount of memory regardless of the problem size. We demonstrate our algorithm for a battery balancing problem which results in a reduction of computation-times from hours to seconds and a reduction in memory from hundreds of megabytes to tens of kilobytes.