Explicit MPC for hybrid systems

Model predictive control (MPC) is not computationally cheap (compared to, say, PID or LQG control) as it requires solving optimization problem – typically a quadratic program (QP) - online. The optimization solver needs to be a part of the controller.

There is an alternative, though, at least in same cases. It is called explicit MPC. The computationally heavy optimization is only perfomed only during the design process and the MPC controller is then implemented just as an affine state feedback

\bm u_k(\bm x(k)) = \mathbf F_k^i \bm x(k) + \mathbf g_k^i,\; \text{if}\; \bm x(k) \in \mathcal R_k^i,

with the coefficients picked from some kind of a lookup table in real time Although retreiving the coefficients of the feedback controller is not computationally trivial, still it is cheaper than full optimization.

Multiparametric programming

The key technique for explicit MPC is multi-parametric programming. In order to explain it, consider the following problem

J^\ast(x) = \inf_z J(z;x).

The z variable is an optimization variable, while x is a parameter. For a given parameter x, the cost function J is minimized. We study how the optimal cost J^\ast depends on the parameter, hence the name parametric programming. If x is a vector, the name of the problem changes to multiparametric programming.

Example: scalar variable, single parameter

Consider the following cost function J(z;x) in z parameterized by x. The optimization variable z is constrained and this constraint is also parameterized by x. \begin{aligned} J(z;x) &= \frac{1}{2} z^2 + 2zx + 2x^2 \\ \text{subject to} &\quad z \leq 1 + x. \end{aligned}

In this simple case we can aim at analytical solution. We proceed in the standard way – we introduce a Lagrange multiplicator \lambda and form the augmented cost function L(z,\lambda; x) = \frac{1}{2} z^2 + 2zx + 2x^2 + \lambda (z-1-x).

The necessary conditions of optimality for the inequality-constrained problem come in the form of KKT conditions \begin{aligned} z + 2x + \lambda &= 0,\\ z - 1 - x &\leq 0,\\ \lambda & \geq 0,\\ \lambda (z - 1 - x) &= 0. \end{aligned}

The last condition – the complementarity condition – gives rise to two scenarios: one corresponding to \lambda = 0, and the other corresponding to z - 1 - x = 0. We consider them separately below.

After substituting \lambda = 0 into the KKT conditions, we get \begin{aligned} z + 2x &= 0,\\ z - 1 - x & \leq 0. \end{aligned}

From the first equation we get how z depends on x, and from the second we obtain a bound on x. Finally, we can also substitute the expression for z into the cost function J to get the optimal cost J^\ast as a function of x. All these are summarized here \begin{aligned} z &= -2x,\\ x & \geq -\frac{1}{3},\\ J^\ast(x) &= 0. \end{aligned}

Now, the other scenario. Upon substitutin z - 1 - x = 0 into the KKT conditions we get

\begin{aligned} z + 2x + \lambda &= 0,\\ z - 1 - x &= 0,\\ \lambda & \geq 0. \end{aligned}

From the second equation we get the expression for z in terms of x, substituting into the first equation and invoking the condition on nonnegativity of \lambda we get the bound on x (not suprisingly it complements the one obtained in the previous scenario). Finally, substituting for z in the cost function J we get a formula for the cost J^\ast as a function of x.

\begin{aligned} z &= 1 + x,\\ \lambda &= -z - 2x \geq 0 \quad \implies \quad x \leq -\frac{1}{3},\\ J^\ast(x) &= \frac{9}{2}x^2 + 3x + \frac{1}{2}. \end{aligned}

The two scenarios can now be combined into a single piecewise affine function z(x) z(x) = \begin{cases} 1+x & \text{if } x \leq -\frac{1}{3},\\ -2x & \text{if } x > -\frac{1}{3}. \end{cases}

x = range(-1, 1, length=100)
z(x) = x <= -1/3 ? 1 + x : -2x
Jstar(x) = x <= -1/3 ? 9/2*x^2 + 3x + 1/2 : 0

using Plots
plot(x, z.(x), label="z(x)")
vline!([-1/3],line=:dash)
xlabel!("x")
ylabel!("z(x)")

and a piecewise quadratic cost function J^\ast(x) J^\ast(x) = \begin{cases} \frac{9}{2}x^2 + 3x + \frac{1}{2} & \text{if } x \leq -\frac{1}{3},\\ 0 & \text{if } x > -\frac{1}{3}. \end{cases}

plot(x, Jstar.(x), label="J*(x)")
vline!([-1/3],line=:dash)
xlabel!("x")
ylabel!("J*(x)")