(629h) A Multi-Parametric Programming Approach for Dynamic Programming & Robust Control

Dynamic Programming is well-documented (Bellman, 2003; Bertsekas, 2005) as being a powerful tool to solve multi-stage decision problems. Based on the optimality principle, the original problem disassembles into a set of small dimension problems. This strategy has been successfully applied to numerous problems, however, the presence of hard constraints is an obstacle. Presence of hard constraints implies non-linear decisions with respect to the present state, which is why the conventional implementation of the dynamic programming procedure would require the solution of global optimisation algorithms. Furthermore, the presence of uncertainty in the dynamic model of the problem imposes further challenges for the solution of the dynamic programming problem. Although some researchers have tackled this problem (see Borrelli et al, 2005), it is an open research topic.

In the present work, a new algorithm is proposed to solve the convex multi-stage problem with hard constraints based on dynamic programming and parametric programming procedures. Each echelon of the dynamic programming procedure is interpreted as a multi-parametric optimisation problem (Dua and Pistikopoulos, 2000; Dua et al., 2002), with the parameters being the states at the current stage and future optimisation (control) variables. Preserving the dynamic recursive procedure, the dimension of the optimisation problem is reduced to a set of sequential lower dimensional multiparametric programming problems, constrained by fewer inequalities; whereas the use of sensitivity analysis circumvents possible non-convexities. Therefore, the robust solution for convex multi-stage decision problems in the presence of uncertainties can be computed with this new algorithm with reduced complexity. The underlying mathematical theory is described and numerical examples are presented to illustrate the potential of the new approach.

References: Bellman, R. (2003), Dynamic Programming. Dover Publications, Mineola. Bemporad, A., Morari, M., Dua, V., Pistikopoulos E.N. (2002), Automatica, 38. Bertsekas, D.P. (2005), Dynamic Programming and Optimal Control. Academic Press, London. Borrelli, F., Baotic, M., Bemporad, A., Morari, M. (2005), Automatica, 41. Dua, V., Bozinis, A., and Pistikopoulos, E. N. (2002), Comp. & Chem. Eng., 26. Dua, V. and Pistikopoulos, E.N. (2000), Ann. of Op. Res., 99. Pistikopoulos, E.N., Dua, V., Bozinis, N., Bemporad, A., Morari, M. (2002), Comp. & Chem. Eng, 26.