(564h) Multi-Grid Schemes for Multi-Scale Predictive Control

Our study analyzes Gauss-Seidel schemes and we study how information can be propagated through distant subsystems by exchanging state and dual information. For strictly convex quadratic programs, we establish conditions under which the Gauss-Seidel scheme is guaranteed to converge to the optimal central solution. In particular, we prove that the convergence rate is exponential in the number of iterations. Our work is motivated by a number of applications that involve multiple spatial and temporal scales. In these applications, partitioning on the entire domain can be nontrivial, because the coupling structure can be irregular (e.g., as in power grids). We show that our analysis framework is general and can be applied to these types of problems with arbitrary structures. The analysis reveals that the coupling structure between subsystems significantly affects the convergence and we show that our established conditions can be used to identify what is the most suitable partitioned structure. Our analysis also reveals that convergence is preserved when different coordination orders are used, indicating that we can derive coordination orders to maximize the computational scalability. For instance, a red-black coordination order enables parallel computation. 

We also show that one can use a low-resolution centralized control formulation (i.e., defined over a coarser mesh) to aid the convergence of the decentralized Gauss-Seidel scheme [7]. We argue that this multi-grid strategy can be seen as a hierarchical MPC structure, in which a low-resolution supervisory controller mitigates low-frequency (global) disturbances and oversees a set of high-resolution decentralized MPC controllers that mitigate high-frequency (local) disturbances. We demonstrate the performance of this hierarchical MPC architecture using an inventory management problem that is operated over multiple temporal scales and using a power grid problem that covers a 2-D spatial domain. We believe that the results have particular significance on the application of MPC for systems with multiple scales, as they allow for the systematic design of hierarchical control structures.