(434b) Diffusing-Horizon Model Predictive Control

There is a growing need for model predictive control (MPC) formulations that can span multiple timescales [1,2,3]. For example, in energy system applications, it is often desired to make planing decisions over months while handling high-frequency disturbances occurring at the time scale of seconds. Under this setting, one may face tractability issues due to the need to use MPC formulation with fine time discretization grids and/or long horizons.

One way to resolve such a tractability issue is to use time-coarsening techniques. Time coarsening constructs an approximate representation of the original MPC problem by using a grid with sparse resolution. The resultant coarse problem has a reduced number of variables and constraints, thus it can be solved in a shorter time. This approach is inspired by the multi-grid method, which has been primarily used for the solution of discretized partial differential equations [4]. The multi-grid scheme applies the so-called algebraic coarsening scheme to the discretized time points to formulate a coarse representation of the original problem [5]. Interestingly, the same idea can be applied to structured optimization problems, such as model predictive control problems [6,7]. In particular, one can aggregate variables and constraints to formulate a coarse problem where the number of variables and constraints is reduced. The move-blocking MPC strategy reported in [8,9] can be regarded as a special case of algebraic coarsening strategy (this aggregates controls but not states).

In this work, we propose a new time-coarsening strategy that we call diffusing-horizon MPC [10]. The key design feature of this strategy is that the grid becomes exponentially sparser as moving forward in time. This particular coarse grid is designed to exploit the fact that in receding horizon control, one does not need to maintain the overall quality of the solution, but one only needs to maintain the quality of the solution at the first time step (the control action implemented in the actual system). A recently established property of optimal control problems, which is known as exponential decay of sensitivity (EDS) [10,11,12,13], states that the effect of parametric perturbations at a future time decays exponentially as one moves backward in time. In other words, the information in the far future has a negligible impact on the implemented control action. Using this property, we show that the coarsening applied to the far future has a negligible impact on the decision in the first step. Therefore, an effective trade-off between the quality of the solution and the tractability of the problem can be achieved. We show the effectiveness of diffusing-horizon MPC by conducting a case study for a heating, ventilation, and air conditioning plant that appears in [14]. We show that computational times can be decreased by two orders of magnitude while increasing the optimal closed-loop cost by only 3%.

Reference:
[1] Baldea, Michael, and Prodromos Daoutidis. "Control of integrated process networks—A multi-time scale perspective." Computers & chemical engineering 31.5-6 (2007): 426-444.
[2] Barrows, Clayton, et al. Time domain partitioning of electricity production cost simulations. No. NREL/TP-6A20-60969. National Renewable Energy Lab.(NREL), Golden, CO (United States), 2014.
[3] Dowling, Alexander W., Ranjeet Kumar, and Victor M. Zavala. "A multi-scale optimization framework for electricity market participation." Applied Energy 190 (2017): 147-164.
[4] Borzì, Alfio, and Volker Schulz. "Multigrid methods for PDE optimization." SIAM review 51.2 (2009): 361-395.
[5] Brandt, Achi. "General highly accurate algebraic coarsening." Electronic Transactions on Numerical Analysis 10.1 (2000): 21.
[6] Zavala, Victor M. "New architectures for hierarchical predictive control." IFAC-PapersOnLine 49.7 (2016): 43-48.
[7] Shin, Sungho, and Victor M. Zavala. "Multi-grid schemes for multi-scale coordination of energy systems." Energy Markets and Responsive Grids. Springer, New York, NY, 2018. 195-222.
[8] Cagienard, Raphael, et al. "Move blocking strategies in receding horizon control." Journal of Process Control 17.6 (2007): 563-570.
[9] Gondhalekar, Ravi, and Jun-ichi Imura. "Least-restrictive move-blocking model predictive control." Automatica 46.7 (2010): 1234-1240.
[10] Shin, Sungho, and Victor M. Zavala. "Diffusing-Horizon Model Predictive Control." arXiv preprint arXiv:2002.08556 (2020).
[11] Xu, Wanting, and Mihai Anitescu. "Exponentially accurate temporal decomposition for long-horizon linear-quadratic dynamic optimization." SIAM Journal on Optimization 28.3 (2018): 2541-2573.
[12] Shin, Sungho, et al. "A parallel decomposition scheme for solving long-horizon optimal control problems." 58th IEEE Conference on Decision and control. IEEE, 2019.
[13] Na, Sen, and Mihai Anitescu. "Exponential Decay in the Sensitivity Analysis of Nonlinear Dynamic Programming." arXiv preprint arXiv:1912.06734 (2019).
[14] Kumar, Ranjeet, et al. "Stochastic Model Predictive Control for Central HVAC Plants." arXiv preprint arXiv:2002.10065 (2020).