Top

Optimization and Engineering

Published in:

18-12-2018 | Research Article

Soft inequality constraints in gradient method and fast gradient method for quadratic programming

Authors: Matija Perne, Samo Gerkšič, Boštjan Pregelj

Published in: Optimization and Engineering | Issue 3/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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.

previous article Optimal designs of experiments for non-isothermal kinetic rates: analysis of different strategies

next article A software framework for embedded nonlinear model predictive control using a gradient-based augmented Lagrangian approach (GRAMPC)

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

The same system state and input components are bound from above and from below, as is often the case. Some solvers, including QPgen and its version augmented with the quadratic cost on constraint violation, assume upper and lower bounds on the same signals and substitute the constraints of the QP (5b) with the form \({\mathbf {b}}_l - {\mathbf {s}} \preceq \widetilde{\mathbf {C}}{\mathbf {x}} \preceq {\mathbf {b}}_u +{\mathbf {s}}\) and similarly for (5c). The QP modified in this way is mathematically equivalent to (5) and more efficient in resource usage for QP structured this way.

The comparison above is made without preconditioning because the results of the two approaches are not directly comparable when preconditioning is used.

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

Bemporad A, Morari M, Dua V, Pistikopoulos EN (2002) The explicit linear quadratic regulator for constrained systems. Automatica 38(1):3–20. https://doi.org/10.1016/S0005-1098(01)00174-1 MathSciNetCrossRefMATH

Borrelli F, Bemporad A, Morari M (2015) Predictive control for linear and hybrid systems. Cambridge University Press, CambridgeMATH

Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, New York. https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf CrossRefMATH

de Oliveira NMC, Biegler LT (1994) Constraint handling and stability properties of model-predictive control. AIChE J 40(7):1138–1155MathSciNetCrossRef

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

Dorn WS (1960) Duality in quadratic programming. Quart Appl Math 18:155–162. https://doi.org/10.1090/qam/112751 MathSciNetCrossRefMATH

Ferreau HJ, Bock HG, Diehl M (2008) An online active set strategy to overcome the limitations of explicit MPC. Int J Robust Nonlinear 18(8):816–830. https://doi.org/10.1002/rnc.1251 MathSciNetCrossRefMATH

Ferreau HJ, Kirches C, Potschka A, Bock HG, Diehl M (2014) qpOASES: a parametric active-set algorithm for quadratic programming. Math Program Comput 6(4):327–363. https://doi.org/10.1007/s12532-014-0071-1 MathSciNetCrossRefMATH

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

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/

Giselsson P, Boyd S (2015) Metric selection in fast dual forward–backward splitting. Automatica 62:1–10. https://doi.org/10.1016/j.automatica.2015.09.010 MathSciNetCrossRefMATH

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

Giselsson P (2014b) QPgen. http://www.control.lth.se/QPgen/index.html, v0.0.2. Accessed 15 Mar 2015

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

Hartley EN, Jerez JL, Suardi A, Maciejowski JM, Kerrigan EC, Constantinides GA (2014) Predictive control using an FPGA with application to aircraft control. IEEE Trans Control Syst Technol 22(3):1006–1017. https://doi.org/10.1109/TCST.2013.2271791 CrossRef

Hovd M, Stoican F (2014) On the design of exact penalty functions for MPC using mixed integer programming. Comput Chem Eng 70:104–113. https://doi.org/10.1016/j.compchemeng.2013.07.001 (Manfred Morari Special Issue)CrossRef

Jerez JL, Goulart PJ, Richter S, Constantinides GA, Kerrigan EC, Morari M (2014) Embedded online optimization for model predictive control at megahertz rates. IEEE Trans Automat Contr 59(12):3238–3251. https://doi.org/10.1109/TAC.2014.2351991 MathSciNetCrossRefMATH

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

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=10.1.1.228.1327&rep=rep1&type=pdf. Accessed 30 Nov 2017

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

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

Maciejowski J (2002) Predictive control: with constraints. Pearson Education, LondonMATH

Mattingley J, Boyd S (2012) CVXGEN: a code generator for embedded convex optimization. Optim Eng 13(1):1–27. https://doi.org/10.1007/s11081-011-9176-9 MathSciNetCrossRefMATH

Mattingley J, Wang Y, Boyd S (2011) Receding horizon control, automatic generation of high-speed solvers. IEEE Control Syst Mag 31:52–65. https://doi.org/10.1109/MCS.2011.940571 MathSciNetMATH

Nesterov Y (2003) Introductory lectures on convex optimization: a basic course. Applied optimization. Springer, New YorkMATH

Patrinos P, Bemporad A (2014) An accelerated dual gradient-projection algorithm for embedded linear model predictive control. IEEE Trans Automat Contr 59(1):18–33. https://doi.org/10.1109/TAC.2013.2275667 MathSciNetCrossRefMATH

Patrinos P, Guiggiani A, Bemporad A (2015) A dual gradient-projection algorithm for model predictive control in fixed-point arithmetic. Automatica 55(C):226–235. https://doi.org/10.1016/j.automatica.2015.03.002 MathSciNetCrossRefMATH

Qin S, Badgwell TA (2003) A survey of industrial model predictive control technology. Control Eng Pract 11(7):733–764. https://doi.org/10.1016/S0967-0661(02)00186-7 CrossRef

Rao CV, Rawlings JB (1999) Steady states and constraints in model predictive control. AIChE J 45(6):1266–1278CrossRef

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

Scokaert POM, Rawlings JB (1999) Feasibility issues in linear model predictive control. AIChE J 45(8):1649–1659CrossRef

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

Wang Y, Boyd S (2010) Fast model predictive control using online optimization. IEEE Trans Control Syst Technol 18:267–278. https://doi.org/10.1109/TCST.2009.2017934 CrossRef

Wright SJ (2019) Efficient convex optimization for linear MPC. In: Raković SV, Levine WS (eds) Handbook of model predictive control. Springer, Cham, pp 287–303. https://doi.org/10.1007/978-3-319-77489-3_13 CrossRef

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

Zeilinger MN, Morari M, Jones CN (2014) Soft constrained model predictive control with robust stability guarantees. IEEE Trans Automat Contr 59(5):1190–1202MathSciNetCrossRefMATH

Zheng A, Morari M (1995) Stability of model predictive control with mixed constraints. IEEE Trans Automat Contr 40(10):1818–1823. https://doi.org/10.1109/9.467664 MathSciNetCrossRefMATH

Title: Soft inequality constraints in gradient method and fast gradient method for quadratic programming
Authors: Matija Perne
Samo Gerkšič
Boštjan Pregelj
Publication date: 18-12-2018
Publisher: Springer US
Published in: Optimization and Engineering / Issue 3/2019
Print ISSN: 1389-4420
Electronic ISSN: 1573-2924
DOI: https://doi.org/10.1007/s11081-018-9416-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 3/2019

Optimal NURBS conversion of PDE surface-represented high-speed train heads

Continent-wide planning of seed production: mathematical model and industrial application

An effective approach of adaptive neuro-fuzzy inference system-integrated teaching learning-based optimization for use in machining optimization of S45C CNC turning

Optimal designs of experiments for non-isothermal kinetic rates: analysis of different strategies

Shape optimization of the ERCOFTAC centrifugal pump impeller using open-source software

American option pricing under GARCH with non-normal innovations

Premium Partners