zbMATH — the first resource for mathematics

Soft inequality constraints in gradient method and fast gradient method for quadratic programming. (English) Zbl 1431.90106
Summary: A quadratic program (QP) with soft inequality constraints with both linear and quadratic costs on constraint violation can be solved with the dual gradient method (GM) or the dual fast gradient method (FGM). The treatment of the constraint violation influences the efficiency and usefulness of the algorithm. We improve on the classical way of extending the QP: our novel contribution is that we obtain the solution to the soft-constrained QP without explicitly introducing slack variables. This approach is more efficient than solving the extended QP with GM or FGM and results in a similar algorithm than if the soft constraints were replaced with hard ones. The approach is intended for applications in model predictive control with fast system dynamics, where QPs of this type are solved at every sampling time in the millisecond range.
90C20 Quadratic programming
49N05 Linear optimal control problems
93C05 Linear systems in control theory
65K10 Numerical optimization and variational techniques
49K20 Optimality conditions for problems involving partial differential equations
65K05 Numerical mathematical programming methods
Full Text: DOI
[1] Afonso RJM, Galvo RKH (2012) Infeasibility handling in constrained MPC. In: Frontiers of model predictive control. InTech, pp 47-64. https://doi.org/10.5772/38437
[2] Bemporad, A.; Morari, M.; Dua, V.; Pistikopoulos, EN, The explicit linear quadratic regulator for constrained systems, Automatica, 38, 3-20, (2002) · Zbl 0999.93018
[3] Borrelli F, Bemporad A, Morari M (2015) Predictive control for linear and hybrid systems. Cambridge University Press, Cambridge · Zbl 1365.93003
[4] Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, New York. https://web.stanford.edu/ boyd/cvxbook/bv_cvxbook.pdf · Zbl 1058.90049
[5] Oliveira, NMC; Biegler, LT, Constraint handling and stability properties of model-predictive control, AIChE J, 40, 1138-1155, (1994)
[6] Domahidi A, Zgraggen AU, Zeilinger MN, Morari M, Jones C (2012) Efficient interior point methods for multistage problems arising in receding horizon control. In: Proceedings of the 51st IEEE conference on decision and control, pp 668-674. https://doi.org/10.1109/CDC.2012.6426855
[7] Dorn, WS, Duality in quadratic programming, Quart Appl Math, 18, 155-162, (1960) · Zbl 0101.37003
[8] Ferreau, HJ; Bock, HG; Diehl, M., An online active set strategy to overcome the limitations of explicit MPC, Int J Robust Nonlinear, 18, 816-830, (2008) · Zbl 1284.93100
[9] 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
[10] Gerkšič S, De Tommasi G (2016) ITER plasma current and shape control using MPC. In: 2016 IEEE conference on control applications (CCA), pp 599-604. https://doi.org/10.1109/CCA.2016.7587895
[11] Gerkšič S, Pregelj B, Perne M (2018) FPGA acceleration of model predictive control for ITER plasma current and shape control. In: 21st IEEE real time conference. https://indico.cern.ch/event/543031/contributions/2921473/
[12] Giselsson, P.; Boyd, S., Metric selection in fast dual forward – backward splitting, Automatica, 62, 1-10, (2015) · Zbl 1330.49032
[13] Giselsson P (2014a) Improved fast dual gradient methods for embedded model predictive control. In: IFAC proceedings on 19th IFAC world congress, vol 47, No. 3, pp 2303-2309
[14] Giselsson P (2014b) QPgen. http://www.control.lth.se/QPgen/index.html, v0.0.2. Accessed 15 Mar 2015
[15] Giselsson P, Boyd S (2014) Preconditioning in fast dual gradient methods. In: 53rd IEEE conference on decision and control, CDC 2014, Los Angeles, CA, USA, 15-17 December 2014, pp 5040-5045. https://doi.org/10.1109/CDC.2014.7040176
[16] Hartley, EN; Jerez, JL; Suardi, A.; Maciejowski, JM; Kerrigan, EC; Constantinides, GA, Predictive control using an FPGA with application to aircraft control, IEEE Trans Control Syst Technol, 22, 1006-1017, (2014)
[17] Hovd, M.; Stoican, F., On the design of exact penalty functions for MPC using mixed integer programming, Comput Chem Eng, 70, 104-113, (2014)
[18] Jerez, JL; Goulart, PJ; Richter, S.; Constantinides, GA; Kerrigan, EC; Morari, M., Embedded online optimization for model predictive control at megahertz rates, IEEE Trans Automat Contr, 59, 3238-3251, (2014) · Zbl 1360.93235
[19] Karush W (2014) Minima of functions of several variables with inequalities as side conditions. In: Giorgi G, Kjeldsen T (eds) Traces and emergence of nonlinear programming. Birkhäuser, Basel. Reproduction of Masters Thesis, Department of Mathematics, University of Chicago, Chicago 1939. https://doi.org/10.1007/978-3-0348-0439-4_10
[20] Kerrigan EC, Maciejowski JM (2000) Soft constraints and exact penalty functions in model predictive control. In: Proceedings of the UKACC international conference (control). http://citeseerx.ist.psu.edu/viewdoc/download?doi= Accessed 30 Nov 2017
[21] Kouzoupis D (2014) Complexity of first-order methods for fast embedded model predictive control. Masters Thesis. Eidgenössische Technische Hochschule, Zürich. https://doi.org/10.3929/ethz-a-010255501
[22] Kuhn HW, Tucker AW (1951) Nonlinear programming. In: Proceedings of the second berkeley symposium on mathematical statistics and probability. University of California Press, Berkeley, pp 481-492. https://projecteuclid.org/euclid.bsmsp/1200500249. Accessed 10 Aug 2017
[23] Maciejowski J (2002) Predictive control: with constraints. Pearson Education, London · Zbl 0978.93002
[24] Mattingley, J.; Boyd, S., CVXGEN: a code generator for embedded convex optimization, Optim Eng, 13, 1-27, (2012) · Zbl 1293.65095
[25] Mattingley, J.; Wang, Y.; Boyd, S., Receding horizon control, automatic generation of high-speed solvers, IEEE Control Syst Mag, 31, 52-65, (2011) · Zbl 1395.93207
[26] Nesterov Y (2003) Introductory lectures on convex optimization: a basic course. Applied optimization. Springer, New York · Zbl 1086.90045
[27] Patrinos, P.; Bemporad, A., An accelerated dual gradient-projection algorithm for embedded linear model predictive control, IEEE Trans Automat Contr, 59, 18-33, (2014) · Zbl 1360.93400
[28] Patrinos, P.; Guiggiani, A.; Bemporad, A., A dual gradient-projection algorithm for model predictive control in fixed-point arithmetic, Automatica, 55, 226-235, (2015) · Zbl 1377.93067
[29] Qin, S.; Badgwell, TA, A survey of industrial model predictive control technology, Control Eng Pract, 11, 733-764, (2003)
[30] Rao, CV; Rawlings, JB, Steady states and constraints in model predictive control, AIChE J, 45, 1266-1278, (1999)
[31] Richter S (2012) Computational complexity certification of gradient methods for real-time model predictive control. Dissertation. Eidgenössische Technische Hochschule, Zürich, https://doi.org/10.3929/ethz-a-007587480
[32] Scokaert, POM; Rawlings, JB, Feasibility issues in linear model predictive control, AIChE J, 45, 1649-1659, (1999)
[33] Ullmann F, Richter S (2012) FiOrdOs-MPC example. Automatic Control Laboratory, ETH Zurich, Zurich. http://fiordos.ethz.ch/dokuwiki/doku.php?id=mpcexample. Accessed 13 Jan 2017
[34] Wang, Y.; Boyd, S., Fast model predictive control using online optimization, IEEE Trans Control Syst Technol, 18, 267-278, (2010)
[35] Wright, SJ; Raković, SV (ed.); Levine, WS (ed.), Efficient convex optimization for linear MPC, 287-303, (2019), Cham
[36] Zafiriou E, Chiou HW (1993) Output constraint softening for SISO model predictive control. In: Proceedings of the American control conference, San Francisco, pp 372-376. http://hdl.handle.net/1903/5360. Accessed 21 Aug 2017
[37] Zeilinger, MN; Morari, M.; Jones, CN, Soft constrained model predictive control with robust stability guarantees, IEEE Trans Automat Contr, 59, 1190-1202, (2014) · Zbl 1360.93260
[38] Zheng, A.; Morari, M., Stability of model predictive control with mixed constraints, IEEE Trans Automat Contr, 40, 1818-1823, (1995) · Zbl 0846.93075
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.