×

Low-complexity method for hybrid MPC with local guarantees. (English) Zbl 1421.93049

Summary: Model predictive control problems for constrained hybrid systems are usually cast as mixed-integer optimization problems (MIPs). However, commercial MIP solvers are designed to run on desktop computing platforms and are not suited for embedded applications, which are typically restricted by limited computational power and memory. To alleviate these restrictions, we develop a novel low-complexity, iterative method for a class of nonconvex, nonsmooth optimization problems. This class of problems encompasses hybrid model predictive control problems, where the dynamics are piecewise affine (PWA). We give conditions such that the proposed algorithm has fixed points and show that, under practical assumptions, our method is guaranteed to converge locally to local minima. This is in contrast to other low-complexity methods in the literature, such as the nonconvex alternating directions method of multipliers (ADMM), for which no such guarantees are known for this class of problems. By interpreting the PWA dynamics as a union of polyhedra, we can exploit the problem structure and develop an algorithm based on operator splitting procedures. Our algorithm departs from the traditional MIP formulation and leads to a simple, embeddable method that only requires matrix-vector multiplications and small-scale projections onto polyhedra. We illustrate the efficacy of the method on two numerical examples, achieving good closed-loop performance with computational times several orders of magnitude smaller compared to state-of-the-art MIP solvers. Moreover, it is competitive with ADMM in terms of suboptimality and computation time, and additionally it provides local optimality and local convergence guarantees.

MSC:

93B40 Computational methods in systems theory (MSC2010)
93C30 Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems)
93B28 Operator-theoretic methods
90C30 Nonlinear programming
49J52 Nonsmooth analysis
47H09 Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc.
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] A. Alessio and A. Bemporad, A survey on explicit model predictive control, in Nonlinear Model Predictive Control, Springer, 2009, pp. 345-369, https://doi.org/10.1007/978-3-642-01094-1_29. · Zbl 1195.93048
[2] A. Arce, A. del Real, and C. Bordons, MPC for battery/fuel cell hybrid vehicles including fuel cell dynamics and battery performance improvement, J. Process Control, 19 (2009), pp. 1289-1304, https://doi.org/10.1016/j.jprocont.2009.03.004.
[3] D. Axehill, Integer Quadratic Programming for Control and Communication, Ph.D. thesis, Linköping University, 2008.
[4] H. Bauschke and P. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, 2011, https://doi.org/10.1007/978-3-319-48311-5. · Zbl 1218.47001
[5] A. Bemporad and M. Morari, Control of systems integrating logic, dynamics, and constraints, Automatica, 35 (1999), pp. 407-427, https://doi.org/10.1016/S0005-1098(98)00178-2. · Zbl 1049.93514
[6] V. Berinde, Iterative Approximation of Fixed Points, 2nd ed., Springer, 2007, https://doi.org/10.1007/978-3-540-72234-2. · Zbl 1165.47047
[7] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2011), pp. 1-122, https://doi.org/10.1561/2200000016. · Zbl 1229.90122
[8] G. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963, https://doi.org/10.7249/r366. · Zbl 0108.33103
[9] S. Di Cairano, A. Bemporad, I. Kolmanovsky, and D. Hrovat, Model predictive control of magnetically actuated mass spring dampers for automotive applications, Int. J. Control, 80 (2007), pp. 1701-1716, https://doi.org/10.1080/00207170701379804. · Zbl 1130.93345
[10] A. Domahidi, A. Zgraggen, M. Zeilinger, M. Morari, and C. Jones, Efficient interior point methods for multistage problems arising in receding horizon control, in Proceedings of the 51st IEEE Conference on Decision and Control, Maui, HI, 2012, pp. 668-674, https://doi.org/10.1109/cdc.2012.6426855.
[11] D. Frick, Automatic Code Generation Tool, https://github.com/dafrick/codegen, 2016.
[12] D. Frick, A. Domahidi, and M. Morari, Embedded optimization for mixed logical dynamical systems, Comput. Chem. Engrg., 72 (2015), pp. 21-33, https://doi.org/10.1016/j.compchemeng.2014.06.005.
[13] T. Geyer, G. Papafotiou, R. Frasca, and M. Morari, Constrained optimal control of the step-down DC-DC converter, IEEE Trans. Power Electronics, 23 (2008), pp. 2454-2464, https://doi.org/10.1109/TPEL.2008.2002057.
[14] A. Hempel, Control of Piecewise Affine Systems through Inverse Optimization, Ph.D. thesis, Dissertation ETH No. 23222, ETH Zürich, 2016, https://doi.org/10.3929/ethz-a-010615354.
[15] R. Henrion and J. Outrata, On calculating the normal cone to a finite union of convex polyhedra, Optimization, 57 (2008), pp. 57-78, https://doi.org/10.1080/02331930701778874. · Zbl 1220.52001
[16] M. Herceg, M. Kvasnica, C. Jones, and M. Morari, Multi-parametric toolbox 3.0, in Proceedings of the European Control Conference, IEEE, 2013, pp. 502-510, https://doi.org/10.23919/ecc.2013.6669862.
[17] J.-H. Hours and C. Jones, A parametric nonconvex decomposition algorithm for real-time and distributed NMPC, IEEE Trans. Automat. Control, 61 (2016), pp. 287-302, https://doi.org/10.1109/TAC.2015.2426231. · Zbl 1359.90134
[18] B. Houska, J. Frasch, and M. Diehl, An augmented Lagrangian based algorithm for distributed nonconvex optimization, SIAM J. Optim., 26 (2016), pp. 1101-1127, https://doi.org/10.1137/140975991. · Zbl 1345.90069
[19] IBM, IBM ILOG CPLEX Optimization Studio, 2015.
[20] M. Jung, Relaxations and Approximations for Mixed-Integer Optimal Control, Ph.D. thesis, Universität Heidelberg, 2013, https://doi.org/10.11588/heidok.00016036.
[21] M. N. Jung, C. Kirches, and S. Sager, On perspective functions and vanishing constraints in mixed-integer nonlinear optimal control, in Facets of Combinatorial Optimization, Springer, 2013, pp. 387-417, https://doi.org/10.1007/978-3-642-38189-8_16. · Zbl 1320.49011
[22] R. Lang, A note on the measurability of convex sets, Arch. Math. (Basel), 47 (1986), pp. 90-92, https://doi.org/10.1007/BF01202504. · Zbl 0607.28003
[23] S. Leyffer, MacMPEC: AMPL Collection of MPECs, Argonne National Laboratory, https://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC, 2009.
[24] G. Li and T. Pong, Global convergence of splitting methods for nonconvex composite optimization, SIAM J. Optim., 25 (2015), pp. 2434-2460, https://doi.org/10.1137/140998135. · Zbl 1330.90087
[25] A. Liniger, A. Domahidi, and M. Morari, Optimization-based autonomous racing of 1:43 scale RC cars, Optimal Control Appl. Methods, 36 (2015), pp. 628-647, https://doi.org/10.1002/oca.2123. · Zbl 1330.93094
[26] J. Löfberg, YALMIP: A toolbox for modeling and optimization in MATLAB, in Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, LA, 2004, pp. 284-289, https://doi.org/10.1109/CACSD.2004.1393890.
[27] S. Magnússon, P. C. Weeraddana, M. G. Rabbat, and C. Fischione, On the convergence of alternating direction Lagrangian methods for nonconvex structured optimization problems, IEEE Trans. Control Network Syst., 3 (2016), pp. 296-309, https://doi.org/10.1109/TCNS.2015.2476198. · Zbl 1370.90196
[28] M. Morari and J. Lee, Model predictive control: Past, present and future, Comput. Chem. Engrg., 23 (1999), pp. 667-682, https://doi.org/10.1016/S0098-1354(98)00301-9.
[29] J. Nocedal and S. Wright, Numerical Optimization, 2nd ed., Springer Science+Business Media, 2006, https://doi.org/10.1007/978-0-387-40065-5. · Zbl 1104.65059
[30] R. A. Poliquin, R. T. Rockafellar, and L. Thibault, Local differentiability of distance functions, Trans. Amer. Math. Soc., 352 (2000), pp. 5231-5249, https://www.jstor.org/stable/221932. · Zbl 0960.49018
[31] R. Rockafellar and R. Wets, Variational Analysis, Springer, 1998, https://doi.org/10.1007/978-3-642-02431-3. · Zbl 0888.49001
[32] A. Ruszczyński, Nonlinear Optimization, Princeton University Press, 2006, https://doi.org/10.2307/j.ctvcm4hcj. · Zbl 1108.90001
[33] R. Takapoui, N. Moehle, S. Boyd, and A. Bemporad, A simple effective heuristic for embedded mixed-integer quadratic programming, Int. J. Control, (2017), pp. 1-11, https://doi.org/10.1080/00207179.2017.1316016. · Zbl 1434.90117
[34] J. Vielma, Mixed integer linear programming formulation techniques, SIAM Rev., 57 (2015), pp. 3-57, https://doi.org/10.1137/130915303. · Zbl 1338.90277
[35] J. J. Ye, Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints, SIAM J. Optim., 10 (2000), pp. 943-962, https://doi.org/10.1137/S105262349834847X. · Zbl 1005.49019
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.