Department of Mathematics, University of Manchester
Tuesday, October 18, 2022, 11:00 - 11:45
Room 01-012, Georges-Köhler-Allee 102, Freiburg 79110, Germany
First-order optimization solvers, such as the Fast Gradient Method (FGM), are increasingly being used to solve Model Predictive Control (MPC) problems in resource-constrained environments where the computation time and available power are limited. Unfortunately, these implementations face two major issues: a poor convergence rate with illconditioned problem data, and instability/non-convergence when implemented using reduced precision data-types. In this work, we exploit the block Toeplitz structure of the MPC problem's matrices to derive two results that are independent of the length of the prediction horizon: a preconditioner and data-type sizing rules that ensure stability. Horizon-independence allows one to use only the predicted system and cost matrices to compute the preconditioner and data-type sizes, instead of the full Hessian. The proposed preconditioner has equivalent performance to an optimal preconditioner in numerical examples, producing speed-ups between 2x and 9x for the Fast Gradient Method, but is computable in closed-form and without the need to solve large semi-definite optimization problems. We propose a metric for measuring the amount of round-off error the FGM iteration can tolerate before becoming unstable, and then combine that metric with a round-off error model derived from the block Toeplitz Hessian structure to derive a method for computing the minimum number of fractional bits needed for an implementation of the FGM using a fixed-point data type. This new design rule nearly halves the number of fractional bits needed to implement an example problem, and results in significant decreases in resource usage, computational energy and execution time for an implementation on a Field Programmable Gate Array. Finally, we derive horizon-independent spectral bounds for the Hessian in terms of the transfer function of the predicted system, and show how these can be used to compute a novel horizon-independent bound on the condition number for the preconditioned Hessian.
Also online via Zoom:
Meeting ID: 627 9173 7415