×

zbMATH — the first resource for mathematics

Recent advances in quadratic programming algorithms for nonlinear model predictive control. (English) Zbl 1416.90030
Summary: Over the past decades, the advantages of optimization-based control techniques over conventional controllers inspired developments that enabled the use of model predictive control (MPC) in applications with very high sampling rates. Since at the heart of most linear and nonlinear MPC controllers resides a quadratic programming (QP) solver, the implementation of efficient algorithms that exploit the underlying problem structure drew the attention of many researchers and the progress in the field has been remarkable. The aim of this paper is to summarize the main algorithmic advances in the field and to provide a consistent benchmark between a selection of software tools that have been recently developed. The code that was used for the simulations is publicly available for readers that wish to reproduce the results or test the benchmarked solvers on their own nonlinear MPC applications.
MSC:
90C20 Quadratic programming
49J20 Existence theories for optimal control problems involving partial differential equations
49M15 Newton-type methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersson, J.: A General-Purpose Software Framework for Dynamic Optimization. PhD thesis, KU Leuven, Leuven (2013)
[2] Axehill, D., Controlling the level of sparsity in MPC, Syst. Control Lett., 76, 1-7, (2015) · Zbl 1307.93151
[3] Axehill, D.; Morari, M., An alternative use of the Riccati recursion for efficient optimization, Syst. Control Lett., 61, 37-40, (2012) · Zbl 1250.93052
[4] Banjac, G., Stellato, B., Moehle, N., Goulart, P., Bemporad, A., Boyd, S.: Embedded code generation using the OSQP solver. In: Proceedings of the IEEE 56th Annual Conference on Decision and Control (CDC). Melboume, Australia (2017)
[5] Bartlettand, RA; Biegler, LT, QPSChur: A dual, active-set, Schur-complement method for large-scale and structured convex quadratic programming algorithm, Optim. Eng., 7, 5-32, (2006) · Zbl 1167.90615
[6] Bemporad, A., Borrelli, F., Morari, M.: The explicit solution of constrained LP-based receding horizon control. In: Proceedings of the 39th IEEE Conference on Decision and Control (CDC). Sydney, Australia (1999)
[7] Bertsekas, DP, Projected Newton methods for optimization problems with simple constraints. SIAM, J. Control Optim., 20, 221-246, (1982) · Zbl 0507.49018
[8] Biegler, LT, Solution of dynamic optimization problems by successive quadratic programming and orthogonal collocation, Comput. Chem. Eng., 8, 243-248, (1984)
[9] Bock, H. G., Recent Advances in Parameteridentification Techniques for O.D.E, 95-121, (1983), Boston, MA · Zbl 0516.65067
[10] Bock, Hans Georg; Diehl, Moritz; Kostina, Ekaterina; Schlöder, Johannes P., 1. Constrained Optimal Feedback Control of Systems Governed by Large Differential Algebraic Equations, 3-24, (2007) · Zbl 1248.93071
[11] Bock, H. G.; Plitt, K. J., A Multiple Shooting Algorithm for Direct Solution of Optimal Control Problems *, IFAC Proceedings Volumes, 17, 1603-1608, (1984)
[12] Cairano, S.; Brand, M.; Bortoff, SA, Projection-free parallel quadratic programming for linear model predictive control, Int. J. Control, 86, 1367-1385, (2013) · Zbl 1278.90291
[13] Diehl, M.; Amrit, R.; Rawlings, JB, A Lyapunov function for economic optimizing model predictive control, IEEE Trans. Autom. Control, 56, 703-707, (2011) · Zbl 1368.93340
[14] Diehl, M.; Bock, HG; Schlöder, JP, A real-time iteration scheme for nonlinear optimization in optimal feedback control, SIAM J. Control Optim., 43, 1714-1736, (2005) · Zbl 1078.65060
[15] Diehl, M.; Bock, HG; Schlöder, JP; Findeisen, R.; Nagy, Z.; Allgöwer, F., Real-time optimization and nonlinear model predictive control of processes governed by differential-algebraic equations, J. Process Control, 12, 577-585, (2002)
[16] Diehl, Moritz; Ferreau, Hans Joachim; Haverbeke, Niels, Efficient Numerical Methods for Nonlinear MPC and Moving Horizon Estimation, 391-417, (2009), Berlin, Heidelberg · Zbl 1195.93038
[17] Diehl, Moritz; Findeisen, Rolf; Allgöwer, Frank, 2. A Stabilizing Real-Time Implementation of Nonlinear Model Predictive Control, 25-52, (2007) · Zbl 1226.93065
[18] Domahidi, A., Perez, J.: FORCES professional. http://embotech.com/FORCES-Pro (2013)
[19] Domahidi, A., Zgraggen, A., Zeilinger, M.N., Morari, M., Jones, C.N.: Efficient interior point methods for multistage problems arising in receding horizon control. In: Proceedings of the IEEE Conference on Decision and Control (CDC), pp. 668-674. Maui, HI (2012)
[20] Ferreau, HJ; Bock, HG; Diehl, M., An online active set strategy to overcome the limitations of explicit MPC, Int. J. Robust Nonlinear Control, 18, 816-830, (2008) · Zbl 1284.93100
[21] Ferreau, HJ; Kirches, C.; Potschka, A.; Bock, HG; Diehl, M., qpOASES: A parametric active-set algorithm for quadratic programming, Math. Program. Comput., 6, 327-363, (2014) · Zbl 1302.90146
[22] Frasch, JV; Sager, S.; Diehl, M., A parallel quadratic programming method for dynamic optimization problems, Math. Program. Comput., 7, 289-329, (2015) · Zbl 1321.90094
[23] Frasch, J.V., Vukov, M., Ferreau, H.J., Diehl, M.: A new quadratic programming strategy for efficient sparsity exploitation in SQP-based nonlinear MPC and MHE. In: Proceedings of the 19th World Congress, The International Federation of Automatic Control. Cape Town, South Africa (2014)
[24] Frasch, J.V., Wirsching, L., Sager, S., Bock, H.G.: Mixed-level iteration schemes for nonlinear model predictive control. In: 4th IFAC Conference on Nonlinear Model Predictive Control. IFAC Proceedings Volumes, vol. 45, pp. 138-144. Elsevier (2012)
[25] Frison, G.: Numerical Methods for Model Predictive Control. Master’s thesis, Department of Informatics and Mathematical Modelling Technical University of Denmark (2012)
[26] Frison, G., Jørgensen, J.B.: Efficient implementation of the Riccati recursion for solving linear-quadratic control problems. In: 2013 IEEE International Conference on Control Applications (CCA), pp. 1117-1122 (2013)
[27] Frison, G., Jørgensen, J.B.: A fast condensing method for solution of linear-quadratic control problems. In: Proceedings of the IEEE Conference on Decision and Control (CDC), pp. 7715-7720. IEEE (2013)
[28] Frison, G., Kouzoupis, D., Jørgensen, J.B., Diehl, M.: An efficient implementation of partial condensing for nonlinear model predictive control. In: Proceedings of the IEEE Conference on Decision and Control (CDC) IEEE (2016)
[29] Frison, G., Kouzoupis, D., Sartor, T., Zanelli, A., Diehl, M.: BLASFEO: Basic linear algebra subroutines for embedded optimization. ACM Trans. Math. Softw. Accepted (2018)
[30] Frison, G., Sorensen, H.B., Dammann, B., Jørgensen, J.B.: High-performance small-scale solvers for linear model predictive control. In: Proceedings of the European Control Conference (ECC), pp. 128-133 (2014)
[31] Frison, G.: Algorithms and Methods for High-Performance Model Predictive Control. PhD thesis, Technical University of Denmark (DTU) (2015)
[32] Gafni, EM; Bertsekas, DP, Two-metric projection methods for constrained optimization, SIAM J. Control Optim., 22, 936-964, (1984) · Zbl 0555.90086
[33] Gertz, EM; Wright, SJ, Object-oriented software for quadratic programming, ACM Trans Math. Softw., 29, 58-81, (2003) · Zbl 1068.90586
[34] Gill, P.E., Murray, W., Saunders, M.A.: User’s guide for QPOPT 1.0: a fortran package for quadratic programming (1995)
[35] Giselsson, Pontus, Improved Fast Dual Gradient Methods for Embedded Model Predictive Control, IFAC Proceedings Volumes, 47, 2303-2309, (2014)
[36] Glad, T.; Jonson, H., A Method for State and Control Constrained Linear Quadratic Control Problems, IFAC Proceedings Volumes, 17, 1583-1587, (1984)
[37] Gondzio, J.; Grothey, A., A new unblocking technique to warmstart interior point methods based on sensitivity analysis, SIAM J. Control Optim., 19, 1184-1210, (2006) · Zbl 1177.90411
[38] Gros, S., Zanon, M., Quirynen, R., Bemporad, A., Diehl, M.: From linear to nonlinear MPC: bridging the gap via the real-time iteration. Int. J Control. https://doi.org/10.1080/00207179.2016.1222553 (2016)
[39] Hours, JH; Jones, CN, A parametric nonconvex decomposition algorithm for real-time and distributed NMPC, IEEE Trans. Autom. Control, 61, 287-302, (2014) · Zbl 1359.90134
[40] Houska, B.; Ferreau, HJ; Diehl, M., ACADO toolkit—an Open source framework for automatic control and dynamic optimization, Optim. Control Appl. Methods, 32, 298-312, (2011) · Zbl 1218.49002
[41] Houska, B.; Ferreau, HJ; Diehl, M., An auto-generated real-time iteration algorithm for nonlinear MPC in the microsecond range, Automatica, 47, 2279-2285, (2011) · Zbl 1227.65054
[42] Houska, B.; Frasch, JV; Diehl, M., An augmented Lagrangian based algorithm for distributed non-convex optimization, SIAM J. Optim., 26, 1101-1127, (2016) · Zbl 1345.90069
[43] Janka, D.; Kirches, C.; Sager, S.; Wächter, A., An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal hessian matrix, Math. Program. Comput., 8, 435-459, (2016) · Zbl 1391.90575
[44] Käpernick, B., Graichen, K.: The gradient based nonlinear model predicitive control software GRAMPC. In: Proceedings of the European Control Conference (ECC) (2014)
[45] Kirches, Christian; Bock, Hans Georg; Schlöder, Johannes P.; Sager, Sebastian, Complementary Condensing for the Direct Multiple Shooting Method, 195-206, (2012), Berlin, Heidelberg
[46] Kirches, C.; Sager, S.; Bock, HG; Schlöder, JP, Time-optimal control of automobile test drives with gear shifts, Optim. Control Appl. Methods, 31, 137-153, (2010) · Zbl 1204.49033
[47] Kirches, Christian; Wirsching, Leonard; Sager, Sebastian; Bock, Hans Georg, Efficient Numerics for Nonlinear Model Predictive Control, 339-357, (2010), Berlin, Heidelberg
[48] Kouzoupis, D.; Klintberg, E.; Diehl, M.; Gros, S., A dual Newton stratgy for scenario decomposition in robust multistage MPC, Int. J. Robust Nonlinear Control, 28, 1913-2677, (2017) · Zbl 1390.49030
[49] Kouzoupis, D., Quirynen, R., Frasch, J.V., Diehl, M.: Block condensing for fast nonlinear MPC with the dual Newton strategy. In: Proceedings of the IFAC Conference on Nonlinear Model Predictive Control (NMPC), vol. 48, pp. 26-31 (2015)
[50] Leineweber, D.B.: Analyse und Restrukturierung eines Verfahrens zur Direkten Lösung von Optimalsteuerungsproblemen. Master’s thesis, University of Heidelberg (1995)
[51] Leineweber, D.B.: Efficient reduced SQP methods for the optimization of chemical processes described by large sparse DAE models. Fortschritt-Berichte VDI Reihe 3 Verfahrenstechnik, vol. 613. VDI Verlag, Düsseldorf (1999)
[52] Leineweber, DB; Bauer, I.; Bock, HG; Schlöder, JP, An efficient multiple shooting based reduced SQP strategy for large-scale dynamic process optimization. Part I: Theoretical aspects, Comput. Chem. Eng., 27, 157-166, (2003)
[53] Leineweber, DB; Schäfer, A.; Bock, HG; Schlöder, FP, An efficient multiple shooting based reduced SQP strategy for large-scale dynamic process optimization. Part II: Software aspects and applications, Comput. Chem. Eng., 27, 167-174, (2003)
[54] Leineweber, D.B., Bock, H.G., Schlöder, J.P.: Fast direct methods for real-time optimization of chemical processes. In: Proceedings of the 15th IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics Berlin, Berlin, 1997. Wissenschaft- und Technik-Verlag (1997)
[55] Li, WC; Biegler, LT, Multistep, Newton-type control strategies for constrained nonlinear processes, Chem. Eng. Res. Des., 67, 562-577, (1989)
[56] Mattingley, J.; Boyd, S., CVXGEN: A code generator for embedded convex optimization, Optim. Eng., 13, 1-27, (2012) · Zbl 1293.65095
[57] Mayne, DQ, Model predictive control: recent developments and future promise, Automatica, 50, 2967-2986, (2014) · Zbl 1309.93060
[58] Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Applied Optimization. vol. 87. Kluwer Academic Publishers (2004) · Zbl 1086.90045
[59] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer-Verlag, New York (2006)
[60] Ohtsuka, T., Acontinuation/GMRES method for fast computation of nonlinear receding horizon control, Automatica, 40, 563-574, (2004) · Zbl 1168.93340
[61] Patrinos, P., Bemporad, A.: An accelerated dual gradient-projection algorithm for linear model predictive control. In: Proceedings of the IEEE Conference on Decision and Control (CDC). IEEE (2012) · Zbl 1360.93400
[62] Patrinos, P.; Bemporad, A., An accelerated dual gradient-projection algorithm for embedded linear model predictive control, IEEE Trans. Autom. Control, 59, 18-33, (2014) · Zbl 1360.93400
[63] Patrinos, P.; Sopasakis, P.; Sarimveis, H., A global piecewise smooth Newton method for fast large-scale model predictive control, Automatica, 47, 2016-2022, (2011) · Zbl 1231.65110
[64] Powell, M. J. D., A fast algorithm for nonlinearly constrained optimization calculations, 144-157, (1978), Berlin, Heidelberg · Zbl 0374.65032
[65] Qin, SJ; Badgwell, TA, A survey of industrial model predictive control technology, Control Eng. Pract., 11, 733-764, (2003)
[66] Quirynen, Rien; Vukov, Milan; Diehl, Moritz, Multiple Shooting in a Microsecond, 183-201, (2015), Cham · Zbl 1337.65055
[67] Quirynen, R.; Vukov, M.; Zanon, M.; Diehl, M., Autogenerating microsecond solvers for nonlinear MPC: A tutorial using ACADO integrators, Optimal Control Appl. Methods, 36, 685-704, (2014) · Zbl 1330.93100
[68] Rao, CV; Wright, SJ; Rawlings, JB, Application of interior-point methods to model predictive control, J. Optim. Theory Appl., 99, 723-757, (1998) · Zbl 0973.90092
[69] Rawlings, J.B., Mayne, D.Q., Diehl, M.M.: Model Predictive Control: Theory, Computation, and Design, 2nd edn. Nob Hill Publishing (2017)
[70] Richter, S.: Computational Complexity Certification of Gradient Methods for Real-time Model Predictive Control. PhD thesis, ETH Zürich (2012)
[71] Richter, S., Jones, C.N., Morari, M.: Real-time input-constrained MPC using fast gradient methods. In: Proceedings of the IEEE Conference on Decision and Control (CDC) IEEE (2009)
[72] Sager, S.: Numerical Methods for Mixed-Integer Optimal Control Problems. Der Andere Verlag, Lübeck (2005) · Zbl 1094.65512
[73] Sargent, R.W.H., Sullivan, G.R.: The development of an efficient optimal control package. In: Stoer, J. (ed.) Optimization Techniques: Proceedings of the 8th IFIP Conference on Optimization Techniques Würzburg, September 5-9, 1977, pp. 158-168. Springer-Verlag (1978)
[74] Schmid, C.; Biegler, LT, Quadratic programming methods for reduced Hessian SQP, Comput. Chem. Eng., 18, 817-832, (1994)
[75] Shahzad, A., Goulart, P.J.: A new hot-start interior-point method for model predictive control. In: Proceedings of the IFAC World Congress (2011)
[76] Steinbach, Marc C., A Structured Interior Point SQP Method for Nonlinear Optimal Control Problems, 213-222, (1994), Basel · Zbl 0937.90510
[77] Stella, L., Themelis, A., Sopasakis, P., Patrinos, P.: A simple and efficient algorithm for nonlinear model predictive control. In: Proceedings of the IEEE Conference on Decision and Control (CDC), pp. 1939-1944. IEEE (2017)
[78] Stellato, B., Banjac, G., Goulart, P., Bemporad, A., Boyd, S.: OSQP: an operator splitting solver for quadratic programs. arXiv:1711.08013(2017)
[79] Ullmann, F.: Fiordos: A Matlab Toolbox for C-Code Generation for First Order Methods. Master’s thesis, ETH Zurich (2011)
[80] Vukov, M., Domahidi, A., Ferreau, H.J., Morari, M., Diehl, M.: Auto-generated algorithms for nonlinear model predictive control on long and on short horizons. In: Proceedings of the IEEE Conference on Decision and Control (CDC), pp. 5113-5118. IEEE (2013)
[81] Wang, Y.; Boyd, S., Fast model predictive control using online optimization, IEEE Trans. Control Syst. Technol., 18, 267-278, (2010)
[82] Wirsching, L.: Multi-level Iteration Schemes with Adaptive Level Choice for Nonlinear Model Predictive Control. PhD thesis, Ruprecht-Karls-Universität, Heidelberg (2018)
[83] Wirsching, L., Bock, H.G., Diehl, M.: Fast NMPC of a chain of masses connected by springs. In: Proceedings of the IEEE International Conference on Control Applications, Munich, pp. 591-596. IEEE (2006)
[84] Wright, SJ, Partitioned dynamic programming for optimal control, SIAM J. Optim., 1, 620-642, (1991) · Zbl 0754.49024
[85] Wright, S.J.: Structured interior point methods for optimal control. In: Proceedings of the 30th IEEE Conference on Decision and Control, pp. 1711-1716 (1991)
[86] Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM Publications, Philadelphia (1997) · Zbl 0863.65031
[87] Zanelli, A., Domahidi, A., Jerez, J.L., Morari, M.: FORCES NLP: An Efficient implementation of interior-point methods for multistage nonlinear nonconvex programs. Int. J Control. https://doi.org/10.1080/00207179.2017.1316017 (2017)
[88] Zanelli, A., Quirynen, R., Jerez, J., Diehl, M.: A homotopy-based nonlinear interior-point method for NMPC. In: Proceedings of the IFAC World Congress, Toulouse, France (2017)
[89] Zavala, VM; Biegler, LT, The advanced step NMPC controller: Optimality, stability and robustness, Automatica, 45, 86-93, (2009) · Zbl 1154.93364
[90] Zometa, P., Kögel, M., Findeisen, R.: \(μ\)AO-MPC: A free code generation tool for embedded real-time linear model predictive control. In: 2013 American Control Conference, pp. 5320-5325. IEEE, Washington, DC (2013)
[91] ACADOS. https://github.com/acados/acados (2018)
[92] BLASFEO. https://github.com/giaf/blasfeo (2016)
[93] hangingchainbenchmark. https://github.com/dkouzoup/hanging-chain-acado (2018)
[94] HPIPM. https://github.com/giaf/hpipm (2017)
[95] HPMPC. https://github.com/giaf/hpmpc (2014)
[96] treeQP. https://github.com/dkouzoup/treeQP (2017)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.