Harnessing Data for Accelerating Model Predictive Control by Constraint Removal

We consider a discrete-time linear time-invariant (LTI) system:

where $x_{k}\in\mathbb{R}^{n}$ and $u_{k}\in\mathbb{R}^{m}$ denote the states and the inputs, respectively, at discrete time $k\in\mathcal{N}$. $A\in\mathbb{R}^{n\times n}$ and $B\in\mathbb{R}^{m\times m}$ are known system matrices. The system is subject to polyhedral state and input constraints:

where $C\in\mathbb{R}^{c\times n},\ D\in\mathbb{R}^{c\times m},\ E\in\mathbb{R}^{c}$ and origin is in the interior of $\mathbb{L}$.

Based on the system dynamic (1) and the constraints (2), an MPC over a finite time horizon of length $T\leq 1$, given the state $x_{k}$ at time $k\in\mathbb{N}$, can be formulated as

where

Here, $x_{.|k},u_{.|k}$ denote the predicted state and the predicted input. $J(x_{.|k},u_{.|k})$ is composed of the stage cost and the terminal cost where the weights $Q,R,P$ are symmetric positive definite matrices. The constraint $\mathbb{X}_{T}=\{x\ |\ C_{T}x\leq E_{T}\}$ is the terminal constraint.

Let $u^{*}_{.|k}$ be the solution of (3). Then, the first input is applied to the system:

The optimization (3) can be expressed as a standard multiparameter quadratic programming (mp-QP) form by regarding $x$ as the parameter vector:

where $x\in\mathbb{R}^{n}$ is the current state, $H\in\mathbb{R}^{n_{z}\times n_{z}},F\in\mathbb{R}^{n\times n_{z}},G\in\mathbb{R}^{n_{c}\times n_{z}},W\in\mathbb{R}^{n_{c}},S\in\mathbb{R}^{n_{c}\times n}$ are parameter matrices which are obtained from $Q,R,P,A,B,C,D,E,C_{T},E_{T}$. We denote an optimal solution to (6) by $z^{*}(x)$. The set of indices of the active constraints responding to $x$ is denoted by $\mathcal{A}(x)$.

If mp-QP has many constraints in (6b), then it is challenging and time-consuming to solve this optimization problem. One approach to reduce computational burden is to remove some redundant constraints.

Nouwens et al. [12] proposed a online constraint removal framework for linear system, called constraint-adaptive MPC. Specially, his method introduced the reduced MPC problem which have fewer constraints compared to the original MPC problem. The mp-QP version of the reduced MPC problem is formulated as follows:

where we define the mapping $\mathbb{I}:\mathbb{R}^{n}\rightrightarrows\mathbb{N}_{[1,n_{c}]}$ from the state space to the indices set of reduced constraints. $z^{*}(x,\mathbb{I}(x))$ denote the optimal solution of (7).

To guarantee that the optimal solution to (7) is the same as that to (6), Nouwens et al. [12] build upon the theorem as follows:

In Lemma 1, $\mathcal{M}(x)$ is regarded as the outer approximation of $z^{*}(x,\mathbb{I}(x))$. This approximation can be obtained by some information about the optimal solution (e.g., reachability and optimality [12]).

The way to apply the Lemma 1 is to first construct the outer approximation $\mathcal{M}(x)$ of $z^{*}(x,\mathbb{I}(x))$ for all possible choices of $\mathbb{I}$. Then, the indices in $\mathbb{C}(x)$ are selected such that (8b) is satisfied. Finally, constraints in $\mathbb{C}(x)$ are removed to formulate the reduced mp-QP problem (7). As shown in Fig. 1, $\mathcal{M}(x)$ is in the half-space formed by $\mathbb{C}(x)$ and contained by $\mathbb{Z}(x,\mathbb{C}(x))$. In this case, the constraints specified by $\mathbb{C}(x)$ can be removed directly without changing the optimal solution, i.e. $z^{*}(x,\mathbb{I}(x))=z^{*}(x)$. Thus, the design of outer approximation $\mathcal{M}(x)$ is essential, and a good approximation leads to efficient constraint removal. In this paper, we are interested in the following problem:

Consider a mp-QP problem with constraints selected by $\mathbb{I}$ which has no relation with the state x compared to (7):

Here, we denote the optimal solution of (9) by $z^{*}_{\mathbb{I}}(x)$. For each $\mathbb{I}$, there exists a $\kappa_{\mathbb{I}}$ [6] such that

The Lipschitz constant $\kappa_{\mathbb{I}}$ depends on $\mathbb{I}$. It is hard to compute the Lipschitz constant $\kappa_{\mathbb{I}}$ unless the explicit law is known [15]. In fact, the explicit law is intractable for large-scale system. In our cases, we need to calculate the maximum Lipschitz constant of mp-QP in different $\mathbb{I}$, i.e., $\kappa_{\text{max}}=\max_{\mathbb{I}\subseteq\mathbb{N}_{[1,n_{c}]}}\kappa_{\mathbb{I}}$. As far as we know, no methods can calculate this constant efficiently. To address this problem, we provide an explicit form for $\kappa_{\text{max}}$ with very low computational cost as follows:

Theorem 1 provides an efficient computing method for the Lipschitz constant. Its computation includes matrix multiplication and matrix norm. Let us analyze the computation complexity of the matrix norm. Here, we are interested in the mp-QP that exists many constraints, i.e., $n_{c}\gg n+n_{z}$. For a matrix $X\in\mathbb{R}^{a\times b}$, its matrix norm $\|X\|_{2}=\sqrt{\lambda_{1}(XX^{T})}=\sqrt{\lambda_{1}(XX^{T})}$. The computation complexity per step of $\lambda_{1}(XX^{T})$ and $\lambda_{1}(X^{T}X)$ with power iteration methods are $\mathcal{O}(a^{2})$ and $\mathcal{O}(b^{2})$, respectively. So the computation complexity of $\|X\|_{2}$ is $\mathcal{O}(a^{2})(a<b)$ or $\mathcal{O}(b^{2})(a>b)$. The dimensions of three matrix in (12) to compute norm are $n_{z}\times n$, $n_{z}\times n_{z}$ and $n_{c}\times n$. Although $n_{c}\gg n+n_{z}$, the computation complexity of matrix norm in (12) is $\mathcal{O}(n^{2}+n_{z}^{2})$ and are not influenced by the number $n_{c}$ of constraints.

This upper bound in Theorem 1 may be not close. To decrease the gap, we can utilize some techiques to find a smaller value $\kappa_{\text{max}}$. Let $\Phi\in R^{n_{c}\times n_{c}}$ be a full-rank matrix. We substitute $G,W,S$ with $\Phi G,\Phi W,\Phi S$ in (6b) and the feasible region and the optimal solution are not changed. The variant of (12) is obtained:

Equation (13) can be used as the Lipschitz constant in (11). We can select the appropriate matrix $\Phi$ to find a smaller value $\hat{\kappa}_{\text{max}}$ than $\kappa_{\text{max}}$ in (12). In Section IV, we provide a empirical approach to choose $\Phi$.

We now utilize the Theorem 1 to construct the outer approximation $\mathcal{M}(x)$. Then, we propose the ca-MPC scheme based on the mapping $\mathbb{I}$ computed by $\mathcal{M}(x)$.

We present the key lemma used in the design of $\mathcal{M}(x)$:

In Lemma 2, we consider $x_{1}=x$ as the current state and $x_{2}=\tilde{x}$ as a historical state. Let reduced constraint indices $\mathbb{I}(x)$ satisfy $\mathcal{A}(\tilde{x})\subseteq\mathbb{I}(x)$:

where

Equation (19) indicates that $\mathcal{M}(x)$ is a sphere set. The term $\|x-\tilde{x}\|_{2}$ in (19) is the distance between the current state and historical state. This distance is expected to be small so that $\mathcal{M}(x)$ can be contained in many constraints of $\mathbb{Z}(x)$. Based on this distance, we can evaluate if the historical state can provide good information for $\mathbb{C}(x)$ and can help remove some redundant constraints. As a result, the historical data which have the smallest distance $\|x-\tilde{x}\|_{2}$ is used to design $\mathcal{M}(x)$ and construct $\mathbb{C}(x)$.

To select the removal constraints $\mathbb{C}(x)$, we utilize the sphere half-space intersection check to evaluate if the sphere set $\mathcal{M}(x)$ is entirely constained in the half-space specified by the constraint in $\mathbb{Z}(x)$. This check leads to our removal rule:

In Algorithm 1, we present the removal process and present our overview of the proposed MPC scheme. Theorem 2 shows that our removal rule (20) maintains the trajectory unchanged.

Theorem 2 indicates that our algorithm exploits the historical data to accelerate the optimization without changing the state trajectory. Compared to solving the optimization problem (6) with a large number of constraints, the computation in line 6 of Algorithm 1 is low unless the historical data is very large. Even though this computation is limited by the number of historical data, some techiques can be used to overcome this problem. For example, the redundant data can removed when distance between two historical data is small.

In Algorithm 1, when data set $D$ is empty, we can initialize with one data $(x,z^{*}(x),\mathcal{A}(x))=(0,0,\emptyset)$. In (20), The terms such as $\|G_{j}\|_{2}$ can be calculated offline which can accelerate the construction of removal constraints.