Projection-free parallel quadratic programming for linear model predictive control

Abstract

A key component in enabling the application of model predictive control (MPC) in fields such as automotive, aerospace, and factory automation is the availability of low-complexity fast optimisation algorithms to solve the MPC finite horizon optimal control problem in architectures with reduced computational capabilities. In this paper, we introduce a projection-free iterative optimisation algorithm and discuss its application to linear MPC. The algorithm, originally developed by Brand for non-negative quadratic programs, is based on a multiplicative update rule and it is shown to converge to a fixed point which is the optimum. An acceleration technique based on a projection-free line search is also introduced, to speed-up the convergence to the optimum. The algorithm is applied to MPC through the dual of the quadratic program (QP) formulated from the MPC finite time optimal control problem. We discuss how termination conditions with guaranteed degree of suboptimality can be enforced, and how the algorithm performance can be optimised by pre-computing the matrices in a parametric form. We show computational results of the algorithm in three common case studies and we compare such results with the results obtained by other available free and commercial QP solvers.

Keywords:

• model predictive control
• optimisation
• numerical algorithms
• constrained control

Acknowledgements

The authors acknowledge Prof. A.V. Knyazev, MERL, for useful insight in interpreting PQP as a variable-preconditioned iterative algorithm, Dr. P. Patrinos, IMT Lucca, for useful insights in the implementation of the GPAD algorithm, and several colleagues and interns at MERL for testing the implementation of PQP algorithms and providing useful data and comments.

These authors made equal contributions in this paper.

Notes

Note: Minimum computing time for M-code and C-code algorithms shown in bold.

Note: Minimum computing time for M-code and C-code algorithms shown in bold.

Figure 4 Trajectories for the jet aircraft control case study. Upper plot: outputs (solid), references (dash), and constraints (dot). Lower plot: control inputs (solid) and constraints (dash)

Note: Minimum computing time for M-code and C-code algorithms shown in bold.

Figure 6 Trajectories in the DC-motor control simulation for reference with a _r = 2.5. Upper plot: load angle (solid) and reference (dash). Middle plot: shaft torque (solid) and constraints (dash). Lower plot: control inputs (solid) and constraints (dash)

Note: Minimum computing time for M-code and C-code algorithms shown in bold.

Figure 7 Trajectories in the DC-motor control simulation for reference with a _r = 4.0. Upper plot: load angle (solid) and reference (dash). Middle plot: shaft torque (solid) and constraints (dash). Lower plot: control inputs (solid) and constraints (dash)

Figure 8 Distribution of the computation time of PQPMPC in DC-motor control simulations for references with a _r = 2.5 (dark grey) and a _r = 4.0 (light grey)

1. Preliminary results related to this subject have been presented in Brand et al. (2011) and Di Cairano and Brand (2013). This paper provides more details on the algorithms and the related convergence proofs and more detailed simulation studies and comparisons. Also, the algorithm implementations have been improved, thus leading to improved performance in the simulations.

2. If there exists multiple such that J(z) = J ^* they are all called optimal solutions.

3. This is obtained by applying to the gradient the operator (·)⁻, which changes the sign to the negative components and set the positive components to 0.

4. In recent versions of the toolbox, the QP algorithm is changed, mainly due to a different toolbox architecture.

5. This algorithm was implemented by the authors of this paper, but it was shown to and discussed with the authors of Bemporad and Patrinos (2012) to verify its correct implementation.