# Finite-Time Computation of Polyhedral
Input-Saturated Output-Admissible Sets ††thanks: The authors are with the
University of Colorado, Boulder. ††thanks: This research is supported by the
NSF-CMMI Award 2046212.

Yaashia Gautam, Marco M. Nicotra

###### Abstract

The paper introduces a novel algorithm for computing the output admissible set
of linear discrete-time systems subject to input saturation. The proposed
method takes advantage of the piecewise-affine dynamics to propagate the
output constraints within the non-saturated and saturated regions. The
constraints are then shared between regions to ensure a proper transition from
one region to another. The resulting algorithm generates a set that is proven
to be polyhedral, safe, positively invariant, and finitely determined.
Moreover, the set is also proven to be strictly larger than the maximal output
admissible set that would be obtained by treating input saturation as a
constraint.

##  I Introduction

Maximal Output Admissible Sets (MOAS) were originally introduced in [1] and
are a cornerstone of constrained control theory. Given an autonomous system
subject to constraints, the MOAS identifies all the initial conditions that
give rise to a constraint-admissible response. This definition is often
leveraged to guarantee the recursive feasibility of command governors [2] and
model predictive control [3]. As a result, significant research effort has
been dedicated to the computation of the MOAS. A systematic algorithm for
computing the MOAS of discrete-time linear systems subject to polyhedral
constraints can be found in [1], and numerous extensions have been proposed to
address bounded disturbances [4, 5], nonlinear dynamics [6], and continuous-
time systems [7].

Although the MOAS is “maximal” under its definition, pioneering results [8, 9]
argue that it is possible to identify significantly larger invariant sets by
treating input saturation as a nonlinearity, as opposed to a regular
constraint. The resulting set is generally non-convex and challenging to
compute. In the absence of output constraints, however, existing literature
provides several tools for estimating the region of attraction of discrete-
time linear systems subject to input saturation. Ellipsoidal approximations
have been proposed in [10, 11, 12], and provably larger polyhedral inner
approximations have been constructed in [13, 14, 15] using recursive
algorithms that take advantage of the piecewise-affine nature of the system.

This paper provides a systematic method for computing the Input-Saturated
Output-Admissible Set (ISOAS), which is a forward invariant inner
approximation of the MOAS for linear systems subject to saturated state
feedback controllers. This is achieved by dividing the state space into
saturated and non-saturated regions and developing suitable methods for
propagating the constraints within each region and sharing them between
regions. Animations depicting the execution of the algorithm can be found at
https://www.colorado.edu/faculty/nicotra/2022/06/20/poc-computation-input-
saturated-output-admissible-sets. The paper is organized as follows: Section
II provides the notation used in the paper. Section III introduces the
necessary assumptions for the formulation of ISOAS and introduces the problem
statement along with a solution approach. Sections IV and V detail the two key
steps of the algorithm, i.e. constraint propagation and constraint sharing.
Numerical examples are then given in Section VI.

##  II Notation

Given a closed set $\mathcal{S}$, the boundary of $\mathcal{S}$ is denoted
with $\partial\mathcal{S}$ and its interior is denoted with
$\mathrm{Int}\,\mathcal{S}=\mathcal{S}\\!\smallsetminus\\!\partial\mathcal{S}$.
The distance between a point $z$ and the set $\mathcal{S}$ is denoted as
$\textrm{dist}(z,\mathcal{S})=\min\|z-s\|,\leavevmode\nobreak\
\textrm{s.t.}\leavevmode\nobreak\ s\in\mathcal{S}$. Given a set
$\mathcal{S}=\\{x\leavevmode\nobreak\ |\leavevmode\nobreak\ Hx\leq h\\}$ such
that $0\in\mathrm{Int}\,\mathcal{S}$, let $\epsilon\in(0,1)$ be a (typically
small) parameter. We denote the tightened set
$(1-\epsilon)\,\mathcal{S}=\\{x\leavevmode\nobreak\ |\leavevmode\nobreak\
Hx\leq(1-\epsilon)h\\}$, which satisfies
$0\in\mathrm{Int}\,(1-\epsilon)\,\mathcal{S}$ and
$(1-\epsilon)\,\mathcal{S}\subset\mathrm{Int}\,\mathcal{S}$. The $\ell$-th row
of a matrix $H$ and a column vector $h$ is identified with $[H]_{\ell}$ and
$[h]_{\ell}$, respectively.

##  III Problem Setting

Consider the linear time-invariant system

$\displaystyle x_{k+1}=Ax_{k}+Bu_{k},$ (1a) $\displaystyle
y_{k}=Cx_{k}+Du_{k},$ (1b)

with $k\in\mathbb{N}$, $x\in\mathbb{R}^{n}$, $u\in\mathbb{R}$, and
$y\in\mathbb{R}^{l}$. Hereafter, we assume $(A,B)$ stabilizable, $(A,C)$
observable, and $B\neq 0$. The system is subject to input saturation

$\underline{u}\leq u_{k}\leq\overline{u},\qquad\forall k\in\mathbb{N}$ (2)

and polyhedral output constraints

$Hy_{k}\leq h,\qquad\forall k\in\mathbb{N}.$ (3)

Let $\mathcal{U}=\\{u\leavevmode\nobreak\ |\leavevmode\nobreak\
\underline{u}\leq u\leq\overline{u}\\}$ and
$\mathcal{Y}=\\{y\leavevmode\nobreak\ |\leavevmode\nobreak\ Hy\leq h\\}$
denote the input saturation set and the output constraint set. Hereafter, we
assume that $\mathcal{U}$ and $\mathcal{Y}$ are non-empty, compact, and
contain the origin in their respective interior.

Let $G_{x}\in\mathbb{R}^{n}\backslash\\{0\\}$ and $G_{u}\in\mathbb{R}$ satisfy

$\begin{bmatrix}G_{x}\\\
G_{u}\end{bmatrix}\in\mathrm{null}\left(\begin{bmatrix}A-I&B\end{bmatrix}\right),$
(4)

and let $G_{y}\\!=\\!CG_{x}+DG_{u}$. Then, the system (1) satisfies
$G_{x}r=AG_{x}r+BG_{u}r$ and $G_{y}r=CG_{x}r+DG_{u}r$, where $r\in\mathbb{R}$
is a parameterization of the equilibrium manifold, which can be used as a
steady-state reference for the system.

To ensure that (2)-(3) are satisfied at a target equilibrium, we define the
set of steady-state admissible references

$\mathcal{R}=\left\\{r\leavevmode\nobreak\ \left|\leavevmode\nobreak\
\begin{bmatrix}\leavevmode\nobreak\ \leavevmode\nobreak\ G_{u}\\\ -G_{u}\\\
HG_{y}\end{bmatrix}r\leq\begin{bmatrix}\overline{u}\\\
-\underline{u}\leavevmode\nobreak\ \leavevmode\nobreak\ \\\
h\end{bmatrix}\right.\right\\}\\!,$ (5)

which satisfies $0\in\mathrm{Int}\;\mathcal{R}$ due to previous assumptions.
Given $\epsilon\in(0,1)$, we then define the set of strictly steady-state
admissible state and reference equilibrium pairs

$\Sigma^{\epsilon}=\left\\{(x,r)\leavevmode\nobreak\
\left|\leavevmode\nobreak\ \begin{array}[]{l}x=G_{x}r\\\\[2.0pt]
r\in(1-\epsilon)\mathcal{R}\end{array}\right.\right\\},$ (6)

which satisfies $0\in\mathrm{Int}\,\Sigma^{\epsilon}$.

###  III-A Maximal Output Admissible Set

Since Maximal Output Admissible Sets are defined for _unforced_ systems [1],
the traditional approach for computing the MOAS is to introduce a
prestabilizing linear controller

$u_{k}=G_{u}r-K(x_{k}-G_{x}r),$ (7)

with $K$ such that $A-BK$ is Schur, and rewrite (1) as

$\displaystyle x_{k+1}=\hat{A}x_{k}+\hat{B}r,$ (8a) $\displaystyle
y_{k}=\hat{C}x_{k}+\hat{D}r,$ (8b)

with $\hat{A}=A-BK$, $\hat{B}=B(G_{u}+KG_{x})$, $\hat{C}=C-DK$, and
$\hat{D}=D(G_{u}+KG_{x})$. Then, given the input and output constraints
(2)-(3), the MOAS is defined as

$\mathcal{O}_{\infty}=\left\\{(x,r)\leavevmode\nobreak\
\left|\leavevmode\nobreak\
\begin{array}[]{l}\hat{u}^{\prime}(k|x,r)\in\mathcal{U},\leavevmode\nobreak\
\forall k\in\mathbb{N}\\\\[2.0pt]
\hat{y}^{\prime}(k|x,r)\in\mathcal{Y},\leavevmode\nobreak\ \forall
k\in\mathbb{N}\end{array}\right.\right\\},$ (9)

where

$\begin{bmatrix}\hat{u}^{\prime}(k|x,r)\\\
\hat{y}^{\prime}(k|x,r)\end{bmatrix}=\begin{bmatrix}-K\\\
\hat{C}\end{bmatrix}\hat{x}^{\prime}(k|x,r)+\begin{bmatrix}G_{u}+KG_{x}\\\
\hat{D}\end{bmatrix}r,$ (10)

and

$\hat{x}^{\prime}(k|x,r)=\hat{A}^{k}x+\sum_{j=1}^{k}\hat{A}^{j-1}\hat{B}r$
(11)

are the closed-form solutions to (8), evaluated at timestep $k$, given
$x_{0}=x$. Since $\mathcal{O}_{\infty}$ may not be computable in finite time,
it is often preferable [2] to compute its inner approximation

$\tilde{\mathcal{O}}_{\infty}=\mathcal{O}_{\infty}\cap\\{\mathbb{R}^{n}\times(1-\epsilon)\mathcal{R}\\}.$
(12)

###  III-B Maximal Input-Saturated Output-Admissible Set

An interesting aspect of $\mathcal{O}_{\infty}$ is that it depends on the
prestabilizing controller (7). As motivated in [8], it is, therefore, possible
to obtain a significantly larger set by replacing (7) with the saturated
prestabilizing controller

$u_{k}=\sigma(G_{u}r-K(x_{k}-G_{x}r)),$ (13)

where $\sigma:\mathbb{R}\to\mathcal{U}$ is the piecewise affine function

$\sigma(u)=\left\\{\begin{array}[]{ll}\overline{u}&\textrm{if}\leavevmode\nobreak\
u\geq\overline{u}\\\ u&\textrm{if}\leavevmode\nobreak\
u\in(\,\underline{u}\,,\overline{u})\\\
\underline{u}&\textrm{if}\leavevmode\nobreak\
u\leq\underline{u}.\end{array}\right.$ (14)

Doing so enables us to define the Maximal Input-Saturated Output-Admissible
Set

$\Omega_{\infty}=\left\\{(x,r)\leavevmode\nobreak\ \left|\leavevmode\nobreak\
\begin{array}[]{l}\hat{y}(k|x,r)\in\mathcal{Y},\leavevmode\nobreak\ \forall
k\in\mathbb{N}\end{array}\right.\right\\},$ (15)

where $\hat{y}(k|x,r)$ is the solution to

$\left\\{\begin{array}[]{ll}\hat{x}(k+1|x,r)=A\hat{x}(k|x,r)+B\hat{u}(k|x,r),\\\
\hat{x}(0|x,r)=x,\\\
\hat{u}(k|x,r)=\sigma(G_{u}r-K(\hat{x}(k|x,r)-G_{x}r)),\\\
\hat{y}(k|x,r)=C\hat{x}(k|x,r)+D\hat{u}(k|x,r).\end{array}\right.$ (16)

Unfortunately, the set $\Omega_{\infty}$ is implicitly defined. Moreover, the
presence of nonlinearities implies that $\Omega_{\infty}$ is, in general, non-
convex. Both these properties make the computation of $\Omega_{\infty}$
intractable, which is why the approach in [8] is limited to checking if a
given state/reference pair satisfies $(x,r)\in\Omega_{\infty}$.

###  III-C Problem Statement

Given system (1) subject to the saturated controller (13), this paper aims to
compute a set $\tilde{\Omega}_{\infty}$ that satisfies

$\tilde{\mathcal{O}}_{\infty}\subset\tilde{\Omega}_{\infty}\subseteq\Omega_{\infty}.$
(17)

The envisioned set should be

  1. 1.

Polyhedral: There exist $\mathcal{H}_{x}\in\mathbb{R}^{\ell\times n}$,
$\mathcal{H}_{r}\in\mathbb{R}^{\ell}$, $\eta\in\mathbb{R}^{\ell}$ such that
$\tilde{\Omega}_{\infty}=\\{(x,r)\leavevmode\nobreak\ |\leavevmode\nobreak\
\mathcal{H}_{x}x+\mathcal{H}_{r}r\leq\eta\\}$;

  2. 2.

Finitely Determined: The number of planar constraints $\ell$ used to define
$\mathcal{H}_{x}\in\mathbb{R}^{\ell\times n}$,
$\mathcal{H}_{r}\in\mathbb{R}^{\ell}$, $\eta\in\mathbb{R}^{\ell}$, is finite;

  3. 3.

Safe: The constrained output of the controlled system is such that
$(x_{k},r)\in\tilde{\Omega}_{\infty}\leavevmode\nobreak\
\Rightarrow\leavevmode\nobreak\ y_{k}\in\mathcal{Y}$;

  4. 4.

Forward Invariant: The state update of the controlled system satisfies
$(x_{k},r)\in\tilde{\Omega}_{\infty}\leavevmode\nobreak\
\Rightarrow\leavevmode\nobreak\ (x_{k+1},r)\in\tilde{\Omega}_{\infty}$.

The resulting set $\tilde{\Omega}_{\infty}$ will hereafter be referred to as
the Input-Saturated Output-Admissible Set (ISOAS).

###  III-D Solution Approach

The solution featured in this paper leverages the piecewise-affine nature of
the prestabilized system. To do so, we first partition the state/reference
space $(x,r)\in\mathbb{R}^{n}\times(1-\epsilon)\mathcal{R}$ into three closed
sets based on (13)-(14), i.e.

  * •

Non-Saturated Region:

$\\!\\!\\!\\!\\!\mathcal{S}=\left\\{(x,r)\leavevmode\nobreak\
\left|\leavevmode\nobreak\
\begin{array}[]{l}G_{u}r-K(x_{k}-G_{x}r)\in[\underline{u},\overline{u}]\\\
r\in(1-\epsilon)\mathcal{R}\end{array}\right.\right\\},$ (18)

  * •

Upper-Saturated Region:

$\\!\\!\\!\\!\\!\overline{\mathcal{S}}=\left\\{(x,r)\leavevmode\nobreak\
\left|\leavevmode\nobreak\
\begin{array}[]{l}G_{u}r-K(x_{k}-G_{x}r)\geq\overline{u}\\\
r\in(1-\epsilon)\mathcal{R}\end{array}\quad\leavevmode\nobreak\
\right.\right\\},$ (19)

  * •

Lower-Saturated Region:

$\\!\\!\\!\\!\\!\underline{\mathcal{S}}=\left\\{(x,r)\leavevmode\nobreak\
\left|\leavevmode\nobreak\
\begin{array}[]{l}G_{u}r-K(x_{k}-G_{x}r)\leq\underline{u}\\\
r\in(1-\epsilon)\mathcal{R}\end{array}\quad\leavevmode\nobreak\
\right.\right\\}.$ (20)

We then propose an iterative procedure to

  * •

Propagate constraints within each region;

  * •

Share constraints between regions.

Finally, we introduce constraint elimination strategies to prevent the
propagation/sharing of redundant constraints.

######  Remark 1.

Although this paper is limited to the single-input case $u\in\mathbb{R}$, the
approach can be generalized to the multi-input case $u\in\mathbb{R}^{m}$, with
$m\leq n$. Doing so would cause the computational cost to grow exponentially
since the number of lower/upper/non-saturated input regions is $3^{m}$. This
scaling is consistent with established results in the literature [14].

##  IV Constraint Propagation

The idea behind constraint propagation is to take advantage of the difference
equation (16) to identify the set of states that will not violate a given
constraint in a single timestep. The resulting one-step constraint enforcement
condition is then iteratively defined as a new constraint. For ease of
notation, the state/reference pair $(x,r)$ will be grouped into a single
vector $z\in\mathbb{R}^{n+1}$, thereby leading to the following definitions

$z=\begin{bmatrix}x\\\
r\end{bmatrix},\qquad\hat{z}(k|z)=\begin{bmatrix}\hat{x}(k|x,r)\\\
r\end{bmatrix}.$ (21)

Since the system dynamics are piecewise-affine, the saturated and non-
saturated regions will be addressed separately.

###  IV-A Non-Saturated Region

Consider $z\in\mathcal{S}$ and let $\kappa(z)\in\mathbb{N}$ be such that
$\hat{z}(k|z)\in\mathcal{S},$ $\forall k\in[0,\kappa(z)]$. Within the time
interval $[0,\kappa(z)]$, the system dynamics (16) satisfy

$\hat{z}(k+1|z)=\begin{bmatrix}\hat{A}&\hat{B}\\\
0&1\end{bmatrix}\hat{z}(k|z)$ (22)

Noting that the $k$-step constraint enforcement condition
$\hat{y}(k|z)\in\mathcal{Y}$ can be written as

$H\begin{bmatrix}\hat{C}&\hat{D}\end{bmatrix}\hat{z}(k|z)\leq h,$ (23)

it follows from $\hat{x}(0|z)=x$ that the constraint
$\hat{y}(0|z)\in\mathcal{Y}$ can be rewritten as $H_{0}z\leq h_{0}$, with

$H_{0}=H\begin{bmatrix}\hat{C}&\hat{D}\end{bmatrix},\qquad h_{0}=h.$ (24)

It then follows from (22) that, $\forall k\in[0,\kappa(z)]$, the constraint
$\hat{y}(k|z)\in\mathcal{Y}$ can be rewritten as $H_{k}z\leq h_{k}$, where
$(H_{k},h_{k})$ satisfy the recursion

$H_{k+1}=H_{k}\begin{bmatrix}\hat{A}&\hat{B}\\\ 0&1\end{bmatrix},\qquad
h_{k+1}=h_{k}.$ (25)

######  Proposition 1.

Given the recursion (24)-(25), the set

$\mathcal{Q}=\mathcal{S}\cap\bigcap_{k=0}^{\infty}\left\\{z\leavevmode\nobreak\
\left|\leavevmode\nobreak\ H_{k}z\leq h_{k}\right.\right\\}$ (26)

is compact, non-zero measure, and finitely determined. In addition,
$z\in\tilde{\mathcal{O}}_{\infty}$ implies
$\hat{z}(k|z)\in\tilde{\mathcal{O}}_{\infty},\leavevmode\nobreak\ \forall
k\in\mathbb{N}$, and
$z\in\mathcal{Q}\smallsetminus\tilde{\mathcal{O}}_{\infty}$ implies the
existence of $\kappa(z)\in\mathbb{N}$ satisfying

$\displaystyle\hat{z}(k|z)$ $\displaystyle\in\mathcal{Q},\qquad\forall
k\in[0,\kappa(z)]$ (27a) $\displaystyle\hat{z}(\kappa(z)\\!+\\!1|z)$
$\displaystyle\not\in\mathcal{Q}.$ (27b)

Moreover,

$\displaystyle H_{k}\,\hat{z}(\kappa(z)\\!+\\!1|z)$ $\displaystyle\leq
h_{k},\qquad\forall k\in\mathbb{N}$ (28a)
$\displaystyle\hat{z}(\kappa(z)\\!+\\!1|z)$ $\displaystyle\not\in\mathcal{S}.$
(28b)

###### Proof.

Compactness of $\mathcal{Q}$ follows from [1, Theorem 2.1]. Since
$\tilde{\mathcal{O}}_{\infty}$ is output admissible, forward invariant, and
does not cause input saturation,
$\tilde{\mathcal{O}}_{\infty}\subset\mathcal{Q}$. Thus, $\mathcal{Q}$ has non-
zero measure because $\tilde{\mathcal{O}}_{\infty}$ has non-zero measure.

By construction, (26) is such that $\hat{z}(k|z)\in\mathcal{Q}$ entails
$H_{j}\,\hat{z}(k+1|z)\leq h_{j},\leavevmode\nobreak\ \forall j\in\mathbb{N}$.
As a result, $\hat{z}(k+1|z)\not\in\mathcal{Q}$ can only be satisfied if
$\hat{z}(k+1|z)\not\in\mathcal{S}$. To show that the set is finitely
determined, we note:

  * •

If $z\in\tilde{\mathcal{O}}_{\infty}$, $\exists\kappa(z)\in\mathbb{N}$ such
that $\textrm{dist}(\hat{z}(k|z),\Sigma^{\epsilon})\leq\delta,$ $\forall
k>\kappa(z)$, where $\delta>0$ is such that

$\\{z\leavevmode\nobreak\ |\leavevmode\nobreak\
\textrm{dist}(z,\Sigma^{\epsilon})\leq\delta\\}\subset\tilde{\mathcal{O}}_{\infty}.$

The constraints $H_{k}z\leq h_{k}$ are therefore redundant for all
$k>\kappa(z)$.

  * •

If $z\in\mathcal{Q}\smallsetminus\tilde{\mathcal{O}}_{\infty}$ there must
exists $\kappa(z)\in\mathbb{N}$ such that
$\hat{z}(\kappa(z)+1|z)\not\in\mathcal{S}$. Thus, the constraints $H_{k}z\leq
h_{k}$ are redundant for all $k>\kappa(z)$;

Since $\kappa(z)$ is finite and uniquely defined in the compact set
$\mathcal{Q}$, the solution to $k^{*}=\max\,\kappa(z),\leavevmode\nobreak\
\mathrm{s.t.}\leavevmode\nobreak\ z\in\mathcal{Q}$ is finite. Therefore, the
constraints $H_{k}z\leq h_{k}$ are redundant for all $k>k^{*}$. ∎

Given $\mathcal{H}_{0}=\\{z\leavevmode\nobreak\ |\leavevmode\nobreak\
H_{0}z\leq h_{0}\\}$, the constraint recursion (25) gives place to a set
function $f$ that outputs (26) as

$\mathcal{Q}=f(\mathcal{S},\mathcal{H}_{0}).$ (29)

This function is detailed in Algorithm 1.

### Redundant Row Reduction

Proposition 1 states that (26) can be computed in finite time. This can be
done by performing a redundant row reduction after each constraint update (25)
until $(H_{k+1},h_{k+1})$ are empty. To check whether the $\ell$-th row of
$(H_{k+1},h_{k+1})$ is redundant, it is sufficient to solve the Linear Program
(LP)

$\begin{array}[]{rrll}z^{*}_{\ell}=\textrm{argmax}&[H_{k+1}]_{\ell}\>z\\\
\mathrm{s.t.}&[H_{k+1}]_{l}\>z&\\!\\!\\!\\!\\!\leq[h_{k+1}]_{l},&\forall
l\neq\ell,\\\ &H_{j}\>z&\\!\\!\\!\\!\\!\leq h_{j},&\forall j\in[0,k],\\\
&z&\\!\\!\\!\\!\\!\in\mathcal{S}.\end{array}$ (30)

If $[H_{k+1}]_{\ell}\>z^{*}_{\ell}\leq[h_{k+1}]_{\ell}$, the $\ell$-th row of
$(H_{k+1},h_{k+1})$ is redundant and should be eliminated.

Algorithm 1 Constraint Propagation, Non-saturated

1:Inputs: Polyhedron $\mathcal{S}$, constraints $H_{0}$, $h_{0}$

2:Outputs: Polyhedron $\mathcal{Q}$, constraints $H_{\infty}$, $h_{\infty}$

3:

4:$H_{\infty}=[\leavevmode\nobreak\ ]$, $\;h_{\infty}=[\leavevmode\nobreak\
]$, $k=0$

5:while $\textrm{length}(h_{k})\neq 0$ do

6: $(H_{k+1},h_{k+1})\leftarrow\eqref{eq:CPlin_rec}$_Constraint Update_

7: for $\ell\in[1,\mathrm{length}(h_{k})]$ do _Row Reduction_

8: $z^{*}_{\ell}\leftarrow\eqref{eq:RowRed}$

9: if $[H_{k+1}]_{\ell}\>z^{*}_{\ell}\leq[h_{k+1}]_{\ell}$ then

10: Eliminate $\ell$-th row of $(H_{k+1},h_{k+1})$

11: end if

12: end for

13: $H_{\infty}=[H_{\infty};H_{k}]$, $\;h_{\infty}=[\;h_{\infty};h_{k}]$_Add
Constraints_

14: $\quad\>k=k+1$

15:end while

16:$\mathcal{Q}=\mathcal{S}\cap\\{z\leavevmode\nobreak\ |\leavevmode\nobreak\
H_{\infty}z\leq h_{\infty}\\}$

17:return $\mathcal{Q}$, $H_{\infty}$, $h_{\infty}$

###  IV-B Saturated Regions

Since the upper-saturated and lower-saturated regions fundamentally behave the
same, this paper only addresses the upper-saturated case. Consider
$z\in\overline{\mathcal{S}}$ and let $\kappa(z)\in\mathbb{N}$ be such that
$\hat{z}(k|z)\in\overline{\mathcal{S}},$ $\forall k\in[0,\kappa(z)]$. Within
the time interval $[0,\kappa(z)]$, the system dynamics satisfy

$\hat{z}(k+1|z)=\begin{bmatrix}A&0\\\
0&1\end{bmatrix}\hat{z}(k|z)+\begin{bmatrix}B\,\overline{u}\\\
0\end{bmatrix}.$ (31)

######  Lemma 1.

The dynamic model (31) admits the equilibrium point
$\bar{z}=[\bar{x}^{T}\leavevmode\nobreak\ 0]^{T}\in\overline{\mathcal{S}}$ if
and only if $I-A$ is invertible and $1+K(I-A)^{-1}B\leq 0$.

###### Proof.

The equilibrium conditions of (31) are $\bar{x}=A\bar{x}+B\bar{u}$. Since
$(A,B)$ is stabilizable, the equilibrium point

$\bar{x}=(I-A)^{-1}B\bar{u}$ (32)

exists and is unique if and only if $I-A$ is invertible. To ensure
$\bar{z}\in\overline{\mathcal{S}}$, $\bar{x}$ must satisfy
$-K\bar{x}\geq\bar{u}$. By substituting (32), this condition becomes
$(1+K(I-A)^{-1}B)\bar{u}\leq 0$. To conclude the proof, it is sufficient to
note that $0\in\mathrm{Int}\leavevmode\nobreak\ \mathcal{U}$ implies
$\bar{u}>0$. ∎

When Lemma 1 is applicable, the system admits undesirable conditions for which
the saturated input $\bar{u}$ is unable to steer the state towards the target
reference. To exclude these points from our set, we introduce the _control
authority constraint_

$-K\hat{x}(k|z)\leq-(1-\tfrac{\epsilon}{2})K\,\overline{x},\leavevmode\nobreak\
\forall k\in\mathbb{N}.$ (33)

Note that the use of $\tfrac{\epsilon}{2}$ is sufficient to ensure

$-KG_{x}r<-(1-\tfrac{\epsilon}{2})K\,\overline{x},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall r\in(1-\epsilon)\mathcal{R}$ (34)

since $G_{u}r\leq(1-\epsilon)\bar{u}$ implies
$-KG_{x}r\leq-(1-\epsilon)K\,\bar{x}$. If the conditions of Lemma 1 do not
hold, (33) is not required. Noting that the $k$-step constraint
$\hat{y}(k|z)\in\mathcal{Y}$ can be written

$H\begin{bmatrix}C&0\end{bmatrix}\hat{z}(k|z)\leq h-HD\,\overline{u},$ (35)

it follows from $\hat{z}(0|z)=z$ that both the output constraint
$\hat{y}(0|z)\in\mathcal{Y}$ and the control authority constraint (33), when
applicable, are enforced if $\overline{H}_{0}z\leq\overline{h}_{0}$, with

$\overline{H}_{0}=\begin{bmatrix}HC&0\\\
-K&0\end{bmatrix},\qquad\qquad\overline{h}_{0}=\begin{bmatrix}h-HD\,\overline{u}\\\
(\tfrac{\epsilon}{2}-1)K\,\overline{x}\end{bmatrix}.$ (36)

It then follows from (31) that, $\forall k\in[0,\kappa(z)]$, the output and
control authority constraints are enforced if
$\overline{H}_{k}z\leq\overline{h}_{k}$, where
$(\overline{H}_{k},\overline{h}_{k})$ satisfy the recursion

$\overline{H}_{k+1}=\overline{H}_{k}\begin{bmatrix}A&0\\\
0&1\end{bmatrix},\qquad\overline{h}_{k+1}=\overline{h}_{k}-\overline{H}_{k}B\,\overline{u}.$
(37)

######  Proposition 2.

Given the recursion (36)-(37), the set

$\overline{\mathcal{Q}}=\overline{\mathcal{S}}\cap\bigcap_{k=0}^{\infty}\left\\{z\>\left|\>\overline{H}_{k}z\leq\overline{h}_{k}\right.\right\\}$
(38)

is compact and finitely determined. In addition, $\forall
z\in\overline{\mathcal{Q}}$, there exists $\kappa(z)\in\mathbb{N}$ satisfying

$\displaystyle\hat{z}(k|z)$
$\displaystyle\in\overline{\mathcal{Q}},\qquad\forall k\in[0,\kappa(z)]$ (39a)
$\displaystyle\overline{H}_{k}\,\hat{z}(\kappa(z)\\!+\\!1|z)$
$\displaystyle\leq\overline{h}_{k},\qquad\forall k\in\mathbb{N}$ (39b)
$\displaystyle\hat{z}(\kappa(z)\\!+\\!1|z)$
$\displaystyle\not\in\overline{\mathcal{S}}.$ (39c)

###### Proof.

$\overline{\mathcal{Q}}$ is compact due to [1, Theorem 2.1]. By construction,
(38) is such that $\hat{z}(k|z)\in\overline{\mathcal{Q}}$ entails
$\overline{H}_{j}\,\hat{z}(k\\!+\\!1|z)\\!\leq\overline{h}_{j},\forall
j\\!\in\\!\mathbb{N}$. Thus, $\hat{z}(k+1|z)\not\in\overline{\mathcal{Q}}$ can
only be satisfied if $\hat{z}(k+1|z)\not\in\overline{\mathcal{S}}$. Moreover,
since the set $\overline{\mathcal{Q}}$ does not contain any equilibrium
points, the linear-affine system (31) necessarily admits a finite time
$\kappa(z)$ such that $\hat{z}(\kappa(z)+1|z)\not\in\overline{\mathcal{Q}}$.
Finally, the solution to $k^{*}=\max\,\kappa(z),\leavevmode\nobreak\
\mathrm{s.t.}\leavevmode\nobreak\ z\in\overline{\mathcal{Q}}$ is finite since
$\overline{\mathcal{Q}}$ is compact. Thus, the constraints
$\overline{H}_{k}z\leq\overline{h}_{k}$ are redundant for all $k>k^{*}$.

∎

Given $\overline{\mathcal{H}}_{0}=\\{z\leavevmode\nobreak\
|\leavevmode\nobreak\ \overline{H}_{0}z\leq\overline{h}_{0}\\}$, we note that
(38) can be redefined as the output of the set function

$\overline{\mathcal{Q}}=\overline{f}(\overline{\mathcal{S}},\overline{\mathcal{H}}_{0}).$
(40)

This function is detailed in Algorithm 2.

Algorithm 2 Constraint Propagation, Upper-saturated

1:Inputs: Polyhedron $\overline{\mathcal{S}}$, constraints:
$\overline{H}_{0}$, $\overline{h}_{0}$

2:Outputs: Polyhedron $\overline{\mathcal{Q}}$, constraints:
$\overline{H}_{\infty}$, $\overline{h}_{\infty}$

3:

4:$\overline{H}_{\infty}=[\leavevmode\nobreak\ ]$,
$\overline{h}_{\infty}=[\leavevmode\nobreak\ ]$, $k=0$

5:while $\textrm{length}(\overline{h}_{k})\neq 0$ do

6:
$(\overline{H}_{k+1},\overline{h}_{k+1})\leftarrow\eqref{eq:CPsat_rec}$_Constraint
Update_

7: if $k=1$ then _Empty Set Prevention_

8: for $\ell\in[1,\mathrm{length}(\overline{h}_{k})]$ do

9: $z^{*}_{\ell}\leftarrow\eqref{eq:RowRed2}$

10: if $[\overline{H}_{1}]_{\ell}\>z^{*}_{\ell}\leq[\overline{h}_{1}]_{\ell}$
then

11: Eliminate $\ell$-th row of $(\overline{H}_{1},\overline{h}_{1})$

12: end if

13: end for

14: $(\overline{H}_{2},\overline{h}_{2})\leftarrow\eqref{eq:CPsat_rec}$

15: end if

16: Algorithm 1, lines 4-9 _Row Reduction_

17: $\overline{H}_{\infty}=[\overline{H}_{\infty};\overline{H}_{k}]$,
$\;\overline{h}_{\infty}=[\overline{h}_{\infty};\overline{h}_{k}]$_Add
Constraints_

18: $\quad\>k=k+1$

19:end while

20:$\overline{\mathcal{Q}}=\overline{\mathcal{S}}\cap\\{z\leavevmode\nobreak\
|\leavevmode\nobreak\ \overline{H}_{\infty}z\leq\overline{h}_{\infty}\\}$

21:return $\mathcal{Q}$, $H_{\infty}$, $h_{\infty}$

_Empty Set Prevention_

Unlike Proposition 1, Proposition 2 does not guarantee that
$\overline{\mathcal{Q}}$ is non-empty. In fact, the constraint recursion
(37)-(38) will output $\overline{\mathcal{Q}}=\emptyset$ whenever $A$ is not
Schur. However, it should be noted that (38) does not take into account the
fact that (31) is only valid for $k\in[0,\kappa(z)]$. Since
$\hat{z}(\kappa(z)+1|z)\not\in\overline{\mathcal{S}}$, there is no need to
enforce constraints on $\hat{z}(\kappa(z)+i|z)$, with $i\geq 2$.

Based on these considerations, we will eliminate all the constraints where the
$2$-step violation is reliant on $\hat{z}(1|z)\not\in\overline{\mathcal{S}}$.
To identify these constraints, we solve the LP

$\begin{array}[]{rrll}z^{*}_{\ell}=\textrm{argmax}&[\overline{H}_{1}]_{\ell}\>z\\\
\mathrm{s.t.}&[\overline{H}_{2}]_{\ell}\>z&\\!\\!\\!\\!\\!\leq[\overline{h}_{2}]_{\ell},\\\
&\overline{H}_{0}\>z&\\!\\!\\!\\!\\!\leq\overline{h}_{0},\\\
&z&\\!\\!\\!\\!\\!\in\overline{\mathcal{S}},\end{array}$ (41)

and eliminate every row that satisfies
$[\overline{H}_{1}]_{\ell}\>z^{*}_{\ell}\leq[\overline{h}_{1}]_{\ell}$. The
constraint recursion is then _recomputed_ starting from the row-reduced
$(\overline{H}_{1},\overline{h}_{1})$, which ensures

$\\{z\leavevmode\nobreak\ |\leavevmode\nobreak\
\overline{H}_{1}z\leq\overline{h}_{1}\\}\setminus\bigcap_{k=2}^{\infty}\\{z\leavevmode\nobreak\
|\leavevmode\nobreak\ \overline{H}_{k}z\leq\overline{h}_{k}\\}\neq\emptyset,$
(42)

thereby guaranteeing that $\overline{\mathcal{Q}}$ is non-empty.

_Relationship to $\mathcal{Q}$ and $\underline{\mathcal{Q}}$_

By construction, the sets $\mathcal{Q}$ and $\overline{\mathcal{Q}}$ are
contiguous and share the saturation boundary $\\{z\leavevmode\nobreak\
|\leavevmode\nobreak\ G_{u}r-K(x-G_{x}r)=\overline{u}\\}$. Conversely, the set
$\overline{\mathcal{Q}}$ does not share any boundaries with its lower-
saturated analogous $\underline{\mathcal{Q}}$. Since
$z\in\overline{\mathcal{Q}}$ implies the existence of a finite $k$ such that
$\hat{z}(k+1|z)\not\in\overline{\mathcal{Q}}$, it is reasonable to wonder
under what conditions the system constraints will be satisfied from time $k+1$
onward. Given $\hat{z}(j|z)\in\overline{\mathcal{Q}},\leavevmode\nobreak\
\forall j\in[0,k]$, the constraints are trivially guaranteed if
$\hat{z}(k+1|z)\in\tilde{\mathcal{O}}_{\infty}$. However, additional care is
needed to address the cases
$\hat{z}(k+1|z)\in\mathcal{Q}\smallsetminus\tilde{\mathcal{O}}_{\infty}$ and
$\hat{z}(k+1|z)\in\underline{\mathcal{Q}}$.

##  V Constraint Sharing

Consider the set
$\tilde{\Omega}_{0}=\mathcal{Q}_{0}\cup\overline{\mathcal{Q}}\,\\!_{0}\cup\underline{\mathcal{Q}}\,\\!_{0}$,
where

$\displaystyle\mathcal{Q}_{0}=f(\mathcal{S},\mathcal{H}_{0}),$ (43a)
$\displaystyle\overline{\mathcal{Q}}\,\\!_{0}=\overline{f}(\overline{\mathcal{S}},\overline{\mathcal{H}}_{0}),$
(43b)
$\displaystyle\underline{\mathcal{Q}}\,\\!_{0}=\underline{f}(\underline{\mathcal{S}},\underline{\mathcal{H}}_{0}),$
(43c)

with $f(\cdot,\cdot)$ and $\overline{f}(\cdot,\cdot)$ featured in (29) and
(40), respectively, and $\underline{f}(\cdot,\cdot)$ analogous to
$\overline{f}(\cdot,\cdot)$. The set
$\tilde{\Omega}_{0}=\mathcal{Q}_{0}\cup\overline{\mathcal{Q}}\,\\!_{0}\cup\underline{\mathcal{Q}}_{0}$
represents the set of initial conditions for which the output constraints are
satisfied as long as $\hat{z}(k|z)$ belongs to the same saturation region as
the initial condition $z$. Since the system is allowed to transition between
regions, however, the set $\tilde{\Omega}_{0}$ is not invariant. The objective
of this section is to share constraints between regions so that transitioning
from one region to the next cannot cause constraint violation.

To this end, we now wish define $\mathcal{Q}_{1}\subseteq\mathcal{Q}_{0}$ such
that, if there exists $\kappa(z)\in\mathbb{N}$ satifying
$\hat{z}(k|z)\in\mathcal{Q}_{1},\leavevmode\nobreak\ \forall k=[0,\kappa(z)],$
and $\hat{z}(\kappa(z)\\!+\\!1|z)\not\in\mathcal{Q}_{1}$, then
$\hat{z}(\kappa(z)+1|z)\in\overline{\mathcal{Q}}\,\\!_{0}\cup\underline{\mathcal{Q}}\,\\!_{0}$.
This set can be obtained as

$\mathcal{Q}_{1}=f\bigl{(}\>\mathcal{Q}_{0}\>,\>\\{\overline{\mathcal{Q}}\,\\!_{0}\smallsetminus\overline{\mathcal{S}}\\}\cup\\{\underline{\mathcal{Q}}\,\\!_{0}\smallsetminus\underline{\mathcal{S}}\\}\>\bigr{)}.$
(44)

Indeed, it follows from Proposition 1 that the transition out of
$\mathcal{Q}_{1}$ must necessarily satisfy $\hat{z}(k+1|z)\not\in\mathcal{S}$
as well as
$\hat{z}(k+1|z)\in\>\\{\overline{\mathcal{Q}}\,\\!_{0}\smallsetminus\overline{\mathcal{S}}\\}\cup\\{\underline{\mathcal{Q}}\,\\!_{0}\smallsetminus\underline{\mathcal{S}}\\}$.
Proposition 2 enables us to define $\overline{\mathcal{Q}}\,\\!_{1}$ and
$\underline{\mathcal{Q}}\,\\!_{1}$ in a similar manner. Thus, the set
$\tilde{\Omega}_{1}=\mathcal{Q}_{1}\cup\overline{\mathcal{Q}}\,\\!_{1}\cup\underline{\mathcal{Q}}\,\\!_{1}$
can be interpreted as the set of initial conditions for which constraint
enforcement is guaranteed as long as the trajectory $\hat{z}(k|z)$ features
only $1$ transition between the saturation regions.

Based on this intuition, we define
$\tilde{\Omega}_{i}=\mathcal{Q}_{i}\cup\overline{\mathcal{Q}}\,\\!_{i}\cup\underline{\mathcal{Q}}\,\\!_{i}$
as the set of initial conditions for which constraint enforcement is
guaranteed as long as the system trajectories feature no more than $i$
transitions between the regions $\mathcal{S}$, $\overline{\mathcal{S}}$, and
$\underline{\mathcal{S}}$. This is achieved by introducing the set recursion

$\displaystyle\mathcal{Q}_{i+1}=f\bigl{(}\>\mathcal{Q}_{i}\>,\>\\{\overline{\mathcal{Q}}\,\\!_{i}\smallsetminus\overline{\mathcal{Q}}\,\\!_{i-1}\\}\cup\\{\underline{\mathcal{Q}}\,\\!_{i}\smallsetminus\underline{\mathcal{Q}}\,\\!_{i-1}\\}\>\bigr{)},$
(45a)
$\displaystyle\overline{\mathcal{Q}}\,\\!_{i+1}=\overline{f}\bigl{(}\>\overline{\mathcal{Q}}\,\\!_{i}\>,\>\\{\mathcal{Q}_{i}\smallsetminus\mathcal{Q}_{i-1}\\}\cup\\{\underline{\mathcal{Q}}\,\\!_{i}\smallsetminus\underline{\mathcal{Q}}\,\\!_{i-1}\\}\>\bigr{)},$
(45b)
$\displaystyle\underline{\mathcal{Q}}\,\\!_{i+1}=\underline{f}\bigl{(}\>\underline{\mathcal{Q}}\,\\!_{i}\>,\>\\{\mathcal{Q}_{i}\smallsetminus\mathcal{Q}_{i-1}\\}\cup\\{\overline{\mathcal{Q}}\,\\!_{i}\smallsetminus\overline{\mathcal{Q}}\,\\!_{i-1}\\}\>\bigr{)},$
(45c)

where
$(\mathcal{Q}_{0},\overline{\mathcal{Q}}\,\\!_{0},\underline{\mathcal{Q}}\,\\!_{0})$
are given in (43) and, for consistency,
$(\mathcal{Q}_{\,\textrm{-}1},\overline{\mathcal{Q}}\,\\!_{\,\textrm{-}1},\underline{\mathcal{Q}}\,\\!_{\,\textrm{-}1})$
are equal to $(\mathcal{S},\overline{\mathcal{S}},\underline{\mathcal{S}})$.

Algorithm 3 ISOAS Computation

1: Initialization

2:$(\mathcal{Q}_{\,\textrm{-}1},\overline{\mathcal{Q}}\,\\!_{\,\textrm{-}1},\underline{\mathcal{Q}}\,\\!_{\,\textrm{-}1})\leftarrow\eqref{eq:Nonsat}\\!-\\!\eqref{eq:Lowsat}$.

3:$(H_{0,0},h_{0,0})\leftarrow\eqref{eq:CPlin_init}$,

4:$(\overline{H}_{0,0},\overline{h}_{0,0})\leftarrow\eqref{eq:CPsat_init}$,
$(\underline{H}_{0,0},\underline{h}_{0,0})\leftarrow\eqref{eq:CPsat_init}^{*}$.

5: Main Loop

6:$i=0$

7:while
$\textrm{length}(h_{i,0})+\textrm{length}(\overline{h}_{i,0})+\textrm{length}(\underline{h}_{i,0})\neq
0$ do

8:Constraint Propagation

9:
$(\mathcal{Q}_{i},H_{i},h_{i})=\textrm{Algorithm}\;\,\ref{alg:C_prop}\leavevmode\nobreak\
(\mathcal{Q}_{i-1},H_{i,0},h_{i,0})$

10:
$(\overline{\mathcal{Q}}_{i},\overline{H}_{i},\overline{h}_{i})=\textrm{Algorithm}\leavevmode\nobreak\
\ref{alg:C_prop2}\;\,(\overline{\mathcal{Q}}_{i-1},\overline{H}_{i,0},\overline{h}_{i,0})$

11:
$(\underline{\mathcal{Q}}_{i},\underline{H}_{i},\underline{h}_{i})=\textrm{Algorithm}\leavevmode\nobreak\
\ref{alg:C_prop2}^{*}(\underline{\mathcal{Q}}_{i-1},\underline{H}_{i,0},\overline{h}_{i,0})$

12:Constraint Sharing

13: for $\ell\in[1,\mathrm{length}(\overline{\eta}_{i})]$ do _Erosion
Prevention_

14: $z^{*}_{\ell}\leftarrow\eqref{eq:RowRed3}$

15: if
$[\overline{\mathcal{H}}_{i}]_{\ell}\>z^{*}_{\ell}\leq[\overline{\eta}_{i}]_{\ell}$
then

16: Eliminate $\ell$-th row of
$(\overline{\mathcal{H}}_{i},\overline{\eta}_{i})$

17: end if

18: end for

19: Repeat 9-14 for lower-saturated region

20: $H_{i+1,0}=[\overline{H}_{i};\underline{H}_{i}],\leavevmode\nobreak\
h_{i+1,0}=[\overline{h}_{i};\underline{h}_{i}]$

21: $\overline{H}_{i+1,0}=[{H}_{i};\underline{H}_{i}],\leavevmode\nobreak\
\overline{h}_{i+1,0}=[{h}_{i};\underline{h}_{i}]$

22: $\underline{H}_{i+1,0}=[\overline{H}_{i};{H}_{i}],\leavevmode\nobreak\
\underline{h}_{i+1,0}=[\overline{h}_{i};{h}_{i}]$

23: $i=i+1$

24:end while

25:return
$\tilde{\Omega}_{\infty}=\mathcal{Q}_{i}\cup\overline{\mathcal{Q}}\,\\!_{i}\cup\underline{\mathcal{Q}}\,\\!_{i}$

######  Proposition 3.

Given the recursion (43)-(45), the set

$\tilde{\Omega}_{\infty}=\lim_{i\to\infty}\left(\mathcal{Q}_{i}\cup\overline{\mathcal{Q}}\,\\!_{i}\cup\underline{\mathcal{Q}}\,\\!_{i}\right).$
(46)

satisfies
$\tilde{\mathcal{O}}_{\infty}\subset\tilde{\Omega}_{\infty}\subseteq\Omega_{\infty}$.
Additionally, if (16) does not feature any limit cycles contained in
$\tilde{\Omega}_{\infty}$, then $\tilde{\Omega}_{\infty}$ is polyhedral,
finitely determined, safe, and forward invariant.

###### Proof.

The properties of $\tilde{\Omega}_{\infty}$ are addressed separately.

$\bullet\leavevmode\nobreak\ $Polyhedral: This property follows from the fact
that all constraints are linear.

$\bullet\leavevmode\nobreak\ $Finitely Determined: Since
$\tilde{\Omega}_{\infty}\subseteq\tilde{\Omega}_{0}$, it follows from (36)
that the set
$\\{\tilde{\Omega}_{\infty}\smallsetminus\tilde{\mathcal{O}}_{\infty}\\}$ does
not contain any equilibrium points. In the absence of limit cycles, the only
invariant set contained in $\tilde{\Omega}_{\infty}$ are the desirable
equilibrium points in the interior of $\tilde{\mathcal{O}}_{\infty}$. Since
$\tilde{\Omega}_{\infty}$ is compact and forward invariant, [16, Lemma 4.1]
ensures that, $\forall z\in\tilde{\Omega}_{\infty}$, there exists a finite
$k^{*}$ such that
$\hat{z}(k|z)\in\tilde{\mathcal{O}}_{\infty},\leavevmode\nobreak\ \forall
k>k^{*}$. Since $\tilde{\mathcal{O}}_{\infty}\subset\mathcal{S}$, the system
features at most $k^{*}$ transitions between the regions $\mathcal{S}$,
$\overline{\mathcal{S}}$, and $\underline{\mathcal{S}}$. Therefore,
$\tilde{\Omega}_{k^{*}}\smallsetminus\tilde{\Omega}_{k^{*}+1}=\emptyset$,
which implies $\tilde{\Omega}_{\infty}=\tilde{\Omega}_{k^{*}}$.

$\bullet\leavevmode\nobreak\ $Non-zero Measure: Due to (26), we note
$\tilde{\mathcal{O}}_{\infty}\subset\mathcal{Q}_{0}$. Moreover, it follows
from (45a) that

$\mathcal{Q}_{i}\,\smallsetminus\,\mathcal{Q}_{i+1}=\left\\{z\in\mathcal{Q}_{i}\leavevmode\nobreak\
\left|\leavevmode\nobreak\ \exists
k:\\!\begin{array}[]{l}\hat{z}(j|z)\in\mathcal{Q}_{i},\leavevmode\nobreak\
\forall j\in[0,k]\\\
\hat{z}(k+1|z)\in\Delta\mathcal{Q}_{i}\end{array}\\!\\!\\!\right.\right\\},$

where
$\Delta\mathcal{Q}_{i}=\\{\overline{\mathcal{Q}}\,\\!_{i}\smallsetminus\overline{\mathcal{Q}}\,\\!_{i-1}\\}\cup\\{\underline{\mathcal{Q}}\,\\!_{i}\smallsetminus\underline{\mathcal{Q}}\,\\!_{i-1}\\}$.
Since $\tilde{\mathcal{O}}_{\infty}$ is forward invariant,
$\tilde{\mathcal{O}}_{\infty}\cap\\{\mathcal{Q}_{i}\smallsetminus\mathcal{Q}_{i+1}\\}=\emptyset$.
As a result,
$\tilde{\mathcal{O}}_{\infty}\subset\mathcal{Q}_{i}\subseteq\tilde{\Omega}_{i},\leavevmode\nobreak\
\forall i\in\mathbb{N}$. Since
$\tilde{\mathcal{O}}_{\infty}\subset\tilde{\Omega}_{\infty}$ is non-zero
measure, $\tilde{\Omega}_{\infty}$ is also non-zero measure.

$\bullet\leavevmode\nobreak\ $Safe: It follows from (26), (38) that the
constraint initialization conditions (24), (36) are sufficient to ensure
$\tilde{\Omega}_{0}\subseteq\\{z\leavevmode\nobreak\ |\leavevmode\nobreak\
\hat{y}(0|z)\in\mathcal{Y}\\}$. Since
$\tilde{\Omega}_{i+1}\subseteq\tilde{\Omega}_{i},\leavevmode\nobreak\ \forall
i\in\mathbb{N}$, we show
$\tilde{\Omega}_{\infty}\subseteq\tilde{\Omega}_{0}\subseteq\\{z\leavevmode\nobreak\
|\leavevmode\nobreak\ \hat{y}(0|z)\in\mathcal{Y}\\}$.

$\bullet\leavevmode\nobreak\ $Forward Invariant: The set
$\mathcal{Q}_{\infty}$ ensures that, if there exists $k\in\mathbb{N}$ such
that

$\displaystyle\hat{z}(j|z)$
$\displaystyle\in\mathcal{Q}_{\infty},\qquad\forall j\in[0,k]$ (47a)
$\displaystyle\hat{z}(k\\!+\\!1|z)$
$\displaystyle\not\in\mathcal{Q}_{\infty},$ (47b)

then
$\hat{z}(k\\!+\\!1|z)\in\overline{\mathcal{Q}}\,\\!_{\infty}\>\cup\>\underline{\mathcal{Q}}\,\\!_{\infty}$.
Noting that both saturated sets $\overline{\mathcal{Q}}\,\\!_{\infty}$ and
$\underline{\mathcal{Q}}\,\\!_{\infty}$ benefit from the analogous property,
the combined set (46) is forward invariant. ∎

The end result, which outputs $\tilde{\Omega}_{\infty}$ based on the system
constraints, is detailed in Algorithm 3.

Figure 1: _Without Empty Set Prevention._
Top Left: Starting sets $\mathcal{Q}_{0,0}$ (green) and
$\overline{\mathcal{Q}}\,\\!_{0,0}$, $\underline{\mathcal{Q}}\,\\!_{0,0}$
(orange).
Top Right: First propagation step $\mathcal{Q}_{0,1}$ and
$\overline{\mathcal{Q}}\,\\!_{0,1}$, $\underline{\mathcal{Q}}\,\\!_{0,1}$.
Bottom Left: Sixth propagation step $\mathcal{Q}_{0,6}$ and
$\overline{\mathcal{Q}}\,\\!_{0,6}$, $\underline{\mathcal{Q}}\,\\!_{0,6}$.
Note how the constraints of the non-saturated regions translate vertically,
thereby making the previous set boundaries redundant.
Bottom Right: Final results $\mathcal{Q}_{0}$ and
$\overline{\mathcal{Q}}\,\\!_{0}$, $\underline{\mathcal{Q}}\,\\!_{0}$.
Note how both non-saturated sets are empty.

_Erosion Prevention_

Before implementing the constraint sharing step (45), we note that some of the
constraints on $\mathcal{Q}_{i}$ might cause the constraints on
$\overline{\mathcal{Q}_{i}}$ to become redundant. To avoid sharing unnecessary
(and potentially harmful) constraints, we solve the LP

$\begin{array}[]{rl}z^{*}_{\ell}=\textrm{argmax}&[\overline{\mathcal{H}}_{i}]_{\ell}\>z\\\\[3.0pt]
\mathrm{s.t.}&z\in\overline{\mathcal{S}}\\\
&z\in\mathcal{Q}_{i}\setminus\mathcal{S}.\end{array}$ (48)

and omit any row $\ell$ that satisfies
$[\overline{\mathcal{H}}_{i}]_{\ell}\>z^{*}_{\ell}\leq[\overline{\eta}_{i}]_{\ell}$.
The same is done for the lower-saturated polyhedron
$\underline{\mathcal{Q}}_{i}$.

##  VI Numerical Examples

###  VI-A Empty Set Prevention

Figure 2: _With Empty Set Prevention._
Top Left: Starting sets $\mathcal{Q}_{0,0}$ (green) and
$\overline{\mathcal{Q}}\,\\!_{0,0}$, $\underline{\mathcal{Q}}\,\\!_{0,0}$
(orange).
Top Right: Final results $\mathcal{Q}_{0}$ and
$\overline{\mathcal{Q}}\,\\!_{0}$, $\underline{\mathcal{Q}}\,\\!_{0}$.
Note that $\mathcal{Q}_{0}$ is identical to Figure 1. The first propagation
step $\overline{\mathcal{Q}}\,\\!_{0,1}$, $\underline{\mathcal{Q}}\,\\!_{0,1}$
is dropped, leading to no changes in saturated sets.
Bottom Left: Constraint sharing step $\mathcal{Q}_{1,0}$ and
$\overline{\mathcal{Q}}\,\\!_{1,0}$, $\underline{\mathcal{Q}}\,\\!_{1,0}$.
Note how the constraints $\mathcal{Q}_{0}\\!\smallsetminus\\!\mathcal{S}$
transfer to the saturated regions.
Bottom Right: Final results $\mathcal{Q}_{1}$ and
$\overline{\mathcal{Q}}\,\\!_{1}$, $\underline{\mathcal{Q}}\,\\!_{1}$.

Our first example showcases the need for the empty set prevention step
detailed in Subsection IV-B. To this end, consider the system

$\displaystyle A=\begin{bmatrix}\leavevmode\nobreak\ 1\leavevmode\nobreak\
&0.1\\\ 0&1\end{bmatrix},\quad B=\begin{bmatrix}0\\\ 0.1\end{bmatrix},$ (49a)
$\displaystyle C=\begin{bmatrix}\leavevmode\nobreak\ 1\leavevmode\nobreak\
&\leavevmode\nobreak\ 0\leavevmode\nobreak\ \\\ 0&1\end{bmatrix},\quad
D=\begin{bmatrix}\leavevmode\nobreak\ 0\leavevmode\nobreak\ \\\
0\end{bmatrix},$ (49b)

subject to the output constraints and input saturations

$\begin{bmatrix}-5\\\ -1\end{bmatrix}\leq y\leq\begin{bmatrix}5\\\
1\end{bmatrix},\qquad-2\leq u\leq 2.$ (50)

The linear feedback gain $K$ is obtained using a Linear Quadratic Regulator
(LQR) with $Q=I$ and $R=1$. For the purpose of this example, we introduce the
following notation to identify the $j$-th step of the constraint propagation
routines (25), (37). Specifically, we denote

$\mathcal{Q}_{i,j}=S\cap\bigcap_{k=0}^{j}\left\\{z\>\left|\>H_{i,k}z\leq
h_{i,k}\right.\right\\}$ (51)

for the non-saturated set and

$\overline{\mathcal{Q}}\,\\!_{i,j}=\overline{\mathcal{S}}\cap\bigcap_{k=0}^{j}\left\\{z\>\left|\>\overline{H}_{i,k}z\leq\overline{h}_{i,k}\right.\right\\}$
(52)

for the upper-saturated set (with $\underline{\mathcal{Q}}\,\\!_{i,j}$ defined
analogously). This notation is consistent with (25), (37), e.g.
$\mathcal{Q}_{i,\infty}=\mathcal{Q}_{i}$. For simplicity, we limit ourselves
to representing the planar cross-section corresponding to $r=0$.

Figure 3: _Without Erosion Prevention_
Planar cross-sections ($r=2$) of the non-saturated set $\mathcal{Q}$ (green)
and the saturated sets $\overline{\mathcal{Q}}$, $\underline{\mathcal{Q}}$
(orange) evaluated at different stages of the algorithm. The thin red dashed
lines are the output constraints and the thick dotted blue lines are the
control authority constraints.
High-Top: Starting sets $\mathcal{Q}_{0,0}$,
$\overline{\mathcal{Q}}\,\\!_{0,0}$, and $\underline{\mathcal{Q}}\,\\!_{0,0}$.
Low-Top: First constraint propagation $\mathcal{Q}_{0,\infty}$,
$\overline{\mathcal{Q}}\,\\!_{0,\infty}$, and
$\underline{\mathcal{Q}}\,\\!_{0,\infty}$.
Note how some of the constraints featured in the saturated region
$\overline{\mathcal{Q}}\,\\!_{0,\infty}$ are redundant with respect to the set
$\mathcal{Q}_{0,\infty}\\!\smallsetminus\\!\mathcal{S}$.
High-Mid: First constraint sharing $\mathcal{Q}_{1,0}$,
$\overline{\mathcal{Q}}\,\\!_{1,0}$, and $\underline{\mathcal{Q}}\,\\!_{1,0}$.
Note how the redundant constraints of the saturated region
$\overline{\mathcal{Q}}\,\\!_{0,\infty}$ are (erroneously) transferred to the
non-saturated region $\mathcal{Q}_{0,0}$.
Low-Mid: Second constraint propagation $\mathcal{Q}_{1,\infty}$,
$\overline{\mathcal{Q}}\,\\!_{1,\infty}$, and
$\underline{\mathcal{Q}}\,\\!_{1,\infty}$.
High-Bottom: Second constraint sharing $\mathcal{Q}_{2,0}$,
$\overline{\mathcal{Q}}\,\\!_{2,0}$, and $\underline{\mathcal{Q}}\,\\!_{2,0}$.
Low-Bottom: Final Result $\mathcal{Q}_{2,\infty}$,
$\overline{\mathcal{Q}}\,\\!_{2,\infty}$, and
$\underline{\mathcal{Q}}\,\\!_{2,\infty}$.

Figure 1 illustrates a first attempt at the computation of
$\tilde{\Omega}_{\infty}$ without using (41) to perform a row reduction of
$\overline{H}_{1}$. In this case, (37) converges to an empty set, which would
then lead to $\tilde{\Omega}_{\infty}=\emptyset$ once the constraints are
shared back into the non-saturated region. Figure 2 shows a correct execution
of the proposed method, whereby the LP (41) is used to identify and eliminate
all the constraints that would cause
$\overline{\mathcal{Q}}\,\\!_{0}=\emptyset$ and
$\underline{\mathcal{Q}}\,\\!_{0}=\emptyset$. The output constraints are then
properly shared from the non-saturated set to the saturated sets. Figure 2
also showcases an interesting property of
$\tilde{\Omega}_{i}=\mathcal{Q}_{i}\cup\overline{\mathcal{Q}}\,\\!_{i}\cup\underline{\mathcal{Q}}\,\\!_{i}$:
the intermediate results, in this case, $\tilde{\Omega}_{0}$ (Top Right), are
not polyhedrons, even though the final result, in this case,
$\tilde{\Omega}_{1}$ (Bottom Right), is polyhedral.

###  VI-B Erosion Prevention

Our second example showcases the need for the erosion prevention step detailed
in Section V. To this end, let

$\displaystyle A=\begin{bmatrix}1&0.1\\\ 0.1&1\end{bmatrix},\quad
B=\begin{bmatrix}0\\\ 0.1\end{bmatrix},$ (53a) $\displaystyle
C=\begin{bmatrix}\leavevmode\nobreak\ 1\leavevmode\nobreak\
&\leavevmode\nobreak\ 0\leavevmode\nobreak\ \\\ 0&1\end{bmatrix},\quad
D=\begin{bmatrix}\leavevmode\nobreak\ 0\leavevmode\nobreak\ \\\
0\end{bmatrix},$ (53b)

be subject to the output constraints and input saturations (50). The linear
feedback gain $K$ is obtained using a Linear Quadratic Regulator (LQR) with
$Q=I$ and $R=1$. Since this system satisfies Lemma 1, it admits the
undesirable equilibria $\overline{x}=[-2\leavevmode\nobreak\
\leavevmode\nobreak\ 0]^{\top}$ and $\underline{x}=[2\leavevmode\nobreak\
\leavevmode\nobreak\ 0]^{\top}$. The corresponding control authority
constraint are plotted in blue in Figures 3 and 4.

Figure 4: _With Erosion Prevention_
Same cross-sections are featured in Fig. 3, but (48) is used to eliminate
redundant constraints before sharing.
Top: Starting sets $\mathcal{Q}_{0,0}$, $\overline{\mathcal{Q}}\,\\!_{0,0}$,
and $\underline{\mathcal{Q}}\,\\!_{0,0}$.
High-Mid: First constraint propagation $\mathcal{Q}_{0,\infty}$,
$\overline{\mathcal{Q}}\,\\!_{0,\infty}$, and
$\underline{\mathcal{Q}}\,\\!_{0,\infty}$.
Note how some of the constraints featured in the saturated region
$\overline{\mathcal{Q}}\,\\!_{0,\infty}$ are redundant with respect to the set
$\mathcal{Q}_{0,\infty}\\!\smallsetminus\\!\mathcal{S}$.
Low-Mid: First constraint sharing $\mathcal{Q}_{1,0}$,
$\overline{\mathcal{Q}}\,\\!_{1,0}$, and $\underline{\mathcal{Q}}\,\\!_{1,0}$.
Note how the redundant constraints of the saturated region
$\overline{\mathcal{Q}}\,\\!_{0,\infty}$ are ignored, thereby leading to
$\mathcal{Q}_{1,0}=\mathcal{Q}_{0,\infty}$.
Bottom: Final Result $\mathcal{Q}_{1,\infty}$,
$\overline{\mathcal{Q}}\,\\!_{1,\infty}$, and
$\underline{\mathcal{Q}}\,\\!_{1,\infty}$.

Figure 3 illustrates a first attempt at the computation of
$\tilde{\Omega}_{\infty}$ without using (48) to eliminate the constraints in
$\overline{\mathcal{Q}}\,\\!_{0}$, $\underline{\mathcal{Q}}\,\\!_{0}$ that are
redundant with respect to $\mathcal{Q}_{0}$. These unnecessary constraints
cause erosion of $\mathcal{Q}_{1,0}$, ultimately leading to
$\tilde{\mathcal{O}}_{\infty}\not\subset\tilde{\Omega}_{\infty}$. Figure 4
shows a correct execution of the proposed method, whereby the LP (48) is used
to identify and eliminate all the constraints in $\overline{\mathcal{Q}}_{0}$,
$\underline{\mathcal{Q}}_{0}$ that are redundant with respect to
$\mathcal{Q}_{0}$. This prevents unnecessary constraints from transfering into
the non-saturated region $\mathcal{Q}_{1,0}$, while maintaining all the
established properties for the saturated regions since
$\overline{\mathcal{Q}}\,\\!_{1,0}\subseteq\overline{\mathcal{Q}}\,\\!_{0}$
and
$\underline{\mathcal{Q}}\,\\!_{1,0}\subseteq\underline{\mathcal{Q}}\,\\!_{0}$.

###  VI-C Comparison Between $\tilde{\mathcal{O}}_{\infty}$,
$\tilde{\Omega}_{\infty}$, and $\Omega_{\infty}$

Our final example showcases how much is gained by treating input saturation as
a nonlinearity (as opposed to a constraint) and how much is lost by computing
a polyhedral inner approximation (as opposed to the _maximal_ set). To this
end, we consider the open-loop unstable system in [15], i.e.,

$\displaystyle A=\begin{bmatrix}1.1&1\\\ 0&1.1\end{bmatrix},\quad
B=\begin{bmatrix}0.5\\\ 1.1\end{bmatrix},$ (54a) $\displaystyle
C=\begin{bmatrix}\leavevmode\nobreak\ 1\leavevmode\nobreak\
&\leavevmode\nobreak\ 0\leavevmode\nobreak\ \\\ 0&1\end{bmatrix},\quad
D=\begin{bmatrix}\leavevmode\nobreak\ 0\leavevmode\nobreak\ \\\
0\end{bmatrix},$ (54b)

subject to the output constraints and input saturations

$\begin{bmatrix}-10\\\ -10\end{bmatrix}\leq y\leq\begin{bmatrix}10\\\
10\end{bmatrix},\qquad-1\leq u\leq 1.$ (55)

The system is prestabilized using the feedback gain matrix
$K=[0.5236\leavevmode\nobreak\ \leavevmode\nobreak\ 1.1264]$. In this case,
the undesirable equilibria $\overline{x}=(I-A)^{-1}B\,\overline{u}$ exist, but
do not satisfy the condition $(1+K(I-A)^{-1}B)\leq 0$. Thus, the control
authority constraints (33) are not applicable.

Figure 5 shows a comparison between $\tilde{\mathcal{O}}_{\infty}$,
$\tilde{\Omega}_{\infty}$, and $\Omega_{\infty}$ for this particular system.
The MOAS $\tilde{\mathcal{O}}_{\infty}$ was obtained by setting input
saturation as a constraint and is significantly smaller than the ISOAS
$\tilde{\Omega}_{\infty}$ featured in this paper. The maximal set
$\Omega_{\infty}$ was instead obtained using a brute-force method to check
whether a given point $(x,r)$ satisfies (15). As expected, $\Omega_{\infty}$
is larger than $\tilde{\Omega}_{\infty}$. However, its non-convex nature makes
it both difficult to compute and impractical to represent. Conversely,
$\tilde{\Omega}_{\infty}$ is convex and can be computed systematically.

Figure 5: _ISOAS Verification 3._ Each figure features a cross-section of the
following sets for a different value of the reference
$r\in(1-\epsilon)\mathcal{R}$. The yellow star is $\Sigma^{\epsilon}$, the
blue set is $\tilde{\mathcal{O}}_{\infty}$, the green set is
$\tilde{\Omega}_{\infty}$ and the purple set is $\Omega_{\infty}$. Top Left:
$r=6$. Top Right: $r=4$. Bottom Left: $r=2$. Bottom Right: $r=0$.

##  VII Conclusion

This paper introduced a method for the finite-time computation of a polyhedral
input-saturated output-admissible set. The set is obtained by treating the
input saturation as a nonlinearity, as opposed to a constraint, thereby
leading to a piecewise-affine system. After segmenting the state/reference
space into saturated and non-saturated regions, the output constraints are
propagated within each region and shared between regions to obtain a
polyhedral, safe, and positively invariant set. Redundant constraint
elimination strategies ensure that the set is non-empty and finitely
determined. Numerical examples show that the input-saturated output-admissible
set featured in this paper can be significantly larger than the maximal output
admissible set and is a reasonable polyhedral inner-approximation of the
(generally non-convex) maximal input-saturated output-admissible set.

## References

  * [1] E. G. Gilbert and K. T. Tan, “Linear systems with state and control constraints: The theory and application of maximal output admissible sets,” IEEE Trans. on Aut. Control, vol. 36, no. 9, pp. 1008–1020, 1991.
  * [2] E. Garone, S. Di Cairano, and I. Kolmanovsky, “Reference and command governors for systems with constraints: A survey on theory and applications,” Automatica, vol. 75, pp. 306–328, 2017.
  * [3] D. Q. Mayne, J. B. Rawlings, C. V. Rao, and P. O. M. Scokaert, “Constrained model predictive control: Stability and optimality,” Automatica, vol. 36, no. 6, pp. 789–814, 2000.
  * [4] I. Kolmanovsky and E. G. Gilbert, “Maximal output admissible sets for discrete-time systems with disturbance inputs,” in American Control Conference, vol. 3, 1995.
  * [5] S. Tarbouriech and E. Castelan, “Maximal admissible polyhedral sets for discrete-time singular systems with additive disturbances,” in IEEE Conf. on Decision and Control, vol. 4, pp. 3164–3169 vol.4, 1997.
  * [6] M. Rachik, A. Tridane, M. Lhous, O. I. Kacemi, Z. Tridane, et al., “Maximal output admissible set and admissible perturbations set for nonlinear discrete systems,” Applied Mathematical Sciences, vol. 1, no. 32, pp. 1581–1598, 2007.
  * [7] M. S. Darup and M. Mönnigmann, “Computation of the largest constraint admissible set for linear continuous-time systems with state and input constraints,” IFAC Proceedings Volumes, vol. 47, no. 3, pp. 5574–5579, 2014.  19th IFAC World Congress.
  * [8] A. Cotorruelo, D. Limon, and E. Garone, “Output admissible sets and reference governors: Saturations are not constraints!,” IEEE Transactions on Automatic Control, vol. 65, no. 3, pp. 1192–1196, 2020.
  * [9] J. De Doná, M. Seron, D. Mayne, and G. Goodwin, “Enlarged terminal sets guaranteeing stability of receding horizon control,” Systems & Control Letters, vol. 47, no. 1, pp. 57–63, 2002.
  * [10] T. Hu and Z. Lin, Control systems with actuator saturation: analysis and design.  Birkhäuser, 01 2001.
  * [11] T. Alamo, A. Cepeda, and D. Limon, “Improved computation of ellipsoidal invariant sets for saturated control systems,” in IEEE Conf. on Decision and Control, pp. 6216–6221, 2005.
  * [12] D. Bertsekas and I. Rhodes, “On the minimax reachability of target sets and target tubes,” Automatica, vol. 7, no. 2, pp. 233–247, 1971.
  * [13] J. M. G. da Silva and S. Tarbouriech, “Polyhedral regions of local stability for linear discrete-time systems with saturating controls,” IEEE Transactions on Automatic Control, vol. 44, no. 11, p. 2081–2085, 1999.
  * [14] B. E. A. Milani, “Piecewise-affine Lyapunov functions for discrete-time linear systems with saturating controls,” Automatica, vol. 38, no. 12, p. 2177–2184, 2002.
  * [15] T. Alamo, A. Cepeda, D. Limon, and E. Camacho, “A new concept of invariance for saturated systems,” Automatica, vol. 42, no. 9, pp. 1515–1521, 2006.
  * [16] H. Khalil, Nonlinear Systems, Third Edition.  Pearson, 2002.