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.

**Extended Abstract:**File Not Uploaded

See more of this Group/Topical: Computing and Systems Technology Division