# Simultaneous Input and State Interval Observers
for Nonlinear Systems  with Full-Rank Direct Feedthrough

Mohammad Khajenejad, Sze Zheng Yong
M. Khajenejad and S.Z. Yong are with the School for Engineering of Matter,
Transport and Energy, Arizona State University, Tempe, AZ, USA (e-mail:
{mkhajene, szyong}@asu.edu).This work is partially supported by NSF grant
CNS-1932066.

###### Abstract

A simultaneous input and state interval observer is presented for Lipschitz
continuous nonlinear systems with unknown inputs and bounded noise signals
for the case when the direct feedthrough matrix has full column rank. The
observer leverages the existence of bounding decomposition functions for mixed
monotone mappings to recursively compute the maximal and minimal elements of
the estimate intervals that are compatible with output/measurement signals,
and are proven to contain the true state and unknown input. Furthermore, we
derive a Lipschitz-like property for decomposition functions, which provides
several sufficient conditions for stability of the designed observer and
boundedness of the sequence of estimate interval widths. Finally, the
effectiveness of our approach is demonstrated using an illustrative example.

##  I Introduction

_Motivation._ State and unknown input estimation has recently emerged as an
important and indispensable component in many engineering applications such as
fault detection, urban transportation, aircraft tracking and attack (unknown
input) detection and mitigation in cyber-physical systems [1, 2, 3].
Particularly, in bounded-error settings, interval/set-membership approaches
have been proposed to provide hard accuracy bounds, which is especially useful
for safety-critical systems [4]. Moreover, since the unknown inputs may be
strategic in adversarial settings, the ability to simultaneously estimate
states and inputs without imposing any assumption on the unknown inputs is
desirable and often crucial.

_Literature review._ Several approaches have been proposed in the literature
to design interval observers [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]. However,
these approaches often hinge upon relatively strong assumptions about the
existence of certain system properties, such as monotone dynamics, [7, 8],
Metzler and/or Hurwitz partial linearization of nonlinearities [10, 12],
cooperativeness [9], linear time-invariant (LTI) dynamics [11] and linear
parameter-varying (LPV) dynamics that admits a diagonal Lyapunov function
[13]. Moreover, the work in [14] addresses the design of interval observers
for a class of continuous time nonlinear systems without unknown inputs using
bounding functions by imposing somewhat restrictive assumptions on the
nonlinear dynamics to conclude stability, without discussing necessary and/or
sufficient conditions for the existence of bounding functions or how to
compute them. The authors in [15] study the problem of interval state
estimation for a class of uncertain nonlinear systems, by extracting a known
nominal observable subsystem from the plant equations and designing the
observer for the transformed system. However, the derived conditions for the
existence and stability of the observer is not _constructive_. Moreover, there
is no guarantee that the derived functional bounds have finite values, i.e.,
be bounded sequences. More importantly, the aforementioned works do not
consider unknown inputs (different from bounded-norm noise/disturbance) nor
the reconstruction/estimation of the uncertain inputs.

The problem of designing an unknown input interval observer that satisfies
$L_{2}/L_{\infty}$ optimality criteria is investigated in [16] where the
required Metzler property is formulated as a part of a semi-definite program.
However, unfortunately, their approach is limited to continuous-time LPV
systems. Moreover, in their setting, the (potentially unbounded) unknown
inputs do not affect the output (measurement) equation. On the other hand, for
systems with linear output equations and where both the state and output
equations are affected by unknown inputs/attacks, the problem of
simultaneously designing state and unknown input set-valued observers has been
studied in our previous works for LTI [3], LPV [17] and switched linear [18]
systems with bounded-norm noise.

_Contributions._ We consider the design of an observer that  _simultaneously_
returns interval-valued estimates of states and unknown inputs for  a broad
range of nonlinear systems.  Our approach is novel in multiple ways. First, to
the best of our knowledge, all existing interval observers in the literature
only return either state [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] or input [16]
estimates, whereas our observer simultaneously returns both. Second, we
consider arbitrary  unknown input signals,  i.e., no restrictive assumptions,
such as being bounded or stochastic with zero mean (as is often assumed for
noise), are imposed on the unknown inputs. Third, leveraging decomposition
functions as _nonlinear bounding mappings_ of mixed monotone vector fields
[19, 20],  which include almost every realistic nonlinear function [21], we
show that our interval estimates are compatible with measurement outputs and
are guaranteed to contain the true states and unknown inputs.  Fourth, we
provide  several sufficient conditions  in the form of Linear Matrix
Inequalities (LMI) for the stability of our designed observer.  Finally, we
provide upper bounds for the interval widths at each time step, as well as
their steady-state values.

##  II Preliminaries

_Notation._ $\mathbb{R}^{n}$ denotes the $n$-dimensional Euclidean space and
$\mathbb{R}_{+{+}}$ positive real numbers. For vectors $v,w\in\mathbb{R}^{n}$
and a matrix $M\in\mathbb{R}^{p\times q}$, $\|v\|\triangleq\sqrt{v^{\top}v}$
and $\|M\|$ denote their (induced) 2-norm,  and $v\leq w$ is an element-wise
inequality. Moreover, the transpose, Moore-Penrose pseudoinverse, $(i,j)$-th
element and rank of $M$ are given by $M^{\top}$, $M^{\dagger}$, $M_{i,j}$ and
${\rm rk}(M)$. We call $M$ a non-negative matrix, i.e., $M\geq 0$, if
$M_{i,j}\geq 0,\forall i\in\\{1\dots p\\},\forall j\in\\{1\dots q\\}$. For a
symmetric matrix $S$, $S\succ 0$ and $S\prec 0$ ($S\succeq 0$ and $S\preceq
0$) are positive and negative (semi-)definite, respectively.

Next, we introduce some definitions and related results that will be useful
throughout the paper.

######  Definition 1 (Interval, Maximal and Minimal Elements, Interval Width).

Set $\mathcal{I}\in\mathbb{R}^{n}$ is called an interval in $\mathbb{R}^{n}$,
if $\exists\underline{s},\overline{s}\in\mathcal{I}$ such that
$\underline{s}\leq x\leq\overline{s},\forall x\in\mathcal{I}$.
$\underline{s}$, $\overline{s}$ and $\|\overline{s}-\underline{s}\|$ are
called the minimal element, the maximal element and the width of
$\mathcal{I}$, respectively.

######  Proposition 1.

[14, Lemma 1] Suppose $\underline{b}\leq b\leq\overline{b}$, where
$\underline{b},b,\overline{b}\in\mathbb{R}^{n}$. Let $A\in\mathbb{R}^{m\times
n}$. Then , $A^{+}\underline{b}-A^{++}\overline{b}\leq Ab\leq
A^{+}\overline{b}-A^{++}\underline{b}$, where
$A^{+},A^{++}\in\mathbb{R}^{m\times n}$, $A^{+}_{i,j}=A_{i,j}$ if $A_{i,j}\geq
0$, $A^{+}_{i,j}=0$ if $A_{i,j}<0$ and $A^{++}=A^{+}-A$.

######  Corollary 1.

If $A\in\mathbb{R}^{n\times m}$ is a non-negative matrix (element-wise), then
$A\underline{b}\leq Ab\leq A\overline{b}$.

######  Definition 2 (Lipschitz Continuity).

Vector field $f(\cdot):\mathcal{D}_{f}\rightarrow\mathbb{R}^{m}$ is globally
$L_{f}$-Lipschitz continuous on $\mathcal{D}_{f}\subseteq\mathbb{R}^{n}$, if
there exists $L_{f}\in\mathbb{R}_{+{+}}$, such that $\|f(x_{1})-f(x_{2})\|\leq
L_{f}\|x_{1}-x_{2}\|$, $\forall x_{1},x_{2}\in D_{f}$.

######  Definition 3 (Mixed-Monotone Mappings and Decomposition Functions).

[19, Definition 4] A mapping
$f:\mathcal{X}\subseteq\mathbb{R}^{n}\rightarrow\mathcal{T}\subseteq\mathbb{R}^{m}$
is mixed monotone if there exists
$f_{d}:\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{T}$ satisfying the
following:

  1. 1.

$f$ is embedded on the diagonal of $f_{d}$, i.e., $f_{d}(x,x)=f(x)$,

  2. 2.

$f_{d}$ is monotone increasing in its first argument, i.e., $x_{1}\geq
x_{2}\implies f_{d}(x_{1},y)\geq f_{d}(x_{2},y)$, and

  3. 3.

$f_{d}$ is monotone decreasing in its second argument, i.e., $y_{1}\geq
y_{2}\implies f_{d}(x,y_{1})\leq f_{d}(x,y_{2})$.

A function $f_{d}$ satisfying the above conditions is called a decomposition
function of $f$.

######  Proposition 2.

[20, Theorem 1] Let
$f:\mathcal{X}\subseteq\mathbb{R}^{n}\rightarrow\mathcal{T}\subseteq\mathbb{R}^{m}$
be a mixed monotone mapping with decomposition function
$f_{d}:\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{T}$ and
$\underline{x}\leq x\leq\overline{x}$, where
$\underline{x},x,\overline{x}\in\mathcal{X}$. Then
$f_{d}(\underline{x},\overline{x})\leq f(x)\leq
f_{d}(\overline{x},\underline{x})$.

##  III Problem Formulation

_System Assumptions._ Consider the nonlinear discrete-time system with unknown
inputs and bounded noise

$\displaystyle\begin{array}[]{ll}x_{k+1}&=f(x_{k})+Bu_{k}+Gd_{k}+w_{k},\\\
y_{k}&=g(x_{k})+Du_{k}+Hd_{k}+v_{k},\end{array}$ (3)

where $x_{k}\in\mathbb{R}^{n}$ is the state vector at time $k\in\mathbb{N}$,
$u_{k}\in\mathbb{R}^{m}$ is a known input vector, $d_{k}\in\mathbb{R}^{p}$ is
an unknown input vector, and $y_{k}\in\mathbb{R}^{l}$ is the measurement
vector. The process noise $w_{k}\in\mathbb{R}^{n}$ and the measurement noise
$v_{k}\in\mathbb{R}^{l}$ are assumed to be bounded, with $\underline{w}\leq
w_{k}\leq\overline{w}$ and $\underline{v}\leq v_{k}\leq\overline{v}$, where
$\underline{w}$, $\overline{w}$ and $\underline{v}$, $\overline{v}$ are the
known  lower and upper bounds of the process and measurement noise signals,
respectively. We also assume  that lower and upper bounds, $\underline{x}_{0}$
and $\overline{x}_{0}$, for the initial state ${x}_{0}$ are available, i.e.,
$\underline{x}_{0}\leq x_{0}\leq\overline{x}_{0}$. The vector fields
$f(\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$,
$g(\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}^{l}$ and matrices $B$, $D$, $G$
and $H$ are known and of appropriate dimensions, where $G$ and $H$ are
matrices that encode the _locations_ through which the unknown input  (or
attack) signal can affect the system dynamics and measurements. Without loss
of generality, we assume that ${\rm rk}[G^{\top}\;H^{\top}]=p$, $n\geq l\geq
1$, $l\geq p\geq 0$ and $m\geq 0$. Moreover, we assume the following:

######  Assumption 1.

The direct feedthrough matrix $H$ has full column rank.

######  Assumption 2.

Vector fields $f(\cdot)$ and $g(\cdot)$ are mixed-monotone with decomposition
functions $f_{d}(\cdot,\cdot):\mathbb{R}^{n\times n}\rightarrow\mathbb{R}^{n}$
and $g_{d}(\cdot,\cdot):\mathbb{R}^{n\times n}\rightarrow\mathbb{R}^{l}$,
respectively.

######  Assumption 3.

Vector fields $f(\cdot)$ and $g(\cdot)$ are globally $L_{f}$-Lipschitz and
$L_{g}$-Lipschitz continuous, respectively.

Note that  Assumption 1 is a common assumption in the unknown input observer
design literature, e.g., [22],  while Assumption 2 is satisfied for a broad
range of nonlinear  functions [21].  Moreover, the decomposition function of a
vector field  is not unique and a specific one is given in [19, Theorem 2] :
If a vector field
$h=\begin{bmatrix}h^{\top}_{1}&\dots&h^{\top}_{n}\end{bmatrix}^{\top}:X\subseteq\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$
is differentiable and its partial derivatives are bounded with known bounds,
i.e., $\frac{\partial h_{i}}{\partial
x_{j}}\in(a^{h}_{i,j},b^{h}_{i,j}),\forall x\in X\in\mathbb{R}^{n}$, where
$a^{h}_{i,j},b^{h}_{i,j}\in\overline{\mathbb{R}}$, then $h$ is mixed monotone
with a decomposition function
$h_{d}=\begin{bmatrix}h^{\top}_{d1}&\dots&h^{\top}_{di}&\dots
h^{\top}_{dn}\end{bmatrix}^{\top}$, where
$h_{di}(x,y)=h_{i}(z)+(\alpha^{h}_{i}-\beta^{h}_{i})^{\top}(x-y),\forall
i\in\\{1,\dots,n\\}$, and $z,\alpha^{h}_{i},\beta^{h}_{i}\in\mathbb{R}^{n}$
can be computed in terms of $x,y,a^{h}_{i,j},b^{h}_{i,j}$ as given in [19,
(10)–(13)]. Consequently, for $x=[x_{1}\dots x_{j}\dots x_{n}]^{\top}$,
$y=[y_{1}\dots y_{j}\dots y_{n}]^{\top}$, we have

$\displaystyle h_{d}(x,y)$ $\displaystyle=h(z)+C_{h}(x-y),$ (4)

with
$C_{h}\triangleq\begin{bmatrix}[\alpha^{h}_{1}-\beta^{h}_{1}]&\dots&[\alpha^{h}_{i}-\beta^{h}_{i}]&\dots[\alpha^{f}_{m}-\beta^{f}_{m}]\end{bmatrix}^{\top}\in\mathbb{R}^{m\times
n}$, $\alpha^{f}_{i},\beta^{f}_{i}$ as given in [19, (10)–(13)],
$z=[z_{1}\dots z_{j}\dots z_{m}]^{\top}$ and $z_{j}=x_{j}$ or $y_{j}$
(dependent on the case, cf. [19, Theorem 1 and (10)–(13)] for details). On the
other hand, when the precise lower and upper bounds, $a_{i,j},b_{i,j}$, of the
partial derivatives are not known or are hard to compute, we can obtain upper
and lower approximations of the bounds by using _affine abstraction_
algorithms, e.g., [23, Theorem 1], with the slopes  set to zero.

_Unknown Input (or Attack) Signal Assumptions._ The unknown inputs $d_{k}$ are
not constrained to be a signal of any type (random or strategic) nor to follow
any model, thus no prior ‘useful’ knowledge of the dynamics of $d_{k}$ is
available (independent of $\\{d_{\ell}\\}$ $\forall k\neq\ell$,
$\\{w_{\ell}\\}$ and $\\{v_{\ell}\\}$ $\forall\ell$). We also do not assume
that $d_{k}$ is bounded or has known bounds and thus, $d_{k}$ is suitable for
representing adversarial attack signals.

The observer design problem can be stated as follows:

######  Problem 1.

Given a nonlinear discrete-time system with unknown inputs and bounded noise
(3), design a stable observer that simultaneously finds bounded intervals of
compatible states and unknown inputs.

##  IV Simultaneous Input and State Interval Observers (SISIO)

###  IV-A Interval Observer Design

We consider a recursive two-step interval-valued observer design, composed of
a _state estimation_ step and an _unknown input estimation_ step with the
following form:

$\displaystyle\text{\emph{State Estimation:}}\ \ \mathcal{I}^{x}_{k}$
$\displaystyle=\mathcal{F}_{x}(\mathcal{I}^{x}_{k-1},\mathcal{I}^{d}_{k-1},u_{k-1}),$
$\displaystyle\text{\emph{Unknown Input Estimation:}}\ \mathcal{I}^{d}_{k}$
$\displaystyle=\mathcal{F}_{d}(\mathcal{I}^{x}_{k},y_{k},u_{k}),$

where $\mathcal{F}_{x}$ and $\mathcal{F}_{d}$ are the to-be-designed interval
mappings, while $\mathcal{I}^{x}_{k}$ and $\mathcal{I}^{d}_{k}$ are the
intervals of compatible states and unknown inputs at time $k$ of the form:

$\displaystyle\mathcal{I}^{d}_{k}$
$\displaystyle=\\{d\in\mathbb{R}^{p}:\underline{d}_{k}\leq
d\leq\overline{d}_{k}\\},$ $\displaystyle\mathcal{I}^{x}_{k}$
$\displaystyle=\\{x\in\mathbb{R}^{n}:\underline{x}_{k}\leq
x\leq\overline{x}_{k}\\},$

i.e., we restrict the estimation errors to closed intervals in the Euclidean
space. In this case, the observer design problem boils down to finding the
minimal and maximal elements $\underline{d}_{k}$, $\overline{d}_{k}$,
$\underline{x}_{k}$ and $\overline{x}_{k}$ of the intervals
$\mathcal{I}^{d}_{k}$ and $\mathcal{I}^{x}_{k}$. Our interval observer can be
defined at each time step $k\geq 1$ as follows (with known $\underline{x}_{0}$
and $\overline{x}_{0}$ such that $\underline{x}_{0}\leq
x_{0}\leq\overline{x}_{0}$):

_State Estimation_ :

$\displaystyle\overline{x}_{k}$
$\displaystyle=f_{d}(\overline{x}_{k-1},\underline{x}_{k-1})+Bu_{k-1}+G^{+}\overline{d}_{k-1}-G^{++}\underline{d}_{k-1}+\overline{w},$
(5) $\displaystyle\underline{x}_{k}$
$\displaystyle=f_{d}(\underline{x}_{k-1},\overline{x}_{k-1})+Bu_{k-1}+G^{+}\underline{d}_{k-1}-G^{++}\overline{d}_{k-1}+\underline{w}.$
(6)

_Unknown Input Estimation_ :

$\displaystyle\overline{d}_{k}$
$\displaystyle=\min(\overline{d}^{1}_{k},\overline{d}^{2}_{k}),\quad\underline{d}_{k}=\max(\underline{d}^{1}_{k},\underline{d}^{2}_{k}),$
(7)

where

$\displaystyle\overline{d}^{1}_{k}$
$\displaystyle=J^{+}\overline{r}_{k}-J^{++}\underline{r}_{k}\quad,\quad\underline{d}^{1}_{k}=J^{+}\underline{r}_{k}-J^{++}\overline{r}_{k},$
(8) $\displaystyle\overline{d}^{2}_{k}$
$\displaystyle=\begin{bmatrix}\overline{d}^{2\top}_{1,k}&\dots&\overline{d}^{2\top}_{p,k}\end{bmatrix}^{\top},\quad\underline{d}^{2}_{k}=\begin{bmatrix}\underline{d}^{2\top}_{1,k}&\dots&\underline{d}^{2\top}_{p,k}\end{bmatrix}^{\top},$
(9) $\displaystyle\overline{d}^{2}_{i,k}$
$\displaystyle=\max\limits_{d_{k}\in\mathcal{D}_{k}}e_{i}d_{k},\ \
\underline{d}^{2}_{i,k}=\min\limits_{d_{k}\in\mathcal{D}_{k}}e_{i}d_{k},\forall
i\in\\{1,\dots p\\},$ (10) $\displaystyle\overline{r}_{k}$
$\displaystyle=y_{k}-g_{d}(\underline{x}_{k},\overline{x}_{k})-Du_{k}-\underline{v},$
(11) $\displaystyle\underline{r}_{k}$
$\displaystyle=y_{k}-g_{d}(\overline{x}_{k},\underline{x}_{k})-Du_{k}-\overline{v},$
(12)

with $J=H^{\dagger}$,
$\tilde{H}\triangleq\begin{bmatrix}H^{\top}-H^{\top}\end{bmatrix}^{\top}$,
$\tilde{r}_{k}\triangleq\begin{bmatrix}\overline{r}_{k}^{\top}&-\underline{r}_{k}^{\top}\end{bmatrix}^{\top}$,
$\mathcal{D}_{k}\triangleq\\{d_{k}|\tilde{H}d_{k}\leq\tilde{r}_{k}\\}$, and
$e_{i}\in\mathbb{R}^{1\times p},e_{i}(1,i)=1,\ e_{i}(1,j)=0,\forall j\neq i$.
In the next sections, we will show that the choice of $J=H^{\dagger}$ and
$f_{d},g_{d}$ as decomposition functions of $f,g$ yields several desirable
observer properties. The SISIO observer is summarized in Algorithm 1.

Algorithm 1 Simultaneous Input and State Interval Observer

1:Initialize: $J=H^{\dagger}$;
$\text{maximal}(\mathcal{I}^{x}_{0})=\overline{x}_{0}$;
$\text{minimal}(\mathcal{I}^{x}_{0})=\underline{x}_{0}$;

2: Compute $J^{+},J^{++},G^{+},G^{++},L_{f_{d}},L_{g_{d}}$ via Proposition 1
and

3: Lemma 1; Compute
$g_{d}(\overline{x}_{0},\underline{x}_{0}),g_{d}(\underline{x}_{0},\overline{x}_{0})$
via (4);

4: $K\triangleq(G^{+}+G^{++})(J^{+}+J^{++})$; $\Delta
w=\overline{w}-\underline{w}$; $\Delta v=\overline{v}-\underline{v}$;

5:
$\overline{r}_{0}=y_{0}-g_{d}(\underline{x}_{0},\overline{x}_{0})-Du_{0}-\underline{v}$;

6:
$\underline{r}_{0}=y_{0}-g_{d}(\overline{x}_{0},\underline{x}_{0})-Du_{0}-\overline{v}$;

7: $\overline{d}^{1}_{0}=J^{+}\overline{r}_{0}-J^{++}\underline{r}_{0}$;
$\underline{d}^{1}_{0}=J^{+}\underline{r}_{0}-J^{++}\overline{r}_{0}$;

8: $\Delta z=\Delta w+K\Delta v$;
$\tilde{H}\triangleq\begin{bmatrix}H^{\top}-H^{\top}\end{bmatrix}^{\top}$;

9:
$\tilde{r}_{0}\triangleq\begin{bmatrix}\overline{r}_{0}^{\top}&-\underline{r}_{0}^{\top}\end{bmatrix}^{\top}$;
$\mathcal{D}_{0}\triangleq\\{d_{0}|\tilde{H}d_{0}\leq\tilde{r}_{0}\\}$;

10: $e_{i}\in\mathbb{R}^{1\times p},e_{i}(1,i)=1,e_{i}(1,j)=0,\forall
i,j\in\\{1,\dots,p\\},j\neq i$;

11: $\forall i\in\\{1,\dots
p\\},\overline{d}^{2}_{i,0}=\max\limits_{d_{0}\in\mathcal{D}_{0}}e_{i}d_{0}$;
$\underline{d}^{2}_{i,0}=\min\limits_{d_{0}\in\mathcal{D}_{0}}e_{i}d_{0}$;

12: $\delta^{x}_{0}=\|\overline{x}_{0}-\underline{x}_{0}\|$;
$\overline{d}_{0}=\min(\overline{d}^{1}_{0},\overline{d}^{2}_{0})$;
$\underline{d}_{0}=\max(\underline{d}^{1}_{0},\underline{d}^{2}_{0})$;

13: $\text{maximal}(\mathcal{I}^{d}_{0})=\overline{d}_{0}$;
$\text{minimal}(\mathcal{I}^{d}_{0})=\underline{d}_{0}$;
$\delta^{d}_{0}=\|\overline{d}_{0}-\underline{d}_{0}\|$;

14:for $k=1$ to $K$ do

15:$\triangleright$ Estimation of ${x}_{k}$

16: Compute
$f_{d}(\overline{x}_{k-1},\underline{x}_{k-1}),f_{d}(\underline{x}_{k-1},\overline{x}_{k-1})$
via (4);

17: Compute $\overline{x}_{k},\underline{x}_{k}$ via (5) and (6);

18: $\delta^{x}_{k}=\mathcal{L}^{k}\delta_{0}^{x}+\|\Delta
z\|\left(\frac{1-\mathcal{L}^{k}}{1-\mathcal{L}}\right)$;

19: $\mathcal{I}^{x}_{k}=\\{x\in\mathbb{R}^{n}:\underline{x}_{k}\leq
x\leq\overline{x}_{k}\\}$;

20:$\triangleright$ Estimation of ${d}_{k}$

21: Compute
$g_{d}(\overline{x}_{k},\underline{x}_{k}),g_{d}(\underline{x}_{k},\overline{x}_{k})$
via (4);

22: Compute $\overline{r}_{k},\underline{r}_{k}$ via (11) and (12);
$\tilde{r}_{k}\triangleq\begin{bmatrix}\overline{r}_{k}^{\top}&-\underline{r}_{k}^{\top}\end{bmatrix}^{\top}$;

23: Compute $\overline{d}^{1}_{k},\underline{d}^{1}_{k}$ via (8);
$\mathcal{D}_{k}\triangleq\\{d_{k}|\tilde{H}d_{k}\leq\tilde{r}_{k}\\}$;

24: Compute $\overline{d}^{2}_{i,k},\underline{d}^{2}_{i,k}$ via (10) $\forall
i\in\\{1,\dots p\\}$;

25: Compute $\overline{d}_{k},\underline{d}_{k}$ via (7);

26:
$\delta^{d}_{k}=\|J^{+}+J^{++}\|L_{g_{d}}\delta_{k}^{x}+\|(J^{+}+J^{++})\Delta
v\|$;

27: $\mathcal{I}^{d}_{k}=\\{d\in\mathbb{R}^{p}:\underline{d}_{k}\leq
d\leq\overline{d}_{k}\\}$;

28:end for

###  IV-B Correctness  (Framer Property) of Interval Estimates

In the following, we show that the SISIO observer returns correct interval
estimates in the sense that at each time step, the true states and unknown
inputs are guaranteed to be within the estimated intervals given by (5)–(7).
This is also known as the _framer property_ , e.g., in [12]. To increase
readability, all proofs will be provided in the appendix.

######  Theorem 1 (Correctness of the Interval Estimates).

Let $\underline{x}_{0}\leq x_{0}\leq\overline{x}_{0}$, where
$\underline{x}_{0}$ and $\overline{x}_{0}$ are known. For the system (3), if
Assumptions 1 and 2 hold, then the SISIO estimate intervals (5)–(7) with
$J=H^{\dagger}$ and $f_{d}(\cdot,\cdot),g_{d}(\cdot,\cdot)$ as decomposition
functions of $f(\cdot),g(\cdot)$ at each step $k$ are _correct_ , i.e., the
true states and unknown inputs are guaranteed to satisfy
$\underline{d}_{k}\leq d_{k}\leq\overline{d}_{k}$ and $\underline{x}_{k}\leq
x_{k}\leq\overline{x}_{k}$.

###  IV-C Boundedness of Interval Estimates and Observer Stability

In this section we study the stability of SISIO, assuming that the
decomposition functions can be obtained using (4). We first derive a
Lipschitz-like property for decomposition functions in Lemma 1. Then, we
derive several sufficient conditions for the stability of  SISIO in Theorem 2.

######  Lemma 1.

Let $h(\cdot):\mathcal{D}_{h}\subseteq\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$
be a globally $L_{h}$-Lipschitz continuous and mixed monotone vector field and
$h_{d}(\cdot,\cdot):\mathcal{D}_{h}\times\mathcal{D}_{h}\rightarrow\mathbb{R}^{m}$
be the decomposition function for $h$, constructed using (4). Consider
$\underline{x}\leq\overline{x}$, both in $\mathcal{D}_{h}$. Then
$\|h_{d}(\overline{x},\underline{x}_{k})-h_{d}(\underline{x}_{k},\overline{x}_{k})\|\leq
L_{h_{d}}\|\overline{x}-\underline{x}\|$, where $L_{h_{d}}\triangleq
L_{h}+2\|C_{h}\|$, with $C_{h}$ given in (4).

######  Theorem 2 (Observer Stability).

Consider the system (3) and the SISIO observer (5)–(7), and suppose that
Assumption 3 and all the assumptions and conditions in Theorem 1 hold and the
decomposition functions $f_{d},g_{d}$ are constructed using (4). Then, the
observer is stable, in the sense that at each time step $k$, interval width
sequences
$\\{\|\Delta^{d}_{k}\|\triangleq\|\overline{d}_{k}-\underline{d}_{k}\|,\|\Delta^{x}_{k}\|\triangleq\|\overline{x}_{k}-\underline{x}_{k}\|\\}_{k=0}^{\infty}$
are bounded, and consequently, interval input and state estimation errors
$\\{\|\tilde{d}_{k}\|\triangleq\max(\|d_{k}-\underline{d}_{k}\|,\|\overline{d}_{k}-{d}_{k}\|),\|\tilde{x}_{k}\|\triangleq\max(\|x_{k}-\underline{x}_{k}\|,\|\overline{x}_{k}-{x}_{k}\|)\\}_{k=0}^{\infty}$
are also bounded, if  either one of the following conditions hold:

  1. (i)

$\mathcal{L}\triangleq(L_{f_{d}}+L_{g_{d}}\|K\|)<1;$

  2. (ii)

$\begin{bmatrix}F&0&0&0&0\\\ *&K^{\top}K&K^{\top}&K^{\top}&K^{\top}K\\\
*&*&I&I&K\\\ *&*&*&0&K\\\ *&*&*&*&0\end{bmatrix}\preceq 0;$

  3. (iii)

There exist a positive definite matrix $P\succ 0$ and a positive semidefinite
matrix $\Gamma\succeq 0$ in $\mathbb{R}^{n\times n}$ such that the following
LMI condition  is satisfied:

$\displaystyle\begin{bmatrix}P+\Gamma-I&0&P\\\ 0&\mathcal{L}I-P&0\\\
P&0&P\end{bmatrix}\preceq 0,$

with $L_{f_{d}}$ and $L_{g_{d}}$ given in Lemma 1,
$K\triangleq(G^{+}+G^{++})(J^{+}+J^{++})$,
$F\triangleq(L^{2}_{f_{d}}+L^{2}_{g_{d}}\lambda_{\max}(K^{\top}K)-1)I$ and
$\lambda_{\max}(K^{\top}K)$ is the maximum eigenvalue of $K^{\top}K$.

It is notable that examples of dynamic systems with only slight differences in
their $G$ and $H$ matrices can be found, which only satisfy a subset of the
three aforementioned conditions and do not satisfy the others. For instance,
for the example system in Section V, we found that it satisfies Conditions (i)
and (ii) but does not satisfy Condition (iii). However, when we change the $G$
and $H$ matrices to $G=\begin{bmatrix}0&0.1\\\ 0.2&-0.2\end{bmatrix}$ and
$H=\begin{bmatrix}0.1&0.3\\\ 0.5&-0.7\end{bmatrix}$, we observe that
$\mathcal{L}=2.5212>1$, so Condition i does not hold. In addition, Condition
(ii) also does not hold, but Condition (iii) holds with
$P=\begin{bmatrix}3.4352&0\\\ 0&3.4352\end{bmatrix}$ and
$\Gamma=\begin{bmatrix}0.3402&0\\\ 0&0.3402\end{bmatrix}$. A search for a more
general condition that  encompasses all of these conditions is a subject of
future work.

Finally, we will provide upper bounds for the interval widths and compute
their steady-state values, if they exist.

######  Lemma 2 (Upper Bounds of the Interval Widths and their Convergence).

Consider the system (3) and the SISIO observer (5)–(7), and suppose that
Assumptions 1–3 hold. Then, at each time step $k$, there exist bounded and
finite-valued upper bounds $\delta^{x}_{k}$ and $\delta^{d}_{k}$, for interval
widths $\|\Delta^{x}_{k}\|$ and $\|\Delta^{d}_{k}\|$ respectively, which can
be computed as follows:

$\displaystyle\|\Delta^{x}_{k}\|$
$\displaystyle\leq\delta^{x}_{k}=\mathcal{L}^{k}\delta_{0}^{x}+\|\Delta
z\|\left(\frac{1-\mathcal{L}^{k}}{1-\mathcal{L}}\right),$
$\displaystyle\|\Delta^{d}_{k}\|$
$\displaystyle\leq\delta^{d}_{k}=\|J^{+}+J^{++}\|L_{g_{d}}\delta_{k}^{x}+\|(J^{+}+J^{++})\Delta
v\|,$

with $L_{g_{d}}$ and $\mathcal{L}$ given in Lemma 1 and Theorem 2,
respectively, $\Delta z\triangleq\Delta w+K\Delta v$, $\Delta
w\triangleq\overline{w}-\underline{w}$, $\Delta
v\triangleq\overline{v}-\underline{v}$ and
$K\triangleq(G^{+}+G^{++})(J^{+}+J^{++})$. Furthermore, if  Condition (i) in
Theorem 2 holds, then the upper bound sequences of the interval widths
converge to steady-state values as follows:

$\displaystyle\overline{\delta}^{x}$
$\displaystyle\triangleq\lim_{k\to\infty}\delta^{x}_{k}=\|\Delta
z\|\frac{\mathcal{L}}{1-\mathcal{L}},\quad\overline{\delta}^{d}\triangleq\lim_{k\to\infty}\delta^{d}_{k}=\mathcal{G}(\overline{\delta}^{x}),$

where
$\mathcal{G}(x)\triangleq\|J^{+}+J^{++}\|L_{g_{d}}x+\|(J^{+}+J^{++})\Delta
v\|$. On the other hand, if Conditions (ii) or (iii) in Theorem 2 hold, then
the interval interval widths $\|\Delta^{x}_{k}\|$ and $\|\Delta^{d}_{k}\|$ are
uniformly bounded by $\min\\{\|\Delta^{x}_{0}\|,\Delta^{P}_{0}\\}$ and
$\min\\{\mathcal{G}(\|\Delta^{x}_{0}\|),\mathcal{G}((\Delta^{P}_{0})\\}$,
respectively, with
$\Delta^{P}_{0}\triangleq\sqrt{\frac{(\Delta^{x}_{0})^{\top}P\Delta^{x}_{0}}{\lambda_{\min}(P)}}$
and $P$ being the solution for the LMI condition in Condition (iii).

##  V Illustrative Example

We consider the time-discretized dynamics of a nonlinear system in [15] with
slight modifications to include measurement and process noise signals, and
unknown inputs and with the following parameters (cf. (3)): $n=2$, $m=1$,
$l=1$, $p=2$,
$f(x_{k})=\begin{bmatrix}f_{1}(x_{k})&f_{2}(x_{k})\end{bmatrix}^{\top}$,
$f_{1}(x_{k})=x_{2,k}+0.25\sin(0.1x_{1,k}x_{2,k})$,
$f_{2}(x_{k})=-0.2x_{2,k}-1.9\sin(0.01x_{1,k})$,
$g(x_{k})=x_{1,k}+0.526x_{2,k}-0.05x_{1,k}x_{2,k}$,
$\mathcal{D}_{f}=\mathcal{D}_{g}=\begin{bmatrix}-5&5\end{bmatrix}\times\begin{bmatrix}-15&15\end{bmatrix}$,
$B=\begin{bmatrix}0&0.1\end{bmatrix}^{\top}$, $D=0_{1\times 2}$,
$G=\begin{bmatrix}0&-0.1\\\ 0.2&-0.2\end{bmatrix}$,
$H=\begin{bmatrix}-0.1&0.3\\\ 0.5&-0.7\end{bmatrix}$,
$u_{k}=0.1\sin(k)+0.75\cos(0.25k)$, $\overline{v}=-\underline{v}=0.01$,
$\overline{w}=-\underline{w}=\begin{bmatrix}0.02&0.02\end{bmatrix}^{\top}$,
$\overline{x}_{0}=\begin{bmatrix}2&1.1\end{bmatrix}^{\top}$,
$\underline{x}_{0}=\begin{bmatrix}-1.1&-2\end{bmatrix}^{\top}$, while the
unknown input signals are depicted in Figure 1. Note that rk$(H)=2$, thus
Assumption 1 holds. Moreover, applying [23, Theorem 1], we can compute finite-
valued upper and lower bounds for partial derivatives of $f(\cdot)$ and
$g(\cdot)$ as: $\begin{bmatrix}a^{f}_{11}&a^{f}_{12}\\\
a^{f}_{21}&a^{f}_{22}\end{bmatrix}=\begin{bmatrix}-0.25&0.99\\\
-0.0019&-0.2\end{bmatrix}$, $\begin{bmatrix}b^{f}_{11}&b^{f}_{12}\\\
b^{f}_{21}&b^{f}_{22}\end{bmatrix}=\begin{bmatrix}0.25&1.01\\\
0.0019&0.2\end{bmatrix}$,
$\begin{bmatrix}a^{g}_{11}&a^{g}_{12}\end{bmatrix}=\begin{bmatrix}0.75&-0.224\end{bmatrix}$,
$\begin{bmatrix}b^{g}_{11}&b^{g}_{12}\end{bmatrix}=\begin{bmatrix}1.25&0.1276\end{bmatrix}$.
Hence, Assumption 2 is also satisfied by [19, Theorem 1]). Therefore, we
expect that the interval estimates are correct by Theorem 1 (i.e., the true
states and unknown inputs are within the estimate intervals), which can be
verified from Figure 1 that depicts interval estimates as well as the true
states and unknown inputs.

Figure 1: Actual states and inputs, $x_{1,k}$, $x_{2,k}$, $d_{1,k}$,
$d_{2,k}$, as well as their estimated maximal and minimal values,
$\overline{x}_{1,k}$, $\underline{x}_{1,k}$, $\overline{x}_{2,k}$,
$\underline{x}_{1,k}$, $\overline{d}_{1,k}$, $\underline{d}_{1,k}$,
$\overline{d}_{2,k}$, $\underline{d}_{2,k}$.  Figure 2: Estimation errors,
estimate interval widths and their upper bounds for the interval-valued
estimates of states, $\|\tilde{x}_{k|k}\|$, $\|\Delta^{x}_{k}\|$,
$\delta^{x}_{k}$, and unknown inputs, $\|\tilde{d}_{k}\|$,
$\|\Delta^{d}_{k}\|$, $\delta^{d}_{k}$.

Furthermore, $f(\cdot)$ and $g(\cdot)$ satisfy Assumption 3 with $L_{f}=0.35$
and $L_{g}=0.74$. In addition, from [19, (10)–(13)]), we obtain
$C_{f}=\begin{bmatrix}0.251&0\\\ 0.0029&0.201\end{bmatrix}$,
$C_{g}=\begin{bmatrix}0&0.225\end{bmatrix}$ using (4), which implies that
$L_{f_{d}}=0.852$ and $L_{g_{d}}=1.19$ by Lemma 1. Consequently,
$\mathcal{L}=0.843$. Since all the required assumptions, including Condition
(i) in Theorem 2, hold, we expect to obtain bounded and convergent interval
estimate errors when applying our observer design procedure. This can be seen
in Figure 2, where at each time step, the actual error is less than or equal
to the interval width, which in turn is less than or equal to the predicted
upper bound for the interval width. Moreover, as expected, the upper bounds
converge to some steady-state values.  Note that, despite our best efforts, we
were unable to find interval-valued observers in the literature that
simultaneously return both state and unknown input estimates for comparison
with our results.

##  VI Conclusion

In this paper, we proposed a simultaneous input and state interval observer
for mixed monotone Lipschitz nonlinear systems with unknown inputs and bounded
noise. We proved that the proposed observer recursively outputs the state and
unknown input interval-valued estimates that are guaranteed to include the
true states and unknown inputs. Moreover, several sufficient conditions for
the stability of the observer and the boundedness of the interval widths were
derived. Finally, we demonstrated the effectiveness of the proposed approach
with an example. For future work, we seek to relax the full-rank assumption
for the direct feedthrough matrix  and to find necessary conditions for
observer stability.

## References

  * [1] W. Liu and I. Hwang.  Robust estimation and fault detection and isolation algorithms for stochastic linear hybrid systems with unknown fault input.  IET control theory & applications, 5(12):1353–1368, 2011.
  * [2] S.Z. Yong, M. Zhu, and E. Frazzoli.  Switching and data injection attacks on stochastic cyber-physical systems: Modeling, resilient estimation and attack mitigation.  ACM Transactions on Cyber-Physical Systems, 2(2):9, 2018.
  * [3] S.Z. Yong.  Simultaneous input and state set-valued observers with applications to attack-resilient estimation.  In 2018 Annual American Control Conference (ACC), pages 5167–5174. IEEE, 2018.
  * [4] F. Blanchini and M. Sznaier.  A convex optimization approach to synthesizing bounded complexity $\ell^{\infty}$ filters.  IEEE Transactions on Automatic Control, 57(1):216–221, 2012.
  * [5] L. Jaulin.  Nonlinear bounded-error state estimation of continuous-time systems.  Automatica, 38(6):1079–1082, 2002.
  * [6] M. Kieffer and E. Walter.  Guaranteed nonlinear state estimator for cooperative systems.  Numerical algorithms, 37(1-4):187–198, 2004.
  * [7] M. Moisan, O. Bernard, and J-L. Gouzé.  Near optimal interval observers bundle for uncertain bioreactors.  In European Control Conference (ECC), pages 5115–5122. IEEE, 2007\.
  * [8] O. Bernard and J-L. Gouzé.  Closed loop observers bundle for uncertain biotechnological models.  Journal of Process Control, 14(7):765–774, 2004.
  * [9] T. Raïssi, G. Videau, and A. Zolghadri.  Interval observer design for consistency checks of nonlinear continuous-time systems.  Automatica, 46(3):518–527, 2010.
  * [10] T. Raïssi, D. Efimov, and A. Zolghadri.  Interval state estimation for a class of nonlinear systems.  IEEE Transactions on Automatic Control, 57(1):260–265, 2011.
  * [11] F. Mazenc and O. Bernard.  Interval observers for linear time-invariant systems with disturbances.  Automatica, 47(1):140–147, 2011.
  * [12] F. Mazenc, T-N. Dinh, and S-I. Niculescu.  Robust interval observers and stabilization design for discrete-time systems with input and output.  Automatica, 49(11):3490–3497, 2013.
  * [13] Y. Wang, D-M. Bevly, and R. Rajamani.  Interval observer design for LPV systems with parametric uncertainty.  Automatica, 60:79–85, 2015.
  * [14] D. Efimov, T. Raïssi, S. Chebotarev, and A. Zolghadri.  Interval state observer for nonlinear time varying systems.  Automatica, 49(1):200–205, 2013.
  * [15] G. Zheng, D. Efimov, and W. Perruquetti.  Design of interval observer for a class of uncertain unobservable nonlinear systems.  Automatica, 63:167–174, 2016.
  * [16] N. Ellero, D. Gucik-Derigny, and D. Henry.  An unknown input interval observer for LPV systems under ${L}_{2}$-gain and ${L}_{\infty}$-gain criteria.  Automatica, 103:294–301, 2019.
  * [17] M. Khajenejad and S.Z. Yong.  Simultaneous input and state set-valued $\mathcal{{H}}_{\infty}$-observers for linear parameter-varying systems.  In American Control Conference (ACC), pages 4521–4526. IEEE, 2019\.
  * [18] M. Khajenejad and S.Z. Yong.  Simultaneous mode, input and state set-valued observers with applications to resilient estimation against sparse attacks.  In Conference on Decision and Control (CDC), 2019.
  * [19] L. Yang, O. Mickelin, and N. Ozay.  On sufficient conditions for mixed monotonicity.  IEEE Transactions on Automatic Control, 64(12):5080–5085, 2019\.
  * [20] S. Coogan and M. Arcak.  Efficient finite abstraction of mixed monotone systems.  In Hybrid Systems: Computation and Control, pages 58–67. ACM, 2015\.
  * [21] L. Yang and N. Ozay.  Tight decomposition functions for mixed monotonicity.  In Conference on Decision and Control (CDC), pages 5318–5322, 2019\.
  * [22] S. Gillijns and B. De Moor.  Unbiased minimum-variance input and state estimation for linear discrete-time systems with direct feedthrough.  Automatica, 43(5):934–937, 2007.
  * [23] K.R. Singh, Q. Shen, and S.Z. Yong.  Mesh-based affine abstraction of nonlinear systems with tighter bounds.  In Conference on Decision and Control (CDC), pages 3056–3061. IEEE, 2018.
  * [24] H.K. Khalil.  Nonlinear systems.  Upper Saddle River, 2002.
  * [25] S.S Delshad, A. Johansson, M. Darouach, and T. Gustafsson.  Robust state estimation and unknown inputs reconstruction for a class of nonlinear systems: Multiobjective approach.  Automatica, 64:1–7, 2016.

## Appendix: Proofs

###  VI-A Proof of Theorem 1

First, note that for $r_{k}\triangleq Hd_{k}=y_{k}-g(x_{k})-Du_{k}-v_{k}$, we
can obtain $\underline{r}_{k}\leq r_{k}=Hd_{k}\leq\overline{r}_{k}$ by
Assumption 2 and the fact that decomposition functions are monotone increasing
in their first argument and decreasing in their second (cf. Definition 3). By
left multiplying the above inequalities by $J=H^{\dagger}$ and from Assumption
1 and Proposition 1, we can conclude that $\underline{d}^{1}_{k}\leq
d_{k}\leq\overline{d}^{1}_{k}$. Moreover, since $\underline{r}_{k}\leq
r_{k}=Hd_{k}\leq\overline{r}_{k}$ can be rearranged as
${d_{k}\in\mathcal{D}_{k}\triangleq\\{d\in\mathbb{R}^{p}\,|}\,\tilde{H}d\leq\tilde{r}_{k}{\\}}$,
the linear programs (10) yield the tightest maximal and minimal elements of
$\mathcal{I}^{d}_{k}$ that enclose $\mathcal{D}_{k}$, i.e.,
$\underline{d}^{2}_{k}\leq d_{k}\leq\overline{d}^{2}_{k}$. Combining this and
$\underline{d}^{1}_{k}\leq d_{k}\leq\overline{d}^{1}_{k}$, we obtain
$\underline{d}_{k}\leq d_{k}\leq\overline{d}_{k}$.

Similarly, since Assumption 2 holds, by applying the fact that decomposition
functions are monotone increasing in their first argument and decreasing in
their second, as well as Proposition 1 to (3), we obtain
$\underline{x}_{k}\leq x_{k}\leq\overline{x}_{k}$ with $\underline{x}_{k}$ and
$\overline{x}_{k}$ given in (5) and (6). ∎

###  VI-B Proof of Lemma 1

Starting from (4),

$\displaystyle
f_{d}(\overline{x},\underline{x})=f(x_{1})+C_{f}(\overline{x}-\underline{x}),$
(13) $\displaystyle
f_{d}(\underline{x},\overline{x})=f(x_{2})+C_{f}(\underline{x}-\overline{x}),$
(14)

where $\forall i\in\\{1\dots n\\}$, $x_{1,{i}}$ and
$x_{2,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i}}$
are either $\overline{x}{{}_{i}}$, or $\underline{x{{}_{i}}}$, depending on
the case (cf. [19, Theorem 1; (10)–(13)]). Moreover,
$\underline{x}\leq\overline{x}$ and $\underline{x}\leq
x_{1},x_{2}\leq\overline{x}.$ This implies that

$\displaystyle-(\overline{x}-\underline{x})\leq
x_{1}-x_{2}\leq\overline{x}-\underline{x}\implies\|x_{1}-x_{2}\|\leq\|\overline{x}-\underline{x}\|.$
(15)

On the other hand, from (13) and (14),

$f_{d}(\overline{x},\underline{x})-f_{d}(\underline{x},\overline{x})=f(x_{1})-f(x_{2})+2C_{f}(\overline{x}-\underline{x}).$

Then, applying triangle inequality and by the Lipschitz continuity of $f$, we
obtain

$\displaystyle\|f_{d}(\overline{x},\underline{x})-f_{d}(\underline{x},\overline{x})\|\leq
L_{f}\|x_{1}-x_{2}\|+2\|C_{f}\|\|(\overline{x}-\underline{x})\|.$ (16)

Combining (15) and (16) yields the result. ∎

###  VI-C Proof of Theorem 2

From (5) and (6), we obtain

$\displaystyle\Delta^{x}_{k+1}=\Delta
f^{x}_{k}+(G^{+}+G^{++})\Delta^{d}_{k}+\Delta w,$ (17)

where $\Delta^{x}_{k}\triangleq\overline{x}_{k}-\underline{x}_{k}$,
$\Delta^{d}_{k}\triangleq\overline{d}_{k}-\underline{d}_{k}$, $\Delta
f^{x}_{k}\triangleq
f_{d}(\overline{x}_{k},\underline{x}_{k})-f_{d}(\underline{x}_{k},\overline{x}_{k})$
and $\Delta w\triangleq\overline{w}-\underline{w}$. Moreover, from (7) and
(8),

$\displaystyle\Delta^{d}_{k}\leq\Delta^{d,1}_{k}=(J^{+}+J^{++})\Delta^{r}_{k},$
(18)

where $\Delta^{d,1}_{k}\triangleq\overline{d}^{1}_{k}-\underline{d}^{1}_{k}$
and $\Delta^{r}_{k}\triangleq\overline{r}_{k}-\underline{r}_{k}$, while from
the definitions of $\overline{r}_{k}$ and $\underline{r}_{k}$ in (11)–(12), we
have

$\displaystyle\Delta^{r}_{k}=\Delta g^{x}_{k}+\Delta v,$ (19)

where $\Delta g^{x}_{k}\triangleq
g_{d}(\overline{x}_{k},\underline{x}_{k})-g_{d}(\underline{x}_{k},\overline{x}_{k})$
and $\Delta v\triangleq\overline{v}-\underline{v}$. Combining (17)–(19) and
using the fact that $G^{+},G^{++},J^{+},J^{++}\geq 0$ and Proposition 1, we
obtain

$\displaystyle\Delta^{x}_{k+1}\leq\Delta h^{x}_{k}+\Delta z,$ (20)

where $K\triangleq(G^{+}+G^{++})(J^{+}+J^{++})$, $\Delta
h^{x}_{k}\triangleq\Delta f^{x}_{k}+K\Delta g^{x}_{k}$ and $\Delta
z\triangleq\Delta w+K\Delta v$. Now, consider the following dynamical system

$\displaystyle\Delta^{s}_{k+1}=\Delta h^{s}_{k}+\Delta z,$ (21)

where $\Delta^{s}_{k}\in\mathbb{R}^{n}$ and $\Delta^{s}_{0}=\Delta^{x}_{0}$.
By non-negativity of $\Delta^{x}_{k}$ and _Comparison Lemma_ [24, Lemma 3.4],
$0\leq\Delta^{x}_{k}\leq\Delta^{s}_{k},\forall k\geq 0$. So, boundedness of
$\\{\Delta^{s}_{k}\\}_{k=0}^{\infty}$ (shown below) implies boundedness of
$\\{\Delta^{x}_{k}\\}_{k=0}^{\infty}$.

Condition (i): Since Assumption 3 holds, the application of triangle
inequality to (20) yields

$\displaystyle\|\Delta^{x}_{k+1}\|\leq\mathcal{L}\|\Delta^{x}_{k}\|+\|\Delta
z\|,$ (22)

where $\mathcal{L}=L_{f_{d}}+L_{g_{d}}\|K\|$, with $L_{f_{d}}$ and $L_{g_{d}}$
given in Lemma 1. Since $\mathcal{L}<1$ (by Condition (i)), by _Comparison
Lemma_ [24, Lemma 3.4], the $\\{\|\Delta^{x}_{k}\|\\}_{k=0}^{\infty}$ is
bounded. Therefore, the interval width dynamics is stable.

Condition (ii): To show that Condition (ii) implies stability, consider a
candidate Lyapunov function $V_{k}=\Delta^{s\top}_{k}\Delta^{s}_{k}$ for (21)
that can be shown to satisfy $\Delta V_{k}\triangleq V_{k+1}-V_{k}\leq 0$
under Condition (ii) as follows:

$\displaystyle\Delta V_{k}\triangleq V_{k+1}-V_{k}$ $\displaystyle=\Delta
f^{s\top}_{k}\Delta f^{s}_{k}+\Delta g^{s\top}_{k}K^{\top}K\Delta
g^{s}_{k}+\Delta v^{\top}K^{\top}K\Delta v+\Delta w^{\top}\Delta w$
$\displaystyle\ \ -\Delta^{s\top}_{k}\Delta^{s}_{k}+2(\Delta
f^{s\top}_{k}K\Delta g^{s}_{k}+\Delta f^{s\top}K\Delta v+\Delta
f^{s\top}\Delta w$ $\displaystyle\ \ +\Delta g^{s\top}K^{\top}K\Delta v+\Delta
g^{s\top}K^{\top}\Delta w+\Delta v^{\top}K^{\top}\Delta w)$
$\displaystyle\leq(L^{2}_{f_{d}}+\lambda_{\max}(K^{\top}K)L^{2}_{g_{d}}-1)\Delta^{s\top}_{k}\Delta^{s}_{k}+\Delta
v^{\top}K^{\top}K\Delta v$ $\displaystyle\ \ +\Delta w^{\top}\Delta w+2(\Delta
f^{s\top}_{k}K\Delta g^{s}_{k}+\Delta f^{s\top}K\Delta v+\Delta
f^{s\top}\Delta w$ $\displaystyle\ \ +\Delta g^{s\top}K^{\top}K\Delta v+\Delta
g^{s\top}K^{\top}\Delta w+\Delta v^{\top}K^{\top}\Delta w)$
$\displaystyle=\begin{bmatrix}\Delta^{s}_{k}\\\ \Delta v\\\ \Delta w\\\ \Delta
f^{s}_{k}\\\ \Delta g^{s}_{k}\end{bmatrix}^{\top}\begin{bmatrix}F&0&0&0&0\\\
*&K^{\top}K&K^{\top}&K^{\top}&K^{\top}K\\\ *&*&I&I&K\\\ *&*&*&0&K\\\
*&*&*&*&0\end{bmatrix}\begin{bmatrix}\Delta^{s}_{k}\\\ \Delta v\\\ \Delta w\\\
\Delta f^{s}_{k}\\\ \Delta g^{s}_{k}\end{bmatrix}\leq 0,$

where the first inequality holds since $\Delta f^{s\top}_{k}\Delta
f^{s}_{k}=\|\Delta f^{s}_{k}\|^{2}\leq L^{2}_{f_{d}}\|\Delta^{s}_{k}\|^{2}$ by
Lemma 1 and $\Delta g^{s\top}_{k}K^{\top}K\Delta
g^{s}_{k}\leq\lambda_{\max}(K^{\top}K)\Delta g^{s\top}_{k}\Delta
g^{s}_{k}=\lambda_{\max}(K^{\top}K)\|\Delta g^{s}_{k}\|^{2}\leq
L^{2}_{g_{d}}\lambda_{\max}(K^{\top}K)\|\Delta^{s}_{k}\|^{2}$ by using the
_Rayleigh Quotient_ and Lemma 1, and the last inequality holds by Condition
(ii). Thus, $\Delta_{k}^{s}$ is bounded and so is $\Delta_{k}^{x}$ by the
Comparison Lemma (i.e., the dynamics of $\Delta^{x}_{k}$ is stable).

Condition (iii): Similarly, we consider a candidate Lyapunov function
$V_{k}=\Delta^{s\top}_{k}P\Delta^{s}_{k}$, where $P\succ 0$, which can be
shown to satisfy $\Delta V_{k}\triangleq V_{k+1}-V_{k}\leq 0$ under Condition
(iii). To show this, note that $\Delta h^{s\top}_{k}\Lambda\Delta
h^{s}_{k}\leq\Delta h^{s\top}_{k}\Delta
h^{s}_{k}\leq\mathcal{L}^{2}\Delta^{s\top}_{k}\Delta^{s}_{k}$, where the
inequalities hold by choosing $\Gamma$ such that $\Gamma\triangleq
I-\Lambda\succeq 0$ and Lemma 1, respectively. Consequently,
$\mathcal{L}^{2}\Delta^{s\top}_{k}\Delta^{s}_{k}-\Delta
h^{s\top}_{k}\Lambda\Delta h^{s}_{k}\geq 0$. Then, inspired by a simplifying
trick used in [25, Proof of Theorem 1] to satisfy $\Delta V_{k}\leq 0$, it
suffices to guarantee that $\tilde{V}_{k}\triangleq\Delta
V_{k}+\mathcal{L}^{2}\Delta^{s\top}_{k}\Delta^{s}_{k}-\Delta
h^{s\top}_{k}\Lambda\Delta h^{s}_{k}=\Delta
V_{k}+\mathcal{L}^{2}\Delta^{s\top}_{k}\Delta^{s}_{k}-\Delta
h^{s\top}_{k}(I-{\Gamma})\Delta h^{s}_{k}\leq 0$, where $\tilde{V}_{k}$ is
also given by

$\displaystyle\tilde{V}_{k}$ $\displaystyle=\Delta h^{s\top}_{k}P\Delta
h^{s}_{k}+\Delta z^{\top}P\Delta z+2\Delta z^{\top}P\Delta
h^{s}_{k}-\Delta^{s\top}_{k}P\Delta^{s}_{k}$ $\displaystyle\ \
+\mathcal{L}^{2}\Delta^{s\top}_{k}\Delta^{s}_{k}-\Delta
h^{s\top}_{k}(I-{\Gamma})\Delta h^{s}_{k}$ $\displaystyle=\Delta
h^{s\top}_{k}(P+\Gamma-I)\Delta
h^{s}_{k}+\Delta^{s\top}_{k}(\mathcal{L}^{2}I-P)\Delta^{s}_{k}$
$\displaystyle\ \ +\Delta z^{\top}P\Delta z+2\Delta z^{\top}P\Delta h^{s}_{k}$
$\displaystyle=\begin{bmatrix}\Delta h^{s}_{k}\\\ \Delta^{s}_{k}\\\ \Delta
z\end{bmatrix}^{\top}\begin{bmatrix}P+\Gamma-I&0&P\\\
0&\mathcal{L}^{2}I-P&0\\\ P&0&P\end{bmatrix}\begin{bmatrix}\Delta h^{s}_{k}\\\
\Delta^{s}_{k}\\\ \Delta z\end{bmatrix}\leq 0,$

which along with $\Gamma\succeq 0$ is equivalent to Condition (iii). Finally,
since $\Delta V_{k}\leq 0$, $\Delta_{k}^{s}$ is bounded and so are the
interval width sequences $\\{\Delta_{k}^{x}\\}_{k=0}^{\infty}$ by the
Comparison Lemma (i.e., the dynamics of $\Delta^{x}_{k}$ is stable). ∎

###  VI-D Proof of  Lemma 2

Applying (22) repeatedly, we have

$\displaystyle\|\Delta^{x}_{k}\|\leq\mathcal{L}^{k}\|\Delta^{x}_{0}\|+\textstyle{\sum}_{i=0}^{k-1}\mathcal{L}^{k-i}\|\Delta
z\|=\mathcal{L}^{k}\delta_{0}^{x}+\|\Delta
z\|\frac{1-\mathcal{L}^{k}}{1-\mathcal{L}}.$

Similarly, by applying Lemma 1 and triangle inequality to (18) and (19), we
obtain the upper bound $\|\Delta^{d}_{k}\|$.  If $\mathcal{L}<1$,  then taking
the limit of $k$ to $\infty$,  returns $\overline{\delta}^{x}$ and
$\overline{\delta}^{d}$.  The rest of the results follow from the non-
increasing Lyapunov functions defined in the proof of Theorem 2, as well as
the fact that $\lambda_{\min}(A)\|x\|^{2}\leq x^{\top}Ax,\forall
x\in\mathbb{R}^{n},A\in\mathbb{R}^{n\times n}$. ∎