Certificates

We are aware of an issue with certificate availability and are working diligently with the vendor to resolve. The vendor has indicated that, while users are unable to directly access their certificates, results are still being stored. Certificates will be available once the issue is resolved. Thank you for your patience.

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

Authors: 
Shin, S., University of Wisconsin-Madison
Zavala, V. M., University of Wisconsin-Madison
We propose to use multi-grid computing schemes to design multi-scale model predictive control (MPC) architectures. This is motivated by the fact that the presence of multiple spatial and temporal scales makes centralized MPC intractable [1]. Decentralized control schemes seek to mitigate this complexity by solving problems over individual subdomains [1,2]. Achieving central optimality in these schemes is important because desirable properties of centralized MPC such as recursive feasibility, stability, and robustness can be inherited [2]. Diverse decentralized coordination schemes such as Gauss-Seidel [3], Lagrangian dual decomposition [4], or alternating direction multipliers [5,6] have been proposed in the past. However, complex coupling between subsystems can make coordination of decentralized controllers quite slow. 
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. 
Reference:
[1] R. Scattolini. Architectures for distributed and hierarchical model predictive control–a review.
Journal of Process Control, 19(5):723–731, 2009.
[2] J. B. Rawllings and D. Mayne. Model predictive control: theory and design. Nob Hill Publishing, 2009. 
[3] Zavala, V. M.. New Architectures for Hierarchical Predictive Control. IFAC-PapersOnLine, 49(7), 43–48. 2016. 
[4] 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.
[5] R. T. Rockafellar. Augmented lagrange multiplier functions and duality in nonconvex programming.
SIAM Journal on Control, 12(2):268–285, 1974.
[6] 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.
[7] W. Hackbusch, Multi-grid methods and applications. Springer Series in Computational Mathematics, 1985.