Multiparametric Dynamic Programming – Recent Advances and Future Challenges

Dynamic programming is a well-known and powerful paradigm for the solution of multi-stage processes. It relies on Bellman's optimality principle, which states that the optimal solution to a multi-stage optimization problem can be obtained by solving each stage recursively to optimality [1]. In particular, dynamic programming has been combined with multiparametric programming (mp-P) and was employed in explicit model-predictive control (MPC), where the MPC problem is solved explicitly offline as a function of the states.

In this work, we examine the current state-of-the-art of mp-DP algorithms. In particular, we show how all approaches presented in the literature can be categorized into direct and indirect mp-DP algorithms [2, 3]. In indirect mp-DP algorithms, one mp-P problem is solved per stage, however at each stage an additional parameter is added to the problem formulation in order to deal with the presence of nonconvexity. Hence when considering larger horizons, this procedure results in a computationally prohibitive effort. Conversely, direct mp-DP algorithms do not increase the problem size as a function of the horizon, as they directly use the principles of dynamic programming in mp-P. Using benchmark test sets, we show that current direct mp-DP algorithms are computationally attractive for hybrid systems, but are significantly outperformed by concatenation-based approaches for continuous systems. The key reasons for this are that (a) n mp-P problems need to be solved per stage, where n is the number of critical regions of the previous stage, and (b) each stage requires the comparison of n parametric profiles, which results in a significant computational burden.

Based on these considerations we propose a novel mp-DP algorithm for continuous linear state-space systems which does not require a comparison procedure while maintaining a constant problem size regardless of the horizon considered. It is based on the concept of direct mp-DP algorithms, which directly substitute the solution of the previous stage. Specifically, the optimal objective function of the previous stage is added to the objective function of currently considered stage. As this function is different for different critical regions of the parameter space, direct mp-DP algorithms require the solution of n mp-P problems.

However, it is well-known in multiparametric programming, that the optimal objective function value of explicit control problems with linear or convex quadratic cost function is convex [4]. Additionally, it was shown in the context of robust explicit control that it is possible to formulate convex piecewise functions as a single variable subject to constraints based on these function [5]. Hence, in this contribution we formulate the stage-wise mp-P using this property, which eliminates the need to formulate and solve n mp-P problems and compare their solutions. While this is indeed applicable to any convex, piecewise function, we specifically consider convex, piecewise affine objective functions as they result in a set of linear constraints which can be handled with existing solvers. Numerical examples are used to highlight the computational improvements over existing mp-DP algorithms, and its performance is compared to concatenation-based approaches.

Based on this result, we investigate new research directions in mp-DP including (a) applicability of mp-DP algorithms to the control of hybrid systems with long horizons, (b) combination of mp-DP algorithms with robust optimization and (c) computational gains in certain classes of problems involving specific characteristics such as path constraints which can be handled well using mp-DP algorithms

As an illustration, we compare the capabilities of mp-DP algorithm with concatenation-based approaches for the case of a cogeneration of heat and power (CHP) system [6]. The CHP is characterised by collaborative interactions between a power generation subsystem and a heat recovery subsystem. The control principles for the former are reduced to the manipulation of the air and gas intake in order to cover the electrical power demand. The feasible operation of the system is taken into account by formulating a model predictive controller with a single input and a single output system. This results in the presence of path constraints within the control problem formulation, which can be dealt with seamlessly using mp-DP. Numerical results will be shown and their implications will be discussed.

References

1.            Bellman, R., Dynamic programming. Dover ed ed. 2003, Mineola, N.Y: Dover Publications.

2.            Faísca, N.P., et al., A multi-parametric programming approach for constrained dynamic programming problems. Optimization Letters, 2008. 2(2): p. 267–280.

3.            Borrelli, F., et al., Dynamic programming for constrained optimal control of discrete-time linear hybrid systems. Automatica, 2005. 41(10): p. 1709–1721.

4.            Bemporad, A., et al., The explicit linear quadratic regulator for constrained systems. Automatica, 2002. 38(1): p. 3–20.

5.            Bemporad, A., F. Borrelli, and M. Morari, Robust Model Predictive Control: Piecewise Linear Explicit Solution, in European Control Conference. 2001: Porto, Portugal. p. 939–944.

6.            Diangelakis, N.A., A.M. Manthanwar, and E.N. Pistikopoulos, A Framework for Design and Control Optimisation: Application on a CHP System, in Proceedings of the 8th International Conference on Foundations of Computer-Aided Process Design, 2014, Elsevier. p. 765–770.