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 . 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.
Â R. Scattolini. Architectures for distributed and hierarchical model predictive controlâa review.
Journal of Process Control, 19(5):723â731, 2009.
Â J. B. Rawllings and D. Mayne.Â Model predictive control: theory and design. Nob Hill Publishing,Â 2009.Â
Â Zavala, V. M.. New Architectures for Hierarchical Predictive Control.Â IFAC-PapersOnLine,Â 49(7), 43â48.Â 2016.Â
Â Q. T. Dinh, C. Savorgnan, and M. Diehl. Combining lagrangian decomposition and excessive gap
smoothing technique for solving large-scale separable convex optimization problems. Computational
Optimization and Applications, 55(1):75â111, 2013.
Â R. T. Rockafellar. Augmented lagrange multiplier functions and duality in nonconvex programming.
SIAM Journal on Control, 12(2):268â285, 1974.
 Summers, T. H., & Lygeros, J. (2012). Distributed model predictive consensus via the Alternating Direction Method of Multipliers.Â 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), (1), 79â84.
 W. Hackbusch, Multi-grid methods and applications. Springer Series in Computational Mathematics, 1985.