A dual Newton strategy for scenario decomposition in robust multistage MPC. (English) Zbl 1390.49030
Summary: 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.
MSC:
| 49M15 | Newton-type methods |
| 90C20 | Quadratic programming |
| 49N10 | Linear-quadratic optimal control problems |
| 93B35 | Sensitivity (robustness) |
References:
| [1] | CampoPJ, MorariM. Robust model predictive control. Paper presented at: American Control Conference; 1987; Minneapolis, MN. |
| [2] | MayneD, SeronM, RakovicS. Robust model predictive control of constrained linear systems with bounded disturbances. Automatica. 2005;41:219‐224. · Zbl 1066.93015 |
| [3] | MayneD, RakovicS, FindeisenR, AllgöwerF. Robust output feedback model predictive control of constrained linear systems. Automatica. 2006;42:1217‐1222. · Zbl 1116.93032 |
| [4] | Munoz de la PenaD, BemporadA, AlamoT. 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. |
| [5] | BernardiniD, BemporadA. 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. |
| [6] | LuciaS, AnderssonJ, BrandtH, DiehlM, EngellS. Handling uncertainty in economic model predictive control: a comparative case study. J Process Control. 2014;24:1247‐1259. |
| [7] | MaiwormM, BathgeT, FindeisenR. Scenario‐based model predictive control: recursive feasibility and stability. IFAC Symp Adv Control Chem Processes. 2015;48(8):50‐56. |
| [8] | LuciaS, FinklerT, BasakB, EngellS. 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. |
| [9] | HanssonA. A primal‐dual interior‐point method for robust optimal control of linear discrete‐time systems. IEEE Trans Autom Control. 2000;45:1639‐1655. · Zbl 0988.93028 |
| [10] | ZeilingerM, RaimondoD, DomahidiA, MorariM, JonesC. On real‐time robust model predictive control. Automatica. 2014;50:683‐694. · Zbl 1298.93160 |
| [11] | BirgeJR, HolmesDF. Efficient solution of two‐stage stochastic linear programs using interior point methods. Comput Optim Appl. 1992;1:245‐276. · Zbl 0792.90051 |
| [12] | JessupE, YangD, ZeniosS. Parallel factorization of structured matrices arising in stochastic programming. SIAM J Optim. 1994;4:833‐846. · Zbl 0813.65063 |
| [13] | SteinbachMC. Tree‐sparse convex programs. Math Methods Oper Res. 2002;56(3):347‐376. · Zbl 1064.90033 |
| [14] | PakazadSK, HanssonA, AndersenMS, NielsenI. Distributed primal‐dual interior‐point methods for solving tree‐structured coupled convex problems using message‐passing. Optim Methods Softw. 2016;32(3):401‐435. · Zbl 1364.90357 |
| [15] | KlintbergE, GrosS. A parallelizable interior‐point method for two‐stage robust MPC. IEEE Trans Control Syst Technol. 2017;25(6):2087‐2097. |
| [16] | LeidereiterC, PotschkaA, BockHG. Dual decomposition for QPs in scenario tree NMPC. Paper presented at: European Control Conference; 2015; Linz, Austria. |
| [17] | KlintbergE, DahlJ, FredrikssonJ, GrosS. An improved dual Newton strategy for scenario‐tree MPC. Paper presented at: IEEE 55th Conference on Decision and Control; 2016; Las Vegas, NV. |
| [18] | BirgeJ. Decomposition and partitioning methods for multistage stochastic linear programs. Oper Res. 1985;33:989‐1007. · Zbl 0581.90065 |
| [19] | MulveyJ, RuszczyńskiA. A new scenario decomposition method for large‐scale stochastic optimization. Oper Res. 1995;43:477‐490. · Zbl 0843.90086 |
| [20] | MartiR, LuciaS, SarabiaD, PaulenR, EngellS. Improving scenario decomposition algorithms for robust nonlinear model predictive control. Comput Chem Eng. 2015;79:30‐45. |
| [21] | FerreauHJ, KozmaA, DiehlM. 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. |
| [22] | FraschJV, SagerS, DiehlM. A parallel quadratic programming method for dynamic optimization problems. Math Program Comput. 2015;7:289‐329. · Zbl 1321.90094 |
| [23] | LiuJWH. The multifrontal method for sparse matrix solution: theory and practice. SIAM Rev. 1992;34(1):82‐109. · Zbl 0919.65019 |
| [24] | VandenbergheL, AndersenMS. Chordal graphs and semidefinite optimization. Foundations Trends Optim. 2015;1(4):241‐433. |
| [25] | GolumbicMC. Algorithmic Graph Theory and Perfect Graphs. 2nd ed. Amsterdam, Netherlands: Elsevier; 2004. · Zbl 1050.05002 |
| [26] | BlairJRS, PeytonB. An Introduction to Chordal Graphs and Clique Trees. New York, NY:Springer New York; 1993:1‐29. · Zbl 0803.68081 |
| [27] | treeQP: A toolbox for tree‐sparse quadratic programming. 2017. https://github.com/dkouzoup/treeQP |
| [28] | FrisonG, KouzoupisD, DiehlM, Jørgensen JB. A high‐performance Riccati based solver for tree‐structured quadratic programs. IFAC World Congress. 2017;50(1):14399‐14405. |
| [29] | FrisonG, KouzoupisD, ZanelliA, DiehlM. BLASFEO: Basic linear algebra subroutines for embedded optimization. CoRR 2017; abs/1704.02457.http://arxiv.org/abs/1704.02457 |
| [30] | BoydS, VandenbergheL. Convex Optimization. Cambridge, UK: University Press; 2004. · Zbl 1058.90049 |
| [31] | BertsekasD, TsitsiklisJN. Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs, NJ: Prentice Hall; 1989. · Zbl 0743.65107 |
| [32] | KozmaA, KlintbergE, GrosS, DiehlM. An improved distributed dual Newton‐CG method for convex quadratic programming problems. Paper presented at: American Control Conference; 2014; Portland, OR. |
| [33] | FraschJV, VukovM, FerreauHJ, DiehlM. 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 |
| [35] | DagumL, MenonR. OpenMP: an industry standard API for shared‐memory programming. IEEE Comput Sci Eng. 1998;5(1):46‐55. |
| [36] | WieB, BernsteinD. Benchmark problems for robust control design. J Guid Control Dynam. 1992;15:1057‐1059. |
| [37] | KothareM, BalakrishnanV, MorariM. Robust constrained model predictive control using linear matrix inequalities. Automatica. 1996;32:1361‐1379. · Zbl 0897.93023 |
| [38] | HPMPC. 2014. https://github.com/giaf/hpmpc |
| [39] | DolanE, MoréJ. Benchmarking optimization software with performance profiles. Math Program. 2002;91:201‐213. · Zbl 1049.90004 |
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.
