×

On the structure of the set of active sets in constrained linear quadratic regulation. (English) Zbl 1429.93097

Summary: The constrained linear quadratic regulation problem is solved by a continuous piecewise affine function on a set of state space polytopes. It is an obvious question whether this solution can be built up iteratively by increasing the horizon, i.e., by extending the classical backward dynamic programming solution for the unconstrained case to the constrained case. Unfortunately, however, the piecewise affine solution for horizon \(N\) is in general not contained in the piecewise affine law for horizon \(N+1\). We show that backward dynamic programming does, in contrast, result in a useful structure for the set of the active sets that defines the solution. Essentially, every active set for the problem with horizon \(N+1\) results from extending an active set for horizon \(N\), if the constraints are ordered stage by stage. Consequently, the set for horizon \(N+1\) can be found by only considering the constraints of the additional stage. Furthermore, it is easy to detect which polytopes and affine pieces are invariant to increasing the horizon, and therefore persist in the limit \(N\rightarrow\infty\). Several other aspects of the structure of the set of active sets become evident if the active sets are represented by bit tuples. There exists, for example, a subset of special active sets that generates a positive invariant and persistent (i.e., horizon-invariant) set around the origin. It is very simple to identify these special active sets, and the positive invariant and persistent region can be found without solving optimal control or auxiliary optimization problems. The paper briefly discusses the use of these results in model predictive control. Some opportunities for uses in computational methods are also briefly summarized.

MSC:

93B45 Model predictive control
49N10 Linear-quadratic optimal control problems
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anderson, B. D.O.; Moore, J. B., Linear optimal control (1971), Prentice-Hall, Inc. Englewood Cliffs: Prentice-Hall, Inc. Englewood Cliffs New Jersey · Zbl 0321.49001
[2] Bakaráč, P., Kalúz, M., Klaučo, M., Löfberg, J., & Kvasnica, M. (2018). Explicit MPC based on approximate dynamic programming. In Proc. 2018 European control conf.; Bakaráč, P., Kalúz, M., Klaučo, M., Löfberg, J., & Kvasnica, M. (2018). Explicit MPC based on approximate dynamic programming. In Proc. 2018 European control conf.
[3] Bazaraa, M. S.; Sherali, H. D.; Shetty, C. M., Nonlinear programming: Theory and algorithms (2006), Wiley-Interscience · Zbl 1140.90040
[4] Bemporad, A.; Morari, M.; Dua, V.; Pistikopoulos, E. N., The explicit linear quadratic regulator for constrained systems, Automatica, 38, 1, 3-20 (2002) · Zbl 0999.93018
[5] Bemporad, A.; Ricker, N. L.; Morari, M., Model predictive control toolbox user’s guide (2018), The Mathworks Inc.
[6] Bertsekas, D. P., Dynamic programming and optimal control (2005), Athena Scientific · Zbl 1125.90056
[7] Chmielewski, D.; Manousiouthakis, V., On constrained infinite-horizon linear quadratic optimal control, Systems & Control Letters, 121-129 (1996) · Zbl 0867.49025
[8] Feller, C.; Johansen, T. A.; Olaru, S., An improved algorithm for combinatorial multi-parametric quadratic programming, Automatica, 45, 5, 1370-1376 (2013) · Zbl 1319.90048
[9] Gilbert, E. G.; Tan, K. T., Linear systems with state and control constraints: The theory and application of maximal output admissible sets, IEEE Transactions on Automatic Control, 36, 9, 1008-1020 (1991) · Zbl 0754.93030
[10] Gupta, A.; Bhartiya, S.; Nataraj, P. S.V., A novel approach to multiparametric quadratic programming, Automatica, 47, 9, 2112-2117 (2011) · Zbl 1279.90169
[11] Gutman, P.-O.; Cwikel, M., An algorithm to find maximal state constraint sets for discrete-time linear dynamical systems with controls and states, IEEE Transactions on Automatic Control, 32, 3, 251-254 (1987) · Zbl 0618.49017
[12] Herceg, M.; Jones, C. N.; Kvasnica, M.; Morari, M., Enumeration-based approach to solving parametric linear complementarity problems, Automatica, 62, 243-248 (2015) · Zbl 1330.93089
[13] Herceg, M., Kvasnica, M., Jones, C. N., & Morari, M. (2013). Multi-parametric toolbox 3.0. In Proc. 2013 European Control Conference; Herceg, M., Kvasnica, M., Jones, C. N., & Morari, M. (2013). Multi-parametric toolbox 3.0. In Proc. 2013 European Control Conference
[14] Malanowski, K., Stability of solutions to convex problems of optimization (1987), Springer · Zbl 0697.49024
[15] Mayne, D. Q., & Raković, S. (2002). Optimal control of constrained piecewise affine discrete time systems using reverse transformation. In Proc. 41st IEEE Conf. on Decision and Control; Mayne, D. Q., & Raković, S. (2002). Optimal control of constrained piecewise affine discrete time systems using reverse transformation. In Proc. 41st IEEE Conf. on Decision and Control
[16] Oberdieck, R.; Diangelakis, N. A.; Pistikopoulos, E. N., Explicit model predictive control: A connected-graph approach, Automatica, 76, 103-112 (2017) · Zbl 1352.93043
[17] Muñoz de la Peña, D., Alamo, T., Bemporad, A., & Camacho, E. F. (2004). A dynamic programming approach for determining the explicit solution of linear MPC controllers. In Proc. 43rd IEEE Conf. on Decision and Control; Muñoz de la Peña, D., Alamo, T., Bemporad, A., & Camacho, E. F. (2004). A dynamic programming approach for determining the explicit solution of linear MPC controllers. In Proc. 43rd IEEE Conf. on Decision and Control
[18] Schulze Darup, M., & Cannon, M. (2016). Some observations on the activity of terminal constraints in linear MPC. In Proc. 2016 European Control Conf.; Schulze Darup, M., & Cannon, M. (2016). Some observations on the activity of terminal constraints in linear MPC. In Proc. 2016 European Control Conf.
[19] Seron, M., Goodwin, G. C., & DeDona, J. A. (2000). Finitely parametrised implementation of receding horizon control for constrained linear systems. In Proc. 2002 American Control Conf.; Seron, M., Goodwin, G. C., & DeDona, J. A. (2000). Finitely parametrised implementation of receding horizon control for constrained linear systems. In Proc. 2002 American Control Conf.
[20] Sznaier, M., & Damborg, M. J. (1987). Suboptimal control of linear systems with state and control inequality constraints. In Proc. 26th Conf. on Decision and Control; Sznaier, M., & Damborg, M. J. (1987). Suboptimal control of linear systems with state and control inequality constraints. In Proc. 26th Conf. on Decision and Control
[21] Tøndel, P.; Johansen, T. A.; Bemporad, A., An algorithm for multi-parametric quadratic programming and explicit MPC solutions, Automatica, 39, 3, 489-497 (2003) · Zbl 1019.93019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.