A dual Newton strategy for scenario decomposition in robust multistage MPC
Corresponding Author
D. Kouzoupis
Department of Microsystems Engineering (IMTEK), University of Freiburg, Freiburg im Breisgau, Germany
Correspondence
D. Kouzoupis, Department of Microsystems Engineering (IMTEK), University of Freiburg, 79110 Freiburg im Breisgau, Germany.
Email: [email protected]
Search for more papers by this authorM. Diehl
Department of Microsystems Engineering (IMTEK), University of Freiburg, Freiburg im Breisgau, Germany
Department of Mathematics, University of Freiburg, Freiburg im Breisgau, Germany
Search for more papers by this authorS. Gros
Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden
Search for more papers by this authorCorresponding Author
D. Kouzoupis
Department of Microsystems Engineering (IMTEK), University of Freiburg, Freiburg im Breisgau, Germany
Correspondence
D. Kouzoupis, Department of Microsystems Engineering (IMTEK), University of Freiburg, 79110 Freiburg im Breisgau, Germany.
Email: [email protected]
Search for more papers by this authorM. Diehl
Department of Microsystems Engineering (IMTEK), University of Freiburg, Freiburg im Breisgau, Germany
Department of Mathematics, University of Freiburg, Freiburg im Breisgau, Germany
Search for more papers by this authorS. Gros
Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden
Search for more papers by this authorSummary
This paper considers the solution of tree-structured quadratic programs as they may arise in multistage model predictive control. In this context, sampling the uncertainty on prescribed decision points gives rise to different scenarios that are linked to each other via the so-called nonanticipativity constraints. Previous work suggests to dualize these constraints and apply Newton's method on the dual problem to achieve a parallelizable scheme. However, it has been observed that the globalization strategy in such an approach can be expensive. To alleviate this problem, we propose to dualize both the nonanticipativity constraints and the dynamics to obtain a computationally cheap globalization. The dual Newton system is then reformulated into small highly structured linear systems that can be solved in parallel to a large extent. The algorithm is complemented by an open-source software implementation that targets embedded optimal control applications.
REFERENCES
- 1Campo PJ, Morari M. Robust model predictive control. Paper presented at: American Control Conference; 1987; Minneapolis, MN.
- 2Mayne D, Seron M, Rakovic S. Robust model predictive control of constrained linear systems with bounded disturbances. Automatica. 2005; 41: 219-224.
- 3Mayne D, Rakovic S, Findeisen R, Allgöwer F. Robust output feedback model predictive control of constrained linear systems. Automatica. 2006; 42: 1217-1222.
- 4Munoz de la Pena D, Bemporad A, Alamo T. Stochastic programming applied to model predictive control. Paper presented at: 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference (CDC-ECC '05;); 2005; Seville, Spain.
- 5Bernardini D, Bemporad A. Scenario-based model predictive control of stochastic constrained linear systems. Paper presented at: Proceedings of the 48th IEEE Conference on Decision and Control; 2009; Shanghai, China.
- 6Lucia S, Andersson J, Brandt H, Diehl M, Engell S. Handling uncertainty in economic model predictive control: a comparative case study. J Process Control. 2014; 24: 1247-1259.
- 7Maiworm M, Bathge T, Findeisen R. Scenario-based model predictive control: recursive feasibility and stability. IFAC Symp Adv Control Chem Processes. 2015; 48(8): 50-56.
- 8Lucia S, Finkler T, Basak B, Engell S. A new robust NMPC scheme and its application to a semi-batch reactor example. IFAC Int Symp Adv Control Chem Processes. 2012; 45(15): 69-74.
- 9Hansson A. A primal-dual interior-point method for robust optimal control of linear discrete-time systems. IEEE Trans Autom Control. 2000; 45: 1639-1655.
- 10Zeilinger M, Raimondo D, Domahidi A, Morari M, Jones C. On real-time robust model predictive control. Automatica. 2014; 50: 683-694.
- 11Birge JR, Holmes DF. Efficient solution of two-stage stochastic linear programs using interior point methods. Comput Optim Appl. 1992; 1: 245-276.
10.1007/BF00249637 Google Scholar
- 12Jessup E, Yang D, Zenios S. Parallel factorization of structured matrices arising in stochastic programming. SIAM J Optim. 1994; 4: 833-846.
10.1137/0804048 Google Scholar
- 13Steinbach MC. Tree-sparse convex programs. Math Methods Oper Res. 2002; 56(3): 347-376.
- 14Pakazad SK, Hansson A, Andersen MS, Nielsen I. Distributed primal-dual interior-point methods for solving tree-structured coupled convex problems using message-passing. Optim Methods Softw. 2016; 32(3): 401-435.
- 15Klintberg E, Gros S. A parallelizable interior-point method for two-stage robust MPC. IEEE Trans Control Syst Technol. 2017; 25(6): 2087-2097.
- 16Leidereiter C, Potschka A, Bock HG. Dual decomposition for QPs in scenario tree NMPC. Paper presented at: European Control Conference; 2015; Linz, Austria.
- 17Klintberg E, Dahl J, Fredriksson J, Gros S. An improved dual Newton strategy for scenario-tree MPC. Paper presented at: IEEE 55th Conference on Decision and Control; 2016; Las Vegas, NV.
- 18Birge J. Decomposition and partitioning methods for multistage stochastic linear programs. Oper Res. 1985; 33: 989-1007.
- 19Mulvey J, Ruszczyński A. A new scenario decomposition method for large-scale stochastic optimization. Oper Res. 1995; 43: 477-490.
- 20Marti R, Lucia S, Sarabia D, Paulen R, Engell S. Improving scenario decomposition algorithms for robust nonlinear model predictive control. Comput Chem Eng. 2015; 79: 30-45.
- 21Ferreau HJ, Kozma A, Diehl M. A parallel active-set strategy to solve sparse parametric quadratic programs arising in MPC. IFAC Nonlin Model Predictive Control Conf. 2012; 45(17): 74-79.
- 22Frasch JV, Sager S, Diehl M. A parallel quadratic programming method for dynamic optimization problems. Math Program Comput. 2015; 7: 289-329.
- 23Liu JWH. The multifrontal method for sparse matrix solution: theory and practice. SIAM Rev. 1992; 34(1): 82-109.
- 24Vandenberghe L, Andersen MS. Chordal graphs and semidefinite optimization. Foundations Trends Optim. 2015; 1(4): 241-433.
10.1561/2400000006 Google Scholar
- 25Golumbic MC. Algorithmic Graph Theory and Perfect Graphs. 2nd ed. Amsterdam, Netherlands: Elsevier; 2004.
- 26Blair JRS, Peyton B. An Introduction to Chordal Graphs and Clique Trees. New York, NY:Springer New York; 1993: 1-29.
- 27 treeQP: A toolbox for tree-sparse quadratic programming. 2017. https://github.com/dkouzoup/treeQP
- 28Frison G, Kouzoupis D, Diehl M, Jørgensen JB. A high-performance Riccati based solver for tree-structured quadratic programs. IFAC World Congress. 2017; 50(1): 14399-14405.
- 29Frison G, Kouzoupis D, Zanelli A, Diehl M. BLASFEO: Basic linear algebra subroutines for embedded optimization. CoRR 2017; abs/1704.02457.http://arxiv.org/abs/1704.02457
- 30Boyd S, Vandenberghe L. Convex Optimization. Cambridge, UK: University Press; 2004.
10.1017/CBO9780511804441 Google Scholar
- 31Bertsekas D, Tsitsiklis JN. Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs, NJ: Prentice Hall; 1989.
- 32Kozma A, Klintberg E, Gros S, Diehl M. An improved distributed dual Newton-CG method for convex quadratic programming problems. Paper presented at: American Control Conference; 2014; Portland, OR.
- 33Frasch JV, Vukov M, Ferreau HJ, Diehl M. A new quadratic programming strategy for efficient sparsity exploitation in SQP-based nonlinear MPC and MHE. Paper presented at: Proceedings of the 19th IFAC World Congress; 2014; Cape Town, South Africa.
- 34 BLASFEO. 2016. https://github.com/giaf/blasfeo
- 35Dagum L, Menon R. OpenMP: an industry standard API for shared-memory programming. IEEE Comput Sci Eng. 1998; 5(1): 46-55.
- 36Wie B, Bernstein D. Benchmark problems for robust control design. J Guid Control Dynam. 1992; 15: 1057-1059.
- 37Kothare M, Balakrishnan V, Morari M. Robust constrained model predictive control using linear matrix inequalities. Automatica. 1996; 32: 1361-1379.
- 38 HPMPC. 2014. https://github.com/giaf/hpmpc
- 39Dolan E, Moré J. Benchmarking optimization software with performance profiles. Math Program. 2002; 91: 201-213.
