(359c) An Efficient Distributed Algorithm for Multistage Scenario Model Predictive Control Using Primal Decomposition

Model predictive control is a mature and widely used optimal control strategy in many applications. Research on model predictive control (MPC) under uncertainty has been steadily gaining more interest and several forms of robust and stochastic MPC formulations have been studied in the control literature, which optimizes a single open-loop control trajectory that optimize over all possible realizations of the uncertainty. This can lead to overly conservative solution. As noted by the authors in [1] a better strategy would be to optimize over different control trajectories rather than a single control trajectory. One such approach is the multistage scenario model predictive control, also widely known as feedback min-max MPC or robust multistage MPC.

In multistage scenario MPC, the uncertainty is sampled into finite number of discrete realizations and the future propagation of the uncertainty in the prediction horizon is represented via a scenario tree. By allowing the control trajectories to vary for each scenario, we explicitly take into account the notion of feedback. In order to capture the real time decision-making process accurately, the so-called non-anticipativity constraints must be enforced which says that the control input leading to any branching must be the same. Consequently, the control input at the first sample must be the same for all the scenarios, thus enabling closed-loop implementation [1].

However, the major challenge with multistage scenario MPC is that it leads to large optimization problems and hence computationally demanding. Since the different scenarios are all independent except for the non-anticipativity constraints, which couples the different scenarios, one can easily decompose the scenario MPC problem into smaller problems and use a master problem to co-ordinate the different subproblems. Scenario decomposition using dual decomposition was proposed in [2] and [3]. Dual decomposition (also known as Lagrangian decomposition) method solves the subproblems by relaxing the coupling constraints. A master problem then co-ordinates the individual subproblems iteratively. The previously relaxed non-anticipativity constraints are feasible only upon convergence. The authors in [3] indicate that such methods require a relatively large number of iterations between the master problem and the subproblem to converge, leading to challenges with practical implementation.

The risk of dual decomposition is then that the master problem may not converge within the required time. This leads to infeasibility of the non-anticipativity constraints, the implications of which are that the different subproblems may give different control inputs at the first sample time in the prediction horizon. This is not acceptable for real-time closed-loop implementation. Therefore, we propose an alternative approach to scenario decomposition using the primal decomposition approach, which ensures the non-anticipativity constraints are always feasible. This is because, in contrast to dual decomposition, primal decomposition produces a primal feasible solution with monotonically decreasing objective value at each iteration [4]. In addition, we also present a novel backtracking algorithm to suitably choose the step-size of the master problem update.

Since the different scenarios differs only in the uncertain parameters, the distributed scenario MPC problem can be recast as a parameteric NLP problem. By exploiting the NLP sensitivities, we only need to solve one subproblem as a full NLP. The remaining subproblems can be solved using the path-following predictor corrector QP algorithm that approximates the NLP [5]. This results in a computationally efficient formulation of the distributed scenario MPC framework. Simulation results using a CSTR case study show that the sensitivity-based distributed scenario MPC provides very good approximation of the fully centralized scenario MPC and the full NLP distributed scenario MPC.

References

1. Scokaert P.O, Mayne D.Q. Min-max feedback model predictive control for constrained linear systems. IEEE Transactions on Automatic control. 1998 Aug;43(8):1136-42.
2. Lucia, S. Subramanian, and S. Engell, “Non-conservative robust nonlinear model predictive control via scenario decomposition,” in Control Applications (CCA), 2013 IEEE International Conference on. IEEE, 2013, pp. 586–591.
3. Marti, S. Lucia, D. Sarabia, R. Paulen, S. Engell, and C. de Prada, “Improving scenario decomposition algorithms for robust nonlin-ear model predictive control,” Computers & Chemical Engineering, vol. 79, pp. 30–45, 2015.
4. P. Bertsekas, Nonlinear programming. Athena Scientific, 1999.
5. Kungurtsev and J. Jaschke, “A predictor-corrector path-following al-gorithm for dual-degenerate parametric optimization problems,” SIAM Journal on Optimization, vol. 27, no. 1, pp. 538–564, 2017.