(60c) 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.