Implications of Inverse Parametric Optimization in Model Predictive Control

Abstract

Recently, inverse parametric linear/quadratic programming problem was shown to be solvable via convex liftings approach [13]. This technique turns out to be relevant in explicit model predictive control (MPC) design in terms of reducing the prediction horizon to at most two steps. In view of practical applications, typically leading to problems that are not directly invertible, we show how to adapt the inverse optimality to specific, possibly convexly non-liftable partitions. Case study results moreover indicate that such an extension leads to controllers of lower complexity without loss of optimality. Numerical data are also presented for illustration.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Interest in parametric optimization algorithms for linear and quadratic programs has been resurged during the last 15 years, following the observation that certain optimal control problems for constrained systems can be solved explicitly offline. In particular, a lot of attention has been attracted by the fact that solutions to the traditional model predictive control problems can be obtained in an explicit formulation by exploiting the concept of parametric convex programming (pCP) [3–5, 19, 22]. This allows to pre-compute the optimal solution to a linear/quadratic programming problem for a range of operating conditions of interest as a piecewise affine (PWA) function defined over a polyhedral partition of the parameter space. The implementation effort of these so-called explicit MPC (eMPC) methods [1] hence reduces to a simple function evaluation, since the controller itself maps into a lookup table of linear gains. This property naturally circumvents the main implementation drawback of the standard implicit MPC, which is the need for online optimization in the receding horizon fashion at each sampling instant. Clearly, within the real-time requirements, the solutions may become too expensive or simply infeasible, namely in the case of systems with fast-evolving dynamics. On the other hand, the efficacy of the offline solution is limited to small-dimensional systems. Therefore the eMPC algorithms necessarily encounter computational difficulties as the parameter space dimension or the prediction horizon increases. Moreover, the resulting PWA controller is often too complex; hence, if allowable, its structure may need to be treated adequately to satisfy the restrictions imposed by the implementation hardware.

In view of handling linear MPC problems often emerging from practical applications, the parametric convex programming has grown into a mature technique providing a variety of numerical algorithms available for effective solution. Recently, the concept of inverse optimality has been shown to provide a new perspective on the structural link between linear MPC and pCP problem formulation via the technique of inverse parametric convex programming (IpCP). As the name suggests, it is defined as an inverse optimality problem of parametric convex programming. It aims to build an alternative optimization problem characterized by an appropriate constraint set and a cost function such that its optimal solution coincides with the one of the original problem. More specifically, the goal of inverse parametric linear/quadratic programming is to construct a linear constraint set and a linear/quadratic cost function such that the optimal solution of this newly formulated problem is equivalent to a given PWA function defined over a given polyhedral partition. This topic has been recently investigated in [2, 7, 13], and turned out to be applicable in the complexity reduction of piecewise affine control law design. This chapter closely follows the results put forward in [13, 14]. Therein, a constructive procedure based upon convex liftings is presented, leading to an important implication in MPC design, that can be stated as follows: every continuous piecewise affine control law can be recovered via an MPC problem with a control horizon at most equal to two prediction steps. Central to the approach is the operation of convex lifting, and the related liftability condition, which plays a crucial role in the existence of an inverse optimal solution.

The main aim of this study is to address the difficulty arising in applications of IpCP in linear MPC, namely that the explicit solution of a linear MPC problem with respect to a quadratic cost function is not, in many cases, convexly liftable. With regard to this issue, in [14] it was shown that, in fact, any parameter space partition associated with a solution of a pQP can be sub-partitioned such that its convex liftability will be guaranteed. In control theory, however, such a subdivision necessarily increases the complexity of PWA control laws, which is commonly urged to be kept as low as possible for the sake of efficient eMPC implementations. Therefore, herein we rather aim at devising an alternative, yet convenient approach that would target pQP-based MPC problems which are typically not directly invertible, without generating any gain in complexity of the inherited solution. To tackle this challenge, we recall the open question of minimal complexity of the inverse optimality formulation, discussed in [12]. It is known that the IpL/QP via convex liftings replaces the constraint set of linear MPC problem based on prediction along a finite horizon with mixed constraints on the control and state variables over two prediction stages. Nevertheless, the main advantage of a significant decrease in the dimension of optimization arguments tends to come at the price of a relatively large set of constraints. Since not all the constraints practically contribute to the optimal solution, an effort is being put into reducing the constraint set towards a minimal representation necessary for the inverse optimality formulation. We exploit this fact and present an algorithmic procedure tailored for the class of MPC problems of interest. At this point the contribution of the proposed extended IpLP approach is twofold as it simultaneously treats the issue of invertibility, preconditioned by convex liftability, and eliminates the redundant constraints from the formulation. The procedure, however, exactly retrieves only a part of the solution. To establish the equivalence of the remaining portion of controller structure we adopt the concept of clipping strategy proposed in [10]. This inverse optimality-based procedure is performance lossless, i.e., the retrieved PWA function inherits all the performance, closed-loop stability and feasibility guarantees of the pQP-based/online MPC solution.

As outlined earlier, the efficient implementation of eMPC, often using embedded platforms, is closely associated with the structure of the explicit controller. Since the PWA control law is defined over a set of polytopic regions, it is clear that if the number of regions becomes large, the storage capacity of the implementation hardware may be easily exceeded. To overcome these limitations, numerous methods for complexity reduction via simplifying eMPC optimizers have been proposed. This is usually achieved by devising less complex equivalent replacement functions of the original PWA feedback with no implications on optimality, or various sophisticated, albeit suboptimal, approximations. A brief, yet recent overview can be found, e.g., in [9, 11]. We recall this topic with regard to the third feature of the approach. As it will be evidenced later, the combination of extended IpLP with the use of a simple clipping filter [10] may find its use in case a low-complexity eMPC controller is sought. Nevertheless, this ability is not an objective of this study, rather an additional gain of the approach. Hence, when an online implementation is of interest and certain assumptions are fulfilled, the less complex, yet performance-wise optimal explicit representation can offer an important advantage. In particular, real-time implementation complexity is determined not only by the memory needed to store the controller, but also by the computational time necessary to find and evaluate the corresponding control law. This is of imminent importance when targeting embedded hardware or controlling fast systems. In this light, extended IpLP with clipping shows its potential use in practical MPC applications; in comparison with the generic convex liftings-based IpCP, which as such does not yield any computational benefits within online eMPC. On the contrary, the obtained explicit solution may in case of directly non-invertible problems become too complex and thus intractable. Additionally, the proposed inverse optimization formulation may be as well cast and solved as an online MPC problem which would shed more light on the merits of its cost/constraints rearrangement.

2 Notation and Definitions

Throughout this study, $\mathbb {R}$, $\mathbb {N}_{>0}$ are used to denote the set of real numbers, and the field of positive integers, respectively. For a compact notation, let us define the index set $\mathcal {I}_{N}:=\{i\in \mathbb {N}_{>0}\mid {i}\le {N}\}$, for a given $N\in \mathbb {N}_{>0}$. For a point $x\in \mathbb {R}^{d}$, by $\mathbb {R}^{n_{x}}$ we denote the vector space containing the point x, hence in this case $\mathbb {R}^{n_{x}}=\mathbb {R}^{d}$. Next, given a finite set $\mathcal {S}=\{x_{1},x_{2},\ldots ,x_{n}\}$ of n points, $\mathrm {Card}(\mathcal {S})$ denotes the cardinal number of the set $\mathcal {S}$. By $\mathrm {conv}(\mathcal {S})$ we denote its convex hull. Also, if $\mathcal {S}$ is a finite set of rays, i.e., $\mathcal {S}=\{ y_1, \ldots , y_n \}$ then $\mathrm {cone}(S)$ represents the cone defined as follows:

$$\begin{aligned} \mathrm {cone}(\mathcal {S}) = \{ t_1y_1 + \cdots + t_ny_n : \; t_i \ge 0,\, \forall 1 \le i \le n \} \end{aligned}$$

(3.1)

A polyhedron is defined as a convex intersection of finitely many closed half-spaces. A polytope is a bounded polyhedron. Given a full-dimensional polyhedron $\mathcal {S}$ in $\mathbb {R}^{d}$, then $\mathcal {V}(\mathcal {S})$ denotes the set of its vertices; $\mathcal {R}(\mathcal {S})$ denotes the set of its rays. Also, $\mathrm {int}(\mathcal {S})$ denotes its interior. $\mathrm {Proj}_{\mathbb {S}}\mathcal {S}$ represents the orthogonal projection of the set $\mathcal {S}$ onto a subspace $\mathbb {S}$ of $\mathbb {R}^d$. Further, a face of $\mathcal {S}$ is the intersection of $\mathcal {S}$ and one of its supporting hyperplanes. A face of dimension $d-1$ is called a facet. The set of all facets of polyhedron $\mathcal {S}$ is denoted as $\mathcal {F}(\mathcal {S})$. Given a function $\kappa (x)$, $\mathrm {dom}(\kappa (x))$ denotes its domain. In addition, given two sets $\mathcal {S}_1,\mathcal {S}_2 \subset \mathbb {R}^d,$ by $\mathcal {S}_{1}\oplus \mathcal {S}_{2}$ we denote their Minkowski sum defined as follows:

$$\begin{aligned} \mathcal {S}_{1}\oplus \mathcal {S}_{2}:=\left\{ {y}\in \mathbb {R}^{d}\mid \exists {x}_{1}\in \mathcal {S}_{1},x_{2}\in \mathcal {S}_{2}\,\,\text { s.t. }\,\,y={x}_{1}+{x}_{2}\right\} . \nonumber \end{aligned}$$

Next, let us recall some necessary definitions.

Definition 3.1

A collection of $N\in \mathbb {N}_{>0}$ full-dimensional polyhedra $\mathcal {X}_{i}\subset \mathbb {R}^{d}$, denoted as $\mathcal {X}=\left\{ \mathcal {X}_{i}\right\} _{i\in \mathcal {I}_N}$, is called a polyhedral partition of a polyhedron $\mathrm {\Omega }\subseteq \mathbb {R}^d$ if:

• (1) $\mathrm {\Omega }={\bigcup }_{i\in \mathcal {I}_{N}}\mathcal {X}_{i}$,

• (2) $\mathrm {int}(\mathcal {X}_{i})\cap \mathrm {int}(\mathcal {X}_{j})=\emptyset$ with $i\ne {j}$, $(i,j)\in \mathcal {I}_{{N}}^{2}$.

In addition, we refer to polyhedra $(\mathcal {X}_{i},\mathcal {X}_{j})$ as neighbours, or adjacent, if $(i,j)\in \mathcal {I}_{{N}}^{2}$, $i\ne {j}$ and $\mathrm {dim}(\mathcal {X}_{i}\cap \mathcal {X}_{j})=d-1$. If a polyhedral partition is a collection of polytopes, then it is called a polytopic partition. $\mathcal {X}_{i}$ are referred to as regions of the partition $\mathcal {X}$.

In this chapter, a cell complex is understood as a polyhedral partition whose facet-to-facet property [20] is fulfilled, meaning that any two neighbouring regions share a common facet. Note that a complete, more general definition of cell complex can be found in [6]. However, for simplicity, we restrict our attention to the property of interest.

Definition 3.2

Given a polyhedral partition $\mathcal {X}=\left\{ \mathcal {X}_{i}\right\} _{i\in \mathcal {I}_{N}}$ of a polyhedron $\mathrm {\Omega }\subseteq \mathbb {R}^d$, a convex lifting is described by the function $z:\mathrm {\Omega }\rightarrow \mathbb {R}$ with:

$$\begin{aligned} z(x)=a_{i}^{T}x+b_{i}~~~\text {for any}~x\in {\mathcal {X}}_{i}, \end{aligned}$$

(3.2)

and $a_{i}\in \mathbb {R}^{d}$, $b_{i}\in \mathbb {R}$, $\forall {i}\in \mathcal {I}_{N}$; such that the following conditions hold:

• (1) z(x) is continuous over $\mathrm {\Omega }$,

• (2) for each $i\in \mathcal {I}_{N}$, $z(x)>a_{j}^{T}x+b_{j}$ for all $x\in \mathcal {X}_{i}\setminus \mathcal {X}_{j}$ and all $j\ne {i}$, $j\in \mathcal {I}_{N}$.

According to Lemma 1 in [15], a polyhedral partition admitting a convex lifting is required to be a cell complex. Conversely, a cell complex is not necessarily convexly liftable. The necessary and sufficient conditions for a cell complex to be convexly liftable¹ are referred to [14] and the references therein.

Moreover, a convex lifting can be in fact seen as a convex surface composed of the convex lower boundary of a polyhedron in an augmented space. This particular polyhedron can be described by the following definition:

Definition 3.3

A given cell complex $\mathcal {X}=\{\mathcal {X}_{i}\}_{i\in \mathcal {I}_{N}}$ of a polyhedron $\mathrm {\Omega }\subseteq \mathbb {R}^d$ has an affinely equivalent polyhedron if there exists a polyhedron $\tilde{\mathcal {X}}\subset \mathbb {R}^{d+1}$ such that for each ${i}\in \mathcal {I}_{N}$:

• (1) $\exists {F}_{i}\in \mathcal {F}(\tilde{\mathcal {X}})$ satisfying: $\mathrm {Proj}_{\mathbb {R}^{d}}F_{i}=\mathcal {X}_{i}$,

• (2) if $\underline{z}(x)=\min \limits _{z}{z}$   s.t.  ${[x^{T}\,z]}^{T}\in \tilde{\mathcal {X}}$, then ${[x^{T}\,\underline{z}(x)]}^{T}\in {F}_{i}$ for $x\in \mathcal {X}_{i}$.

The second condition in Definition 3.3 implies that the set of facets of $\tilde{\mathcal {X}}$ at the lower values of z is exclusively considered. These lower facets $F_{i}$ build a convex surface in $\mathbb {R}^{d+1}$ known as the previously defined convex lifting, and their image via the orthogonal projection onto $\mathbb {R}^{d}$ recovers the cell complex $\mathcal {X}$.

We remark that an additional set of definitions is provided within Sect. 3.5 as it closely relates to the problems treated therein.

3 Inverse Parametric Optimization via Convex Liftings

This section aims to recall the constructive solution to the inverse parametric linear/quadratic programming problem via convex liftings. For ease of presentation, let us start from a larger perspective—with the definition of a parametric convex² programming problem, which can be cast as follows:

$$\begin{aligned} \begin{aligned} \min \limits _{\theta }&\quad {f}(\theta ,x)\\ \mathrm {s.t.}&\quad {g}_{i}(\theta ,x)\le {0},\,\,\forall {i}\in \mathcal {I}_p,\\&\quad {h}_{j}(\theta ,x)=0,\,\,\forall {j}\in \mathcal {I}_q, \end{aligned} \end{aligned}$$

(3.3)

where $\theta$, x denote the decision variable and the parameter, respectively. The terms $g_i(\theta ,x)$, $h_j(\theta ,x)$ represent the left-hand sides of respective inequality and equality constraints for the optimization problem (3.3).

In view of parametric linear/quadratic programming, the equality constraints are omitted for simplicity. Moreover, $g_i(\theta ,x),\,\forall {i}\in \mathcal {I}_p$ define linear constraints on $\theta$ and/or x, from the geometrical point of view representing a polyhedron in the augmented space of $\left[ \theta ^T\,\,x^T\right] ^T$. Still, $f(\theta ,x)$ stands for a linear or quadratic cost function, which has the following description:

$$\begin{aligned} f(\theta ,x)= \theta ^TH\theta + (F^Tx + Y)^T\theta , \end{aligned}$$

(3.4)

with a positive semidefinite matrix $H=H^T \succeq 0$ and appropriately dimensional matrices F, Y.

It is well known from the works of [4, 19, 22] that the optimal solution to a parametric linear/quadratic programming problem is a piecewise affine function defined over a polyhedral partition. It is shown therein that the optimal solution to a pQP problem with respect to $H \succ 0$ is continuous and unique. Otherwise, the continuity and the uniqueness properties may not be preserved for the case of a pLP. Fortunately, it is shown e.g., in [17] that an equivalently continuous optimal solution can always be selected. Therefore, the IpL/QP can focus on continuous PWA functions.

Given a continuous PWA function defined over a polyhedral partition, IpL/QP aims to find an appropriate optimization problem, characterized by a linear/quadratic cost function and a set of linear constraints such that the optimal solution to this optimization problem is equivalent to the given PWA function. Mathematically, let $f_{\mathrm {pwa}}(x):\mathrm {\Omega }\subseteq \mathbb {R}^{n_x}\rightarrow \mathbb {R}^{n_u}$ denote a continuous PWA function to be recovered, defined as follows:

$$\begin{aligned} f_{\mathrm {pwa}}(x)=F_{i}x+G_i \, \text { for } x\in \mathcal {X}_i. \end{aligned}$$

(3.5)

IpL/QP aims to find a cost function J(x, z, u) and a set of four matrices $H_x,H_u,$ $H_z, K$ such that:

$$\begin{aligned} f_{\mathrm {pwa}}(x) = \mathrm {Proj}_{\mathbb {R}^{n_u}} \mathrm {arg}\underset{\left[ z^{T}u^{T}\right] ^T}{\min } \, J(x,z,u) \,\, \text { s.t. } \,\, H_xx+H_zz+H_uu \le K, \end{aligned}$$

(3.6)

where z represents an auxiliary variable for the recovered optimization problem and will be shown to be a 1-dimensional variable.

Assumption 3.1

As reported in [13, 15], this inverse optimality problem is valid under the following standing assumptions:

• A1.1 The polyhedral partition $\mathcal {X}$ is the partition of a polyhedron $\mathrm {\Omega }$.

• A1.2 The polyhedral partition $\mathcal {X}$ is convexly liftable.

Note that Assumption A1.1 is of help in order to guarantee the convexity of the recovered optimization problem. On the other hand, Assumption A1.2 is not restrictive due to Theorem 2 and Lemma 2, also reported in [15]. Accordingly, if the given polyhedral partition does not satisfy Assumption A1.2, one can refine it such that the internal boundaries are maintained and the new partition is convexly liftable. Such subdivision will be discussed in more detail for the cases often encountered in MPC in Sect. 3.5.

As outlined in the introductory section, central to the constructive procedure of [13] is the operation of convex lifting for the given partition, recalled in Definition 3.2. An algorithm for the construction of convex liftings is referred to [14] and extended to a cell complex of a polyhedron via Theorem 1 in [15]. The following sets are also defined:

$$\begin{aligned} \begin{aligned} V_x&= \bigcup _{i \in \mathcal {I}_N} \mathcal {V}(\mathcal {X}_i),\, R_x = \bigcup _{i \in \mathcal {I}_N} \mathcal {R}(\mathcal {X}_i),\\ V_{\left[ x^T \,z\,\,u^T\right] ^T}&= \left\{ \left[ x^T \,z(x)\,\,f^T_{\mathrm {pwa}}(x)\right] ^T \mid x \in V_x \right\} , \\ R_{\left[ x^T \,z\,\,u^T\right] ^T}&= \left\{ \left[ r^T \,\, \hat{z}(r) \,\,\hat{f}^T(r)\right] ^T \mid r \in R_x,\,\, \begin{aligned}&\hat{z}(r)=a_{i}^{T}r \\&\hat{f}(r) = F_{i}r \end{aligned} \,\, \text { if } \,\, r\in \mathcal {R}(\mathcal {X}_i) \right\} , \\ \mathrm {\Pi }_v&= \mathrm {conv}(V_{\left[ x^T \,z\,\,u^T\right] ^T}),\, \mathrm {\Pi }_r = \mathrm {cone}(R_{\left[ x^T \,z\,\,u^T\right] ^T}), \\ \mathrm {\Pi }&= \mathrm {\Pi }_v \oplus \mathrm {\Pi }_r. \end{aligned} \end{aligned}$$

(3.7)

Following (3.7), recall that $V_x$, $R_x$ denote the sets of vertices and rays of the cell complex $\mathcal {X}$, respectively. Also, $V_{\left[ x^T \,z\,\,u^T\right] ^T}$, $R_{\left[ x^T \,z\,\,u^T\right] ^T}$ stand for the sets of augmented vertices and rays of $\mathcal {X}$, into $\mathbb {R}^{n_x+n_u+1}.$ Note, however, that under convex liftings, the augmented terms for a vertex are different from the one for a ray as shown in (3.7). More clearly, consider a vertex v and a ray r of region $\mathcal {X}_i$ in the cell complex $\mathcal {X}$. After embedding to the space of convex lifting, the augmented term corresponding to v is $a_{i}^{T}v+b_i.$ However, under this embedding, the augmented term of r becomes $a_{i}^{T}r$. The resulting constraint set $\mathrm {\Pi }$ is computed via the Minkowski sum of $\mathrm {\Pi }_v$ and $\mathrm {\Pi }_r$. This is basically due to Minkowski-Weyl theorem (see Corollary 7.1b in [18]).

Based on the above notation, we recall here the main result for IpL/QP problem via the following theorem.

Theorem 3.1

Given a continuous PWA function $f_{\mathrm {pwa}}(x),$ defined over a cell complex $\mathcal {X}=\left\{ \mathcal {X}_i \right\} _{i \in \mathcal {I}_N}$ satisfying Assumptions A1.1, A1.2, then $f_{pwa}(x)$ is the image via the orthogonal projection of the optimal solution to the following parametric linear programming problem:

$$\begin{aligned} \underset{\left[ z\,\,u^T\right] ^T}{\min }\, z \quad \text { subject to } \quad \left[ x^T \, z\,\, u^T\right] ^T \in \mathrm {\Pi }. \end{aligned}$$

(3.8)

For the proof of Theorem 3.1 we refer to Sect. 5 of [15]. Note, however, that as discussed in [12], not all constraints of $\mathrm {\Pi }$ are meaningful in (3.8). Many of them contribute to the construction of feasible region instead of building its optimal solution. Therefore, these constraints may need to be removed to simplify the optimization problem. Algorithms put forward in [12] can be effectively utilized to carry out this procedure.

We remark that this theorem is meaningful in the context of implicit MPC where it can help to overcome its computational limitations by implementing this alternative optimization approach and solving the LP³ (3.8) at each sampling time. In this study we rather exploit this concept for efficient explicit MPC implementations. This point is discussed in Sect. 3.5 and clarified via a case study in Sect. 3.6.

4 Application to Linear MPC Problems

This section aims to recall an important result of IpL/QP related to the linear model predictive control . Consider a discrete-time, linear invariant system:

$$\begin{aligned} x(k+1)=Ax(k) + Bu(k), \end{aligned}$$

(3.9)

where (A, B) is stabilizable. In MPC problems, a cost function is typically defined over a finite prediction horizon $N\in \mathbb {N}_{>0}$ as follows:

$$\begin{aligned} J(U,x(k))=\sum _{i=0}^{N-1}\ell _{i}(x_{k+i\mid {k}},u_{k+i\mid {k}})+V_{N}(x_{k+N\mid {k}}) \end{aligned}$$

(3.10)

where $x_{k+i\mid {k}}\in \mathbb {R}^{n_{x}}$ is the ($k+i$)-th prediction of the system state at time k, $u_{k+i\mid {k}}$ denotes the control action at time instant $k+i$, and $U={[u_{k\mid {k}}^{T},\ldots ,u_{k+N-1\mid {k}}^{T}]}^{T}$.

The $\ell _{i}(x_{k+i\mid {k}},u_{k+i\mid {k}})$ term of the objective represents a stage cost $\forall {i}\in \mathcal {I}_{N-1}\cup \{0\}$ and $V_{N}(x_{k+N\mid {k}})$ denotes the terminal penalty. Moreover, the state and control variables are typically required to satisfy constraints:

$$\begin{aligned} x_{k+i|k} \in \mathbb {X}, \, u_{k+i|k}\in \mathbb {U},\;\forall {i}\in \mathcal {I}_{N-1}\cup \{0\}, \; x_{k+N|k}\in \mathbb {X}_{f} \end{aligned}$$

(3.11)

with polyhedra $\mathbb {X}, \mathbb {U}$ containing the origin in their interior. A suitable terminal constraint set $\mathbb {X}_{f}\subset \mathbb {X}$ is considered to guarantee closed-loop stability.

A linear MPC problem thus aims to solve the following optimization problem:

$$\begin{aligned} \underset{U}{\min }\,J(U,x(k)) \quad \text { subject to } \quad (3.11) \end{aligned}$$

(3.12)

where the stage costs and the terminal cost tend to take one of the following forms:

• (1) 2-norm: $\ell _i(x_{k+i|k}, u_{k+i|k})=x^T_{k+i|k}Qx_{k+i|k} +u^T_{k+i|k}Ru_{k+i|k}$, $V_N(x_{k+N|k})=x_{k+N|k}^{T}Px_{k+N|k}$, where $Q=Q^T$ is a positive semidefinite matrix and R, P are symmetric, positive definite matrices,

• (2) $1/\infty$-norm: $\ell _i(x_{k+i|k}, u_{k+i|k})=\Vert Qx_{k+i|k} \Vert _p + \Vert Ru_{k+i|k} \Vert _p$, $V_N(x_{k+N|k})=\Vert Px_{k+N|k} \Vert _p,$ where $p = 1/\infty$ and Q, R, P are of appropriate dimension.

As shown in [3, 4], the optimal solutions of such linear MPC problems of modest size can be found explicitly by parametric linear/quadratic programming, as follows:

$$\begin{aligned} U^{*}=\text {arg}\,\underset{U}{\text {min}}\,J(U,x(k))~~\text {s.t.}~~GU\le {W}+Ex(k), \end{aligned}$$

(3.13)

where the control input sequence U is regarded as the decision variable, the current state x(k) represents the parameter, and G, W, E are appropriate matrices describing the constraints (3.11). In the implementation, the receding horizon MPC feedback becomes $u_{k}=\mathrm {Proj}_{\mathbb {R}^{n_{u}}}U^{*}$. This explicit solution to a linear MPC problem has a piecewise affine structure, and therefore it inherits also the properties of an inverse optimality problem recalled earlier. Based on this property, the main result in this section is summarized via the following theorem.

Theorem 3.2

The continuous explicit solution of a generic linear MPC problem with respect to a linear/quadratic cost function is equivalently obtained through a linear MPC problem with a linear cost function and the control horizon at most equal to two prediction steps.

Interested reader is further referred to [13] for the proof. Therein, numerical examples can also be found, illustrating the application of the generic inverse optimality solution to problems that are directly invertible. This allows one to recover the optimal explicit continuous feedback inherited from the linear MPC problem via an inverse pL/QP problem, while the structure of the PWA control law and the underlying parameter partition are maintained. The following section is going further and focuses on more realistic MPC scenarios where the convex liftability of the state-space partition is not a priori guaranteed, hence requiring to appropriately revisit the IpCP procedure in order to find an inverse problem formulation and its solution.

5 A Novel Approach for a Class of Primarily Non-invertible Control Laws Obtained from MPC Problems

As outlined in the introduction, we aim at recovering linear MPC problems whose explicit solution obtained by parametric convex programming leads to a convexly non-liftable parameter partition, which therefore may not be used within the generic IpCP scheme proposed in [13] where the authors build upon the assumption that the state-space partition to be recovered is a convexly liftable cell complex (cf. Definition 3.2). Here, we are, however, interested in situations when the partition inherited from the solution of an MPC problem is found to be a convexly non-liftable polyhedral partition or cell complex, eventually. As mentioned recently in [14], the parameter space partition associated with the optimal solution to a parametric quadratic programming problem, is in many cases not convexly liftable. We remark that this tends to be the case for most of practical set-ups involving input constraints, usually yielding explicit controllers with many saturated regions.⁴ One may observe that the larger their number is, the smaller the likelihood of constructing a convex lifting gets. In such a case, a straightforward scheme to approach this problem would be to rearrange the possibly disconnected and non-convex union of polyhedra sharing the same saturated control law, in a way to allow for convex liftability of the entire partition. Despite the existence of several region merging techniques, none of them can in fact guarantee this property. Even if we manage to remove the saturated regions completely, as per separation-based complexity reduction of [11], the collection of unsaturated polyhedra left to be lifted may very often be non-convex, which prevents us from constructing its affinely equivalent polyhedron while recovering the explicit controller without giving rise to some additional regions.

This problem may be as well treated by an appropriate sub-partitioning of a given convexly non-liftable polyhedral partition, as outlined recently in [14]. Therein, it is shown that any parameter space polyhedral partition associated with a solution of a pQP problem can be sub-partitioned such that its internal boundaries are preserved and the new cell complex is convexly liftable. Despite the new hyperplane arrangement allows the convex liftability to be retrieved, it naturally leads to a refining that can easily increase the complexity of a PWA feedback to a large extent. Implementation of such an eMPC controller may thus become a costly, if not intractable, alternative to the original one.

In view of the aforementioned practical aspects, let us now briefly formulate an extended inverse optimality problem to be tackled henceforth.

Problem 3.1

Given a, possibly, convexly non-liftable polyhedral partition/cell complex⁵ $\mathcal {R}=\left\{ \mathcal {R}_{i}\right\} _{i\in \mathcal {I}_{R}}$ of a polyhedron $\mathrm {\Omega }\subseteq \mathbb {R}^{n_{x}}$, associated with a continuous piecewise affine function $\kappa (x)=f_{\mathrm {pwa}}(x):\mathrm {\Omega }\rightarrow \mathbb {R}^{n_{u}}$, find a linear cost function J(x, z, u), and matrices $H_{x},H_{u},H_{z},K$ such that the inverse optimal solution

$$\begin{aligned} {\left\{ \begin{array}{ll} \tilde{\kappa }(x)=\mathrm {Proj}_{\mathbb {R}^{n_{u}}}\text {arg}\,\underset{{[z\,u^{T}]}^{T}}{\text {min}}J(x,z,u),\\ \quad \text {s.t.}~~H_{x}x+H_{z}z+H_{u}u\le {K}. \end{array}\right. } \end{aligned}$$

(3.14)

returns an equivalent replacement of $\kappa (x)$ when passed through a suitable filter $\phi (\cdot )$.

Assumption 3.2

At this point, some assumptions need to be stated to make the present approach reasonable from both the construction and practical viewpoint:

• A2.1 The parametric linear programming (pLP) problems are exclusively considered as possible candidates for the inverse optimality solutions.

• A2.2 $\mathcal {R}$ is the partition of a polytope $\mathrm {\Omega }$.

• A2.3 $\kappa (x)$ is the explicit optimal solution to a pQP-based linear MPC problem.

• A2.4 $\kappa (x)$ is partially saturated with the corresponding polytopic regions causing $\mathcal {R}$ to be convexly non-liftable.

Assumption A2.1 provides a manageable framework for the constructive inverse optimality procedures by imposing linearity of the candidate pCP problems. Although a quadratic cost function may be used as well, in the scope of this study an IpLP is of interest for brevity, yet with a straightforward extension towards IpQP. Meanwhile, Assumption A2.2 merely requires the feasible set to be a polytope, which is usual in the context of MPC. However, it is not restrictive, and the procedure can be easily extended to the case where the feasible set is a polyhedron. The other two assumptions stem from a more practical reasoning outlined at the beginning of this section. By Assumption A2.3 we focus our attention rather on explicit solutions obtained by parametric quadratic programming. Considering pQP in this context not only relates to the nature of most linear MPC problems, but it is mainly due to the typically inherent curse of direct non-liftability of the associated solutions, defined over convexly non-liftable state-space partitions.⁶ This is in contrast to pLP problems which are directly invertible without any refinement required [14], and also for this fact are not of interest here. The last assumption stems from numerous observations encountered in practical MPC problems where the explicit receding horizon feedbacks usually contain many regions for which the associated optimal control action is either constantly on the upper limit or constantly on the lower limit. This reasonable idea was also central to the works of [10, 11] aiming for complexity reduction of explicit MPC feedback laws. Recall that, in general, $\mathcal {R}$ inherited from a pQP may be convexly non-liftable since it is mostly a strict polyhedral partition, i.e., facet-to-facet property does not hold [20]; however, it may as well be a cell complex that is not convexly liftable simply due to the nature of its hyperplane arrangement (see e.g., the example in [15]). The second part of Assumption A2.4 moreover hints that the liftability issue is typically induced by the existence and structural properties of the collections of aforementioned saturated polytopic regions. This becomes more and more likely as the cardinality of such collections increases, at the price of the remaining collection of unsaturated regions, which is itself thus in a vast majority of cases found to be convexly liftable. In fact, as it is evidenced, e.g., in [10, 11], a typical explicit MPC feedback law contains a significantly smaller number of unsaturated regions as compared to the number of saturated ones. In addition, if the convex liftability of the collection of unsaturated regions, as invoked via Assumption A2.4, practically happened not to hold, it is still possible to use sub-partitioning to preserve it. With the usual structural proportions mentioned above, it would however become still very cheap compared to a complete partition refining—actually, as a matter of fact, such a possible slight increase in controller complexity would be most likely eliminated by a notable complexity reduction indicated by the approach proposed in the following subsection. Needless to say, no such an issue has been encountered within tested practical MPC scenarios, neither is it present in the case study put forward in Sect. 3.6.

To review the objective, by exploiting the procedure of inverse parametric optimization via convex liftings [13], we aim to reconstruct an appropriate linear programming problem (3.14) with respect to a given piecewise affine function $\kappa (x)$ defined over a given, possibly convexly non-liftable polyhedral partition/cell complex of the parameter space, $\mathcal {R}$, such that the optimal solution of this reconstructed problem is equivalent to the given PWA function. The equivalence requires that the boundary between two different regions of the parameter space partition corresponding to two different affine functions is preserved, whereas a proper rearrangement of the subset of the domain of definition, over which the PWA function is saturated, is allowable. This property is effectively exploited within this study. An example is the new convexly liftable cell complex $\tilde{\mathcal {R}}$ corresponding to a structurally modified, yet optimal PWA solution function $\phi (\tilde{\kappa }(x))$, as shown in Sect. 3.5.

The following subsections present the main contribution of this study—the extension to convex liftings-based inverse parametric convex programming procedure, namely IpLP, with the main focus on a wide and challenging class of primarily non-invertible linear MPC problems having the explicit optimal solution in the form as per Assumption 3.2.

5.1 Additional Notation and Definitions

Let us now append some necessary notation, related closely to the topic treated in this section. We first state a set of definitions found to be useful and hence adopted from [10] to keep the notation compact. To make the further explanation more clear, we restrict ourselves to single-input systems (cf. Remark 3.2).

Definition 3.4

Let $\overline{\kappa }$ and $\underline{\kappa }$ denote, respectively, the maximum and minimum values which the PWA function $\kappa (x):=f_{i}^{T}x+g_{i}$ attains over $\mathrm {dom}(\kappa (x))$. Denote by $\mathcal {I}_{\mathrm {max}}$ ($\mathcal {I}_{\mathrm {min}}$) the index set of regions where $\kappa (x)$ is saturated at the maximum (minimum), and let $\mathcal {I}_{\mathrm {sat}}=\mathcal {I}_{\mathrm {max}}\cup \mathcal {I}_{\mathrm {min}}$. We call a region $\mathcal {R}_{i}$ the saturated region if it is either saturated at the minimum or at the maximum, i.e., if $i\in \mathcal {I}_{\mathrm {sat}}$. Otherwise the region is called unsaturated. The index set of unsaturated regions is denoted by $\mathcal {I}_{\mathrm {unsat}}$.

Definition 3.5

Given a continuous PWA function $\kappa (x)$, defined over the parameter space partition $\mathcal {R}=\left\{ \mathcal {R}_{i}\right\} _{i=1}^{R}$, we call the PWA function $\tilde{\kappa }(x):=\tilde{f}_{j}^{T}x+\tilde{g}_{j}$ a suitable augmentation of $\kappa (x)$ if the following properties hold:

• P1: $\tilde{\kappa }(x)$ is defined over partition $\tilde{\mathcal {R}}=\{\tilde{\mathcal {R}}_{j}\}_{j=1}^{\tilde{R}}$ such that $\bigcup _{j\in \mathcal {I}_{\tilde{R}}}\tilde{\mathcal {R}}_{j}=\bigcup _{i\in \mathcal {I}_{R}}\mathcal {R}_{i}$, i.e., $\mathrm {dom}(\tilde{\kappa }(x))=\mathrm {dom}(\kappa (x))$.

• P2: $\tilde{\kappa }(x)=\kappa (x),\;\forall {x}\in \mathcal {R}_{\mathcal {I}_{\mathrm {unsat}}}$.

• P3: $\tilde{\kappa }(x)\ge \overline{\kappa },\;\forall {x}\in \mathcal {R}_{\mathcal {I}_{\mathrm {max}}}$.

• P4: $\tilde{\kappa }(x)\le \underline{\kappa },\;\forall {x}\in \mathcal {R}_{\mathcal {I}_{\mathrm {min}}}$.

In addition, we introduce several polyhedral operations, which were shown to be convenient in the context of IpCP complexity analysis [12], and are utilized here to clarify the algorithmic notation.

Given a full row rank matrix $M\in \mathbb {R}^{r\times (d+1)}$, by $\mathcal {P}(M)$ we denote the polyhedron

$$\begin{aligned} \mathcal {P}(M)=\{x\in \mathbb {R}^{d}\mid {M}(\cdot ,1:d)x\le {M}(\cdot ,d+1)\}, \end{aligned}$$

where $M(\cdot ,i)$ denotes the $i{\text {th}}$ column of the matrix M and $M(\cdot ,i:j)$ represents the matrix composed by the $i{\text {th}}$–$j{\text {th}}$ columns of M. Conversely, given a polyhedron $\mathcal {P}$, by $\mathcal {P}^{-1}(P)$ we denote the minimal representation (in terms of dimension) of a matrix M satisfying $P=\{x\in \mathbb {R}^{d}\mid {M}(\cdot ,1:d)x\le {M}(\cdot ,d+1)\}$. Note that $\mathcal {P}^{-1}(P)$ is not unique due to the following observation: $\mathcal {P}(M)=\mathcal {P}(\alpha {M}),\alpha >0$.

For ease of presentation let us also define an operator for removal of redundant constraints. Given two sets of constraints corresponding to two polyhedra $P_{M}$, $P_{N}$, $M\in \mathcal {P}^{-1}(P_{M})\subset \mathbb {R}^{r_{M}\times (d+1)}$, $N\in \mathcal {P}^{-1}(P_{N})\subset \mathbb {R}^{r_{N}\times (d+1)}$, by $\mathrm {RmRdd}(M,N)$ we denote the set of constraints characterizing $P_{M}$ which are not redundant in the representation of $P_{N}$. We remark that there exist numerous algorithms for removing redundant constraints. Herein, we recall the one presented in [16] through a mathematical description as follows: $\mathrm {RmRdd}(M,N)=K\in \mathbb {R}^{r_{K}\times (d+1)}$ s.t.

• K is a sub-block of M,

• for any $i\in \mathcal {I}_{r_{K}}$, $\underset{x\mid {x}\in {P}_{N}}{\mathrm {max}}K(i,1:d)x>K(i,d+1)$.

In addition, for $P_{M}\subseteq {P}_{N}$, $M\in \mathcal {P}^{-1}(P_{M})$, $N\in \mathcal {P}^{-1}(P_{N})$, $\mathrm {RmRdd}(N,M)=\emptyset$.

5.2 Extended Convex Liftings-Based Inverse pLP with Clipping

In this subsection we show how to recover solutions to a given class of MPC problems via another reformulated IpLP-based MPC problem with the prediction horizon equal to two prediction steps while preserving optimality.

Given a convexly non-liftable polyhedral partition/cell complex $\mathcal {R}=\left\{ \mathcal {R}_{i}\right\} _{i\in \mathcal {I}_{R}}$, the proposed procedure exploits the possibly non-convex collection of unsaturated regions, $\mathcal {R}_{\mathcal {I}_{\mathrm {unsat}}}$, which is assumed to be convexly liftable (recall Assumption A2.4 and related comments). The first step is hence to find the gains $(a_{i},b_{i}),\forall {i}\in \mathcal {I}_{\mathrm {unsat}}$ of its associated convex lifting. This can be carried out efficiently by using the constructive procedure (Algorithm 3.1 in [15]) first proposed in [14], yielding $z(x)=a_{i}^{T}x+b_{i}$, with $x\in \bigcup _{i\in \mathcal {I}_{\mathrm {unsat}}}\mathcal {R}_i$. Further, instead of constructing an affinely equivalent polyhedron, we build the vertex set $V_{{[x^{T}z\,u^{T}]}^{T}}^{\mathrm {unsat}}$ and compute its dual, half-space representation $\mathrm {\Pi }_{{[x^{T}z\,u^{T}]}^{T}}^{\mathrm {unsat}}=\mathrm {conv}(V_{{[x^{T}z\,u^{T}]}^{T}}^{\mathrm {unsat}})$ as per Theorem 5.3 in [13], slightly modified for our case. This polytope is to be used to construct a constraint set for Problem 3.1 by extending the given convex lifting and control law over the saturated regions.

As outlined in the introduction, for the further course of this study we exploit the question of minimal complexity of the inverse optimality formulation, discussed in [12]. In particular, not all the constraints—defining half-spaces of the set $\mathrm {\Pi }_{{[x^{T}z\,u^{T}]}^{T}}$ within the generic IpCP problem formulation are meaningful from the optimization point of view, in the sense that they are not active at the optimum. Therefore, it is sufficient to exclusively consider only the active constraints, which are defined by corresponding supporting hyperplanes containing certain facets of $\mathrm {\Pi }_{{[x^{T}z\,u^{T}]}^{T}}$. We adopt this idea to preserve the active constraints which are thus not redundant in the half-space representation of $\mathrm {\Pi }_{{[x^{T}z\,u^{T}]}^{T}}^{\mathrm {unsat}}$. Such a relaxation naturally modifies this set in both parameter and argument space; hence it needs to be associated with an appropriate restriction in the parameter space, which bounds the domain of validity for the optimal solution. This procedure is summarized in Algorithm 3.1.

Remark 3.1

Note that the explicit solution ${[\underline{z}\,\underline{u}^{T}]}^{T}$ required as input for Algorithm 3.1 is known a priori with respect to a given continuous PWA function and constructed convex lifting associated with $\mathcal {R}_{\mathcal {I}_{\mathrm {unsat}}}$, without the need to solve the minimization problem. Step 8 is present to avoid the redundancy phenomena while adding supplementary constraints given by $\overline{M}_{\mathrm {f}}$. In addition, we remark that for the MPC control laws designed with the feasible set $\mathrm {\Omega }=\mathrm {conv}(\mathcal {R})$ to be positively invariant, these constraints (Steps 6-9) can be further omitted as long as the initial state $x_{0}\in \mathrm {\Omega }$. This may reduce the complexity of the formulation in implicit MPC implementations.

This algorithmic procedure first retrieves the minimal half-space representation of the set $\mathrm {\Pi }_{{[x^{T}z\,u^{T}]}^{T}}^{\mathrm {unsat}}$, potentially useful for the IpCP problem formulation, and given by an unbounded polyhedron $\mathrm {\Pi }_{\mathrm {min}}$ (Steps 1–6). Feasibility of this set is further provided through a restriction imposed on its parameter subspace (Step 7). Additional redundant constraints that may emerge at this point are effectively removed via Step 8. The resulting constraint set is thus given by $\tilde{\mathrm {\Pi }}$ (Step 10). Now, recall that, geometrically, each active constraint corresponds to a hyperplane of dimension $n_{x}+n_{u}$. Therefore, we are interested in the constraints corresponding to the supporting hyperplanes of $\tilde{\mathrm {\Pi }}$ which contain the $n_{x}$-faces whose orthogonal projection onto $\mathbb {R}^{n_{x}}$ retrieves the parameter space partition $\mathcal {R}$ associated with the optimal PWA function $\kappa (x)$. This is indeed not quite the case here, since $\mathrm {Proj}_{\mathbb {R}^{n_{x}+n_{u}}}\tilde{\mathrm {\Pi }}$ (or $\mathrm {Proj}_{\mathbb {R}^{n_{x}+1}}\tilde{\mathrm {\Pi }}$—affinely equivalent polyhedron to $\tilde{\mathcal {R}}$) is formed as a convex extension of $\mathrm {Proj}_{\mathbb {R}^{n_{x}+n_{u}}}\mathrm {\Pi }_{{[x^{T}\underline{z}\,\underline{u}^{T}]}^{T}}^{\mathrm {unsat}}$ ($\mathrm {Proj}_{\mathbb {R}^{n_{x}+1}}\mathrm {\Pi }_{{[x^{T}\underline{z}\,\underline{u}^{T}]}^{T}}^{\mathrm {unsat}}$, respectively) over $\bigcup _{i\in \mathcal {I}_{\mathrm {sat}}}\mathcal {R}_{i}$, bounded by the restriction in the parameter space $\mathbb {R}^{n_{x}}$ imposed by the feasible set $\mathrm {\Omega }=\mathrm {dom}(\kappa (x))$. It follows that the explicit optimal solution ($\tilde{\kappa }(x)$, $\tilde{\mathcal {R}}$) to thusly cast “inverse” problem is not equivalent anymore, in the sense that $\tilde{\kappa }(x)$ does not coincide with the original PWA feedback $\kappa (x)$, namely in its saturated portions defined over $\mathcal {R}_{\mathcal {I}_{\mathrm {sat}}}$. The cell complex $\tilde{\mathcal {R}}$ in this way inherits a collection of regions with similar (or equivalent, if $\bigcup _{i\in \mathcal {I}_{\mathrm {unsat}}}\mathcal {R}_{i}$ is convex) partitioning as $\mathcal {R}_{\mathcal {I}_{\mathrm {unsat}}}$.

The following theorem summarizes the minimal formulation of an extended IpLP problem resulting directly from Algorithm 3.1.

Theorem 3.3

The image via orthogonal projection onto $\mathbb {R}^{n_{u}}$ of the optimal solution to the following optimization problem

$$\begin{aligned} {{\min \limits _{{[z\,u^{T}]}^{T}}}\quad {z}\quad \mathrm {s.t.}\quad {[x^{T} z\,u^{T}]}^{T}\in {\tilde{\mathrm {\Pi }}}} \end{aligned}$$

(3.15)

where $\tilde{\mathrm {\Pi }}$ is obtained from Algorithm 3.1, is a suitable augmentation of the given continuous PWA function $\kappa (x):\mathrm {\Omega }\rightarrow \mathbb {R}^{n_{u}}$, denoted as $\tilde{\kappa }(x)$ and associated with a convexly liftable cell complex $\tilde{\mathcal {R}}=\lbrace \mathcal {\tilde{R}}_{j}\rbrace _{j\in \mathcal {I}_{\tilde{R}}}$.

Proof

Follows directly from Algorithm 3.1 and from Definition 3.5 of $\tilde{\kappa }(x)$.    $\square$

As implied by Theorem 3.3, solution of LP (3.15) renders a suitable augmentation $\tilde{\kappa }(x)$ of the original piecewise affine function $\kappa (x)$. The augmented function, however, cannot be readily applied as an explicit receding horizon MPC feedback since, in general, $\tilde{\kappa }(x)\ne \kappa (x)$ for $x\in \mathcal {R}_{\mathcal {I}_\mathrm {sat}}$. Therefore, to achieve the equivalence of the two, we adopt the concept of a simple clipping filter proposed in [10], and recalled here as follows:

Theorem 3.4

([10]) Consider a saturated continuous PWA function $\kappa (x)$ and its suitable augmentation $\tilde{\kappa }(x)$ obtained per Theorem 3.3. Let

$$\begin{aligned} \phi (\tilde{\kappa }(x)):=\max \left\{ \underline{\kappa },\min \left\{ \tilde{\kappa }(x),\overline{\kappa }\right\} \right\} \end{aligned}$$

(3.16)

Then the equivalence $\phi (\tilde{\kappa }(x))=\kappa (x)$ is established for all $x\in {\mathrm {dom}}(\kappa (x))$.

Proof

Straightforward with respect to Definition 3.5; can be found in [10].    $\square$

Remark 3.2

As outlined in Sect. 3.5.1, the above derived procedure is clearly valid for single-input systems. However, the dimension of $\kappa (x)$ in Problem 3.1 is not necessarily equal to 1, in fact, it can be extended for the case when $\kappa (x)$ is a vector-valued function with $n_{u}>1$. In that case, Definitions 3.4, 3.5, and Theorem 3.4 need to be slightly modified in an adequate manner to account for this fact; for more details see [10].

Finally, in Algorithm 3.2 we summarize the proposed constructive IpLP-based procedure towards recovering a suitable augmentation of a given continuous piecewise affine function, which when passed through a clipping filter represents the solution to Problem 3.1.

6 A Case Study with Implication in Low-Complexity eMPC

The main aim of this section is to illustrate the proposed constructive procedure via a case study MPC problem. It is shown that by executing all the steps of Algorithm 3.2, i.e., formulating and solving an extended IpLP problem with clipping, we obtain a performance-lossless replacement of the receding horizon MPC feedback associated with the original control problem. In addition, we perform an analysis to assess the computational complexity of the scheme as well as the structural complexity of the recovered eMPC controller.

The example is taken from an active vibration control task [21], where the objective is to attenuate vibrations of a flexible cantilever beam, described by the following experimentally identified state-space model:

$$\begin{aligned} \begin{aligned} x(k+1)&= \begin{bmatrix} 0.867&1.119\\ -0.214&0.870 \end{bmatrix} x(k)+ \begin{bmatrix} 9.336{{\textsc {e}}-}4\\ 5.309{{\textsc {e}}-}4 \end{bmatrix} u(k)\\ y(k)&= \begin{bmatrix} -0.553&-0.705 \end{bmatrix} x(k) \end{aligned} \end{aligned}$$

(3.17)

where the output of the model is the beam tip deflection in $\mathrm {mm}$, and the input is the direct actuator voltage in $\mathrm {V}$. Control inputs required to steer the system (3.17) into equilibrium can be computed by solving the following optimization problem:

$$\begin{aligned} \begin{aligned} \min \limits _{u_{0},\ldots ,{u}_{N-1}}&x_{N}^{T}P{x}_{N}+\displaystyle \sum _{k=0}^{N-1}\left[ x_{k}^{T}Qx_{k}+Ru_{k}^{2}\right] \\ \mathrm {s.t.}&x_{0}=x(k)\\&x_{k+1}=Ax_{k}+Bu_{k},{k}=0,\ldots ,N-1\\&u_k\in \mathbb {U},{k}=0,\ldots ,N-1\\&x_N\in \mathbb {X}_{f} \end{aligned} \end{aligned}$$

(3.18)

subject to constraints $\left| u_{k}\right| \le {120}\,\mathrm {V}$. The MPC problem (3.18) was formulated with $Q=C^{T}C$, $R=1{{\textsc {e}}-}4$, and P and $\mathbb {X}_{f}$ designed such that closed-loop stability is guaranteed, i.e., by setting P to the solution of DARE and using a positive control invariant terminal set $\mathbb {X}_{f}$. Next, it was recast and solved as a pQP. The explicit MPC feedback $\kappa (x)$ for different horizon lengths N was obtained using MPT Toolbox [8]. Each resulting PWA solution $u_{0}^{*}(x)=\kappa (x)$ was subsequently post-processed using the extended IpLP procedure described by Algorithm 3.2.

Table 3.1 reports the results obtained by the proposed extended IpLP procedure, marked by ($\cdot$b), compared to the standard explicit solution via parametric quadratic programming, denoted as ($\cdot$a), used for the solution of (3.18) for different lengths of prediction horizon $N\in \{10,20,30,40,50\}$. The complexity of the IpLP-based scheme is expressed in terms of the number of regions of the resulting eMPC controller, and the number of constraints (half-spaces defining the constraint set $\tilde{\mathrm {\Pi }}$) in LP (3.15). As an example, the standard MPC problem needs 90 constraints with the horizon of length 40 to obtain the PWA control law shown in Fig. 3.1, while the formulation of IpLP with clipping requires 641 constraints (551 non-redundant “general” constraints and additional 90 constraints to conserve the solution’s structure) and exactly two prediction steps to yield the same result, see Fig. 3.2. Moreover, one may also notice the complexity reduction in the number of polytopic regions of the underlying state-space partition. In this particular case, the recovered partition consists of 814 regions instead of 3397 regions of the original partition, which corresponds to the reduction by a factor of more than four.

Table 3.1 Selected data comparing equivalent (in terms of the resulting feedback law) formulations of the case study MPC problem for different lengths of prediction horizon N

Fig. 3.1

Surface plot of the explicit MPC control law we aim to recover (3397 regions, $N=40$)

Fig. 3.2

Surface plot of the recovered eMPC controller (811 regions, $N=2$). Result of the clipping procedure is shown in orange colour (illustration only)

The total memory footprint of the original function $\kappa$ for the investigated scenario with 3397 regions is 408 kB. The recovered function $\tilde{\kappa }$, on the other hand, requires 105 kB, with additional 16 bytes to store the clipping filter $\phi (\cdot )$. This indicates reduction of memory consumption by a factor of 3.8. The worst-case computational effort needed to evaluate $\kappa$ is 54332 FLOPs, which can be by employing $\tilde{\kappa }$ reduced, adequately, to 14278 FLOPs (14272 FLOPs to perform point location by sequential search and 6 FLOPs to evaluate $\phi (\tilde{\kappa }(x))$).

Table 3.2 Remark on computation times of the main algorithmic features for the respective formulation of the case study MPC example

To review the complexity also from another practical point of view, Table 3.2 reports the CPU times spent on main algorithmic routines of the proposed extended IpCP approach and its generic pCP counterpart. The total time of the former may be split among four consecutive parts, in fact, represented by Steps 2 to 5 of Algorithm 3.2. Clearly, the last two steps represent the computationally most demanding procedures, which also scale more significantly as N increases. However, when summed up, the algorithmic features of extended IpCP, including the core pLP itself, are still shown to require less offline time than the original explicit solution (pQP).

Remark 3.3

Note that the two approaches may only be compared in terms of memory consumed by storage of the polyhedral partition along with the associated PWA function, or eventually the time required for online evaluation of the controller—both reduced here w.r.t. the data in Table 3.1. However, this is not the case for the offline pre-processing time spent on solving the respective pCPs since the entire IpCP procedure assumes the existence of the original explicit controller. Yet, such a study can shed more light on computational effort of the proposed approach with respect to the generic one, and in this way allow to analyse its viability.

Finally, we present a brief illustration of the aforementioned results. In particular, Fig. 3.1 shows the explicit optimal solution to the receding horizon MPC problem (3.18) for $N=40$. The optimal feedback takes form of a continuous PWA function $\kappa (x)$ defined over a state-space partition $\mathcal {R}$. This cell complex is not convexly liftable due to the hyperplane arrangement of the two large collections of polytopes representing the controller regions over which $\kappa (x)$ is saturated at $\overline{\kappa }$ or $\underline{\kappa }$. This solution thus presents a candidate for the extended IpLP scheme. Following the algorithmic procedure presented in Sect. 3.5.1 we obtain the solution of an extended inverse MPC problem with $N=2$, which is the PWA function $\tilde{\kappa }(x)$ depicted in Fig. 3.2. It is defined over a similar recovered partition $\tilde{\mathcal {R}}$, which is a convexly liftable cell complex. The optimality of $\tilde{\kappa }(x)$ over its entire domain of validity is achieved by passing it through a simple clipping filter $\phi (\cdot )$.

The resulting low-complexity feedback law can be readily and conveniently used within online/offline explicit MPC implementations while preserving all the performance, closed-loop stability and feasibility properties. We note that the proposed approach may be analogously exploited in implicit MPC schemes, at each sampling instant solving the equivalent “horizon 2” problem with the constraint set $\mathrm {\Pi }_{\mathrm {min}}$ (cf. Remark 3.1); hence revealing the full potential efficiency of the convex liftings-based inverse optimality approach in practical model predictive control applications.

7 Conclusion

The chapter presents an approach exploiting the inverse parametric convex programming based upon the concept of convex lifting. As shown recently, for any continuous PWA function defined over a polyhedral partition, one may find an appropriate equivalent function by solving another parametric linear/quadratic programming problem with a supplementary variable of dimension equal to 1. Applying this idea to the model predictive control framework allowed to further state that any linear MPC formulation has an equivalent inverse reformulation with two steps of the prediction horizon. This study, in particular, deals with the invertibility of the PWA functions resulting from pQP optimization problems, which is in fact seldom guaranteed due to its structural properties. Despite being already proven that this issue can always be treated by a suitable sub-partitioning of the corresponding parameter space partition, herein the emphasis has been put mainly on devising a technique which would not increase the controller’s explicit representation in terms of the polytopic regions. On the contrary, an algorithmic extension to the inverse parametric linear programming is presented, which in addition to the primary objective—to allow to target a class of common practical problems yielding convexly non-liftable cell complexes containing saturated regions, emerged to be capable of producing a lesser number of regions. This implies an expected applicability of the proposed scheme within implementations of explicit MPC, as compared to the generic convex liftings-based IpCP. It is evidenced by the presented numerical analysis which suggests that the inverse optimality concept applied to a complex but computable eMPC may lead to a lower complexity explicit control law. Subject of ongoing research remains the investigation of complexity bounds for the inverse optimality formulation. Apart from a valuable theoretic insight, the clarification of this topic shall yet improve computational tools necessary to fully exploit the efficacy of this control design approach.