Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
The Essentials of Model Predictive Control Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Explicit (Offline) Optimization for MPC

verfasst von : Nikolaos A. Diangelakis, Richard Oberdieck, Efstratios N. Pistikopoulos

Erschienen in: Handbook of Model Predictive Control

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this chapter, we present the fundamentals of multi-parametric programming and its application to explicit model predictive control (MPC), i.e. the offline solution of MPC problems for both continuous and hybrid systems. In particular, we first show how MPC problems can be reformulated as multi-parametric programming problems, then we show how explicit/multi-parametric solutions are derived and the key underlying theoretical properties. Finally, we present solution procedures for these type of problems and discuss applicability issues and potential future research directions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Convexification and Real-Time Optimization for MPC with Aerospace Applications
Nächstes Kapitel Real-Time Implementation of Explicit Model Predictive Control
Fußnoten
1
Problem (10) can be viewed as a special case of problem (9) with Q = 0n×n and H = 0n×q, which is inherently positive semi-definite.
 
2
For an introduction into the concept of Lagrangian multipliers and duality in general, the reader is referred to the excellent textbook by C. A. Floudas [28].
 
3
Assuming no degeneracy, in the case of mp-LP problems, the cardinality of the active set k is \(\text{card}\left (k\right ) = n\) and thus the parametric solution is directly given as \(u\left (\theta \right ) = G_{k}^{-1}\left (W_{k} + S_{k}x\right )\).
 
4
In general, the term “parametric” refers to the case where a single parameter is considered, while “multi-parametric” suggests the presence of multiple parameters.
 
5
It is convex, if the following z-transformation is applied \(u = z -\frac{1} {2}H^{-1}Zx\), based on the nomenclature of problem (9).
 
6
In an excellent technical note from 2002, Baotić actually already commented on the connected graph nature of the problem, however without providing a formal proof or further discussion on the topic [7].
 
7
This does not consider problems arising from scaling, round-off computational errors or the presence of identical constraints in the problem formulation.
 
8
Consider Figure 1a: if the constraint which only coincides at the single point with the feasible space is chosen as part of the active set, the corresponding parametric solution will only be valid in that point.
 
9
A similar approach was presented in 2006 by Olaru and Dumur [56].
 
10
In other words: if k is infeasible, so is its powerset.
 
11
In the case of mp-MILP problems, the MINLP becomes a mixed-integer linear programming problem.
 
12
The limiting iteration number ρ limit is the maximum number of iterations performed on a single machine before the result is returned to the main algorithm.
 
13
Note that in the case of the envelopes of solutions approach to the mp-MIQP problem the critical regions are polytopes but a comparison procedure between alternative solutions is necessary.
 
14
Note that this claim refers mainly to alleviating the necessity of optimization hardware equipment for the application of optimization based MPC as the explicit solution enables the use of MPC-on-a-chip as described in [60].
 
15
If the sampling time of a system is 1μs, but the point location of the explicit MPC controller may require up to 5μs, the explicit MPC controller cannot be applied in practice.
 
Literatur
1.
Acevedo, J., Pistikopoulos, E.N.: A multiparametric programming approach for linear process engineering problems under uncertainty. Ind. Eng. Chem. Res. 36(3), 717–728 (1997)CrossRef
2.
Ahmadi-Moshkenani, P., Johansen, T.A., Olaru, S.B.: On degeneracy in exploration of combinatorial tree in multi-parametric quadratic programming. In: IEEE Conference on Decision and Control (2016)
3.
Ahmadi-Moshkenani, P., Olaru, S.B., Johansen, T.A.: Further results on the exploration of combinatorial tree in multi-parametric quadratic programming. In: Proceedings of the European Control Conference, pp. 116–122 (2016)
4.
Airan, A., Bhartiya, S., Bhushan, M.: Linear machine: a novel approach to point location problem. In: International Symposium on Dynamics and Control of Process Systems, pp. 445–450. IFAC, Oxford (2013)
5.
Airan, A., Bhushan, M., Bhartiya, S.: Linear machine solution to point location problem. IEEE Trans. Autom. Control 62(3), 1403–1410 (2016)MathSciNetCrossRef
6.
Axehill, D., Besselmann, T., Raimondo, D.M., Morari, M.: A parametric branch and bound approach to suboptimal explicit hybrid MPC. Automatica 50(1), 240–246 (2014)MathSciNetCrossRef
7.
Baotić, M.: An efficient algorithm for multi-parametric quadratic programming. Technical Report AUT02-04, Automatic Control Laboratory, ETH Zurich, Switzerland (February 2002)
8.
Baotic, M., Borrelli, F., Bemporad, A., Morari, M.: Efficient on-line computation of constrained optimal control. SIAM J. Control Optim. 47(5), 2470–2489 (2008)MathSciNetCrossRef
9.
Bayat, F., Johansen, T.A., Jalali, A.A.: Using hash tables to manage the time-storage complexity in a point location problem: application to explicit model predictive control. Automatica 47(3), 571–577 (2011)MathSciNetCrossRef
10.
Bayat, F., Johansen, T.A., Jalali, A.A.: Flexible piecewise function evaluation methods based on truncated binary search trees and lattice representation in explicit MPC. IEEE Trans. Control Syst. Technol. 20(3), 632–640 (2012)CrossRef
11.
Bazaraa, M.S.: Nonlinear Programming: Theory and Algorithms, 3rd edn. Wiley, Chichester (2013)
12.
Bemporad, A.: A multiparametric quadratic programming algorithm with polyhedral computations based on nonnegative least squares. IEEE Trans. Autom. Control 60(11), 2892–2903 (2015)MathSciNetCrossRef
13.
Bemporad, A., Morari, M.: Control of systems integrating logic, dynamics, and constraints. Automatica 35(3), 407–427 (1999)MathSciNetCrossRef
14.
Bemporad, A., Borrelli, F., Morari, M.: Model predictive control based on linear programming – the explicit solution. IEEE Trans. Autom. Control 47(12), 1974–1985 (2002)MathSciNetCrossRef
15.
Bemporad, A., Morari, M., Dua, V., Pistikopoulos, E.N.: The explicit linear quadratic regulator for constrained systems. Automatica 38(1), 3–20 (2002)MathSciNetCrossRef
16.
Borrelli, F., Baotic, M., Bemporad, A., Morari, M.: Efficient on-line computation of constrained optimal control. In: Conference on Decision and Control, vol. 2, pp. 1187–1192 (2001)MATH
17.
Borrelli, F., Bemporad, A., Morari, M.: Geometric algorithm for multiparametric linear programming. J. Optim. Theory Appl. 118(3), 515–540 (2003)MathSciNetCrossRef
18.
Borrelli, F., Baotić, M., Bemporad, A., Morari, M.: Dynamic programming for constrained optimal control of discrete-time linear hybrid systems. Automatica 41(10), 1709–1721 (2005)MathSciNetCrossRef
19.
Christophersen, F.J., Kvasnica, M., Jones, C.N., Morari, M.: Efficient evaluation of piecewise control laws defined over a large number of polyhedra. In: European Control Conference (2007)
20.
Columbano, S., Fukuda, K., Jones, C.N.: An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices. CRM Proc. Lect. Notes 48, 1–30 (2009)MathSciNetCrossRef
21.
Diangelakis, N.A., Avraamidou, S., Pistikopoulos, E.N.: Decentralized multiparametric model predictive control for domestic combined heat and power systems. Ind. Eng. Chem. Res. 55(12), 3313–3326 (2016)CrossRef
22.
Dua, V., Pistikopoulos, E.N.: Algorithms for the solution of multiparametric mixed-integer nonlinear optimization problems. Ind. Eng. Chem. Res. 38(10), 3976–3987 (1999)CrossRef
23.
Dua, V., Pistikopoulos, E.N.: An algorithm for the solution of multiparametric mixed integer linear programming problems. Ann. Oper. Res. 99(1–4), 123–139 (2000)MathSciNetCrossRef
24.
Dua, V., Bozinis, N.A., Pistikopoulos, E.N.: A multiparametric programming approach for mixed-integer quadratic engineering problems. Comput. Chem. Eng. 26(4–5), 715–733 (2002)CrossRef
25.
Feller, C., Johansen, T.A.: Explicit MPC of higher-order linear processes via combinatorial multi-parametric quadratic programming. In: 2013 European Control Conference (ECC), pp. 536–541 (2013)
26.
Feller, C., Johansen, T.A., Olaru, S.B.: An improved algorithm for combinatorial multi-parametric quadratic programming. Automatica 49(5), 1370–1376 (2013)MathSciNetCrossRef
27.
Fiacco, A.V.: Sensitivity analysis for nonlinear programming using penalty methods. Math. Program. 10(1), 287–311 (1976)MathSciNetCrossRef
28.
Floudas, C.A.: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Topics in Chemical Engineering. Oxford University Press, New York (1995)MATH
29.
Fuchs, A., Axehill, D., Morari, M.: On the choice of the linear decision functions for point location in polytopic data sets – application to explicit MPC. In: Conference on Decision and Control, pp. 5283–5288 (2010)
30.
Gál, T.: The historical development of parametric programming. In: Brosowski, B., Deutsch, F. (eds.) Parametric Optimization and Approximation. International Series of Numerical Mathematics/Internationale Schriftenreihe zur Numerischen Mathematik/Série internationale d’Analyse numérique, vol. 72, pp. 148–165. Birkhäuser, Basel (1985)
31.
Gál, T.: Postoptimal Analyses, Parametric Programming, and Related Topics: Degeneracy, Multicriteria Decision Making, Redundancy, 2nd edn. W. de Gruyter, Berlin (1995)
32.
33.
Grancharova, A., Johansen, T.A.: Approaches to explicit nonlinear model predictive control with reduced partition complexity. In: 2009 European Control Conference (ECC), pp. 2414–2419 (2009)
34.
Gupta, A., Bhartiya, S., Nataraj, P.S.V.: A novel approach to multiparametric quadratic programming. Automatica 47(9), 2112–2117 (2011)MathSciNetCrossRef
35.
Heemels, W.P.M.H., De Schutter, B., Bemporad, A.: Equivalence of hybrid dynamical models. Automatica 37(7), 1085–1091 (2001)CrossRef
36.
Herceg, M., Mariéthoz, S., Morari, M.: Evaluation of piecewise affine control law via graph traversal. In: European Control Conference, pp. 3083–3088 (2013)
37.
Herceg, M., Kvasnica, M., Jones, C.N., Morari, M.: Multi-parametric toolbox 3.0. In: 2013 European Control Conference (ECC), pp. 502–510 (2013)
38.
Herceg, M., Jones, C.N., Kvasnica, M., Morari, M.: Enumeration-based approach to solving parametric linear complementarity problems. Automatica 62, 243–248 (2015)MathSciNetCrossRef
39.
Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013)MATH
40.
Jafargholi, M., Peyrl, H., Zanarini, A., Herceg, M., Mariéthoz, S.: Accelerating space traversal methods for explicit model predictive control via space partitioning trees. In: European Control Conference, pp. 103–108 (2014)
41.
Johansen, T.A., Grancharova, A.: Approximate explicit constrained linear model predictive control via orthogonal search tree. IEEE Trans. Autom. Control 48(5), 810–815 (2003)MathSciNetCrossRef
42.
Jones, C.N., Morari, M.: Multiparametric linear complementarity problems. In: 2006 45th IEEE Conference on Decision and Control, pp. 5687–5692 (2006)
43.
Jones, C.N., Grieder, P., Raković, S.V.: A logarithmic-time solution to the point location problem for parametric linear programming. Automatica 42(12), 2215–2218 (2006)MathSciNetCrossRef
44.
Jones, C.N., Kerrigan, E.C., Maciejowski, J.M.: Lexicographic perturbation for multiparametric linear programming with applications to control. Automatica 43(10), 1808–1816 (2007)MathSciNetCrossRef
45.
Karush, W.: Minima of functions of several variables with inequalities as side constraints. Master’s thesis, Dept.˜of Mathematics, Univ.˜of Chicago (1939)
46.
Kuhn, H.W., Tucker, A.W.: Nonlinear programming. In: Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pp. 481–492. University of California Press, Berkeley (1951)
47.
Li, Z., Ierapetritou, M.G.: A method for solving the general parametric linear complementarity problem. Ann. Oper. Res. 181(1), 485–501 (2010)MathSciNetCrossRef
48.
Markowitz, H.: Portfolio selection. J. Financ. 7(1), 77–91 (1952)
49.
Martinez-Rodriguez, M.C., Brox, P., Baturone, I.: Digital VLSI implementation of piecewise-affine controllers based on lattice approach. IEEE Trans. Control Syst. Technol. 23(3), 842–854 (2015)CrossRef
50.
Monnigmann, M., Kastsian, M.: Fast explicit model predictive control with multiway trees. In: World Congress, IFAC proceedings volumes, pp. 1356–1361. IFAC/Elsevier, New York (2011)
51.
Monnigmann, M., Jost, M.: Vertex based calculation of explicit MPC laws. In: American Control Conference (ACC), pp. 423–428 (2012)
52.
Oberdieck, R., Pistikopoulos, E.N.: Parallel computing in multi-parametric programming. In: Kravanja, Z., Bogataj, M. (eds.) 26th European Symposium on Computer Aided Process Engineering, volume 38 of Computer Aided Chemical Engineering, pp. 169–174. Elsevier, Amsterdam (2016)
53.
Oberdieck, R., Wittmann-Hohlbein, M., Pistikopoulos, E.N.: A branch and bound method for the solution of multiparametric mixed integer linear programming problems. J. Glob. Optim. 59(2–3), 527–543 (2014)MathSciNetCrossRef
54.
Oberdieck, R., Diangelakis, N.A., Papathanasiou, M.M., Nascu, I., Pistikopoulos, E.N.: POP – parametric optimization toolbox. Ind. Eng. Chem. Res. 55(33), 8979–8991 (2016)CrossRef
55.
Oberdieck, R., Diangelakis, N.A., Pistikopoulos, E.N.: Explicit model predictive control: a connected-graph approach. Automatica 76, 103–112 (2017)MathSciNetCrossRef
56.
Olaru, S.B., Dumur, D.: On the continuity and complexity of control laws based on multiparametric linear programs. In: 2006 45th IEEE Conference on Decision and Control, pp. 5465–5470 (2006)
57.
Oliveri, A., Gianoglio, C., Ragusa, E., Storace, M.: Low-complexity digital architecture for solving the point location problem in explicit Model Predictive Control. J. Frankl. Inst. 352(6), 2249–2258 (2015)MathSciNetCrossRef
58.
Papathanasiou, M.M., Avraamidou, S., Steinebach, F., Oberdieck, R., Mueller-Spaeth, T., Morbidelli, M., Mantalaris, A., Pistikopoulos, E.N.: Advanced control strategies for the multicolumn countercurrent solvent gradient purification process (MCSGP). AIChE J. 62(7), 2341–2357 (2016)CrossRef
59.
Patrinos, P., Sarimveis, H.: A new algorithm for solving convex parametric quadratic programs based on graphical derivatives of solution mappings. Automatica 46(9), 1405–1418 (2010)MathSciNetCrossRef
60.
Pistikopoulos, E.N.: From multi-parametric programming theory to MPC-on-a-chip multi-scale systems applications. Comput. Chem. Eng. 47, 57–66 (2012)CrossRef
61.
Rawlings, J.B., Mayne, D.Q.: Model Predictive Control: Theory and Design. Nob Hill Pub., Madison (2009)
62.
Rockafellar, R.T.: Convex Analysis. Princeton Mathematical Series. Princeton University Press, Princeton (1970)CrossRef
63.
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Grundlehren der mathematischen Wissenschaften. Springer, Berlin (1998)
64.
Sakizlis, V.: Design of model based controllers via parametric programming. PhD thesis, Imperial College, London (2003)
65.
Sakizlis, V., Perkins, J.D., Pistikopoulos, E.N.: Explicit solutions to optimal control problems for constrained continuous-time linear systems. IEEE Proc. Control Theory Appl. 152(4), 443–452 (2005)CrossRef
66.
Spjøtvold, J., Tøndel, P., Johansen, T.A.: A method for obtaining continuous solutions to multiparametric linear programs. In: World Congress, IFAC proceedings volumes, p. 902. IFAC/Elsevier, New York (2005)
67.
Spjotvold, J., Rakovic, S.V., Tondel, P., Johansen, T.A.: Utilizing reachability analysis in point location problems. In: Conference on Decision and Control, pp. 4568–4569 (2006)
68.
Spjøtvold, J., Kerrigan, E.C., Jones, C.N., Tøndel, P., Johansen, T.A.: On the facet-to-facet property of solutions to convex parametric quadratic programs. Automatica 42(12), 2209–2214 (2006)MathSciNetCrossRef
69.
Spudic, V., Baotic, M.: Fast coordinated model predictive control of large-scale distributed systems with single coupling constraint. In: 2013 European Control Conference (ECC), pp. 2783–2788 (2013)
70.
Spudic, V., Jelavic, M., Baotic, M.: Explicit model predictive control for reduction of wind turbine structural loads. In: 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pp. 1721–1726 (2012)
71.
Sun, M., Chachuat, B., Pistikopoulos, E.N.: Design of multi-parametric NCO tracking controllers for linear dynamic systems. Comput. Chem. Eng. 92, 64–77 (2016)CrossRef
72.
Tøndel, P., Johansen, T.A., Bemporad, A.: Evaluation of piecewise affine control via binary search tree. Automatica 39(5), 945–950 (2003)MathSciNetCrossRef
73.
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)MathSciNetCrossRef
74.
Wang, Y., Jones, C., Maciejowski, J.: Efficient point location via subdivision walking with application to explicit MPC. In: European Control Conference (2007)
75.
Zhang, J., Xiu, X., Xie, Z., Hu, B.: Using a two-level structure to manage the point location problem in explicit model predictive control. Asian J. Control 18(3), 1075–1086 (2015)MathSciNetCrossRef
Metadaten
Titel
Explicit (Offline) Optimization for MPC
verfasst von
Nikolaos A. Diangelakis
Richard Oberdieck
Efstratios N. Pistikopoulos
Copyright-Jahr
2019
Buch
Handbook of Model Predictive Control

Print ISBN: 978-3-319-77488-6

Electronic ISBN: 978-3-319-77489-3

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-319-77489-3_16

Neuer Inhalt

    Bildnachweise