# State Estimation for Control Systems with a Multiplicative Uncertainty through Polyhedral Techniques

Elena K. Kostousova

► To cite this version:

Elena K. Kostousova. State Estimation for Control Systems with a Multiplicative Uncertainty through Polyhedral Techniques. 25th System Modeling and Optimization (CSMO), Sep 2011, Berlin, Germany. pp.165-176, 10.1007/978-3-642-36062-6_17. hal-01347534

HAL Id: hal-01347534

https://inria.hal.science/hal-01347534v1

Submitted on 21 Jul 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# State Estimation for Control Systems with a Multiplicative Uncertainty through Polyhedral Techniques

Elena K. Kostousova

Institute of Mathematics and Mechanics,
Ural Branch of the Russian Academy of Sciences,
16, S.Kovalevskaja street, Ekaterinburg, 620990, Russia
kek@imm.uran.ru

**Abstract.** The paper deals with polyhedral estimates for reachable tubes of differential systems with a multiplicative uncertainty, namely linear systems with set-valued uncertainties in initial states, additive inputs and coefficients of the system. We present nonlinear parametrized systems of ordinary differential equations (ODE) which describe the evolution of the parallelotope-valued estimates for reachable sets (time cross-sections of the reachable tubes). The main results are obtained for internal estimates. In fact, a whole family of the internal estimates is introduced. The properties of the obtained ODE systems (such as existence and uniqueness of solutions, nondegeneracy of estimates) are investigated. Using some optimization procedure we also obtain a differential inclusion which provides nondegenerate internal estimates. Examples of numerically constructed external and internal estimates are presented.

**Keywords:** Differential systems, reachable sets, set-valued state estimation, multiplicative uncertainty, polyhedral estimates, parallelepipeds, parallelotopes, interval analysis.

## 1 Introduction

The problem of constructing trajectory tubes (in particular, reachable tubes) is an essential theme in control theory [25]. Since practical construction of such tubes may be cumbersome, different numerical methods are devised for this cause, in particular, methods based on approximations of sets either by arbitrary polytopes with a large number of vertices or by unions of points [6], [3], [1] (here and below, we mention, as examples, only some references from numerous publications; see also references therein). Such methods, as well as the methods based on different schemes of discrete approximations of initial set-valued problems [2], [31] and numerical methods of solving the Hamilton-Jacobi-Bellman equation [30], are devised to obtain approximations as accurate as possible. But they may require much calculations, especially for large dimensional systems; also smaller step-sizes create a heavy computational load. It is appropriate to
mention approximations by polytopes based on support functions or supporting points [4], [23].

Other techniques are based on estimates of sets by domains of some fixed shape such as ellipsoids, parallelepipeds, zonotopes [7], [11], [13], [15]-[17], [22], [24]-[29]. Fair results in this area were obtained for linear systems with set-valued initial states and set-valued additive uncertain inputs. The main advantage of the mentioned techniques is that they enable to obtain approximate solutions using relatively simple tools (up to explicit formulas). Note that more accurate approximations and even exact representations of the solutions may be obtained by using the whole families of such simple estimates (as it was proposed by A.B. Kurzhanski) [25]-[27], [22], [16]. The methods of interval analysis which use subpavings of interval vectors [14] serve the same purpose, but such methods may require much computations and memory for large dimensional systems.

It is also important to study linear systems when system matrices are uncer-
tain too. This leads to the multiplicative uncertainty and additional difficulties
due to nonlinearity of the problem (in particular, reachable sets — cross-sections
of reachable tubes — can be non-convex). There are some results for such systems
with different types of bounds on uncertainties [5], [8], [12], including construct-
ing external ellipsoidal estimates [7], [29] and external interval (in other terms,
coordinate-wise or box-valued) estimates [15], [24], [28].

We construct polyhedral (parallelepiped-valued and parallelotope-valued) es-
timates for reachable sets and reachable tubes of differential systems with pa-
rallelepiped-valued uncertainties in initial states and in additive uncertain inputs
and with interval uncertainties in coefficients of the system. In contrast to in-
terval analysis, faces of our estimates may be not parallel to coordinate planes.
The main results are obtained for the internal estimates. Using constructions
from [19], [20], we obtain nonlinear parametrized systems of ordinary differen-
tial equations (ODE) which describe the evolution of centers and matrices of
the parallelotope-valued internal estimates for the reachable sets. So, in fact, the
whole family of internal estimates is introduced (but, unfortunately, unlike the
case of linear systems [25]-[27], [22], [16], this family does not ensure exact repre-
sentations of the reachable sets in general). The properties of the obtained ODE
systems (such as existence and uniqueness of solutions for fixed values of param-
eters, nondegeneracy of estimates) are investigated. Using some optimization
procedure we also obtain a differential inclusion which provides nondegenerate
internal estimates. ODE for external estimates were obtained earlier [18]. Here
we remind these results for completeness of the exposition. Results of numerical
simulations are presented.

The following notation is used below: $\mathbb{R}^n$ — the $n$-dimensional vector space;
$\top$ — the transposition symbol; $\|x\|_1 = \sum_{i=1}^n |x_i|$, $\|x\|_2 = (x^\top x)^{1/2}$, $\|x\|_\infty =
\max_{1 \le i \le n} |x_i|$ — vector norms for $x = (x_1, x_2, \ldots, x_n)^\top \in \mathbb{R}^n$; $e^i = (0, \ldots, 0, 1, 0, \ldots, 0)^\top$
— the unit vector oriented along the axis $0x_i$ (the unit stands at $i$-position);
$e = (1, 1, \ldots, 1)^\top$; $\mathbb{R}^{n \times m}$ — the space of real $n \times m$-matrices $A =
\{a_i^j\} = \{a^j\}$ (with columns $a^j$); $I$ — the unit matrix; $0$ — the zero matrix
(vector); $\text{Abs } A = \{|a_i^j|\}$ for $A = \{a_i^j\}$; $\text{diag } \pi$, $\text{diag } \{\pi_i\}$ — the diagonal matrix
A with $a_i^i = \pi_i$ ($\pi_i$ — the components of the vector $\pi$); det $A$ — the determinant of $A \in \mathbb{R}^{n \times n}$; tr $A = \sum_{i=1}^n a_i^i$ — the trace of $A$; $\|A\| = \max_{1 \le i \le n} \sum_{j=1}^m |a_i^j|$ — the matrix norm for $A \in \mathbb{R}^{n \times m}$ induced by the vector norm $\|x\|_\infty$; the notation of the type $k = 1, \dots, N$ is used instead of $k = 1, 2, \dots, N$ for shortening.

## 2 Problem Formulation

Consider the following system ($x \in \mathbb{R}^n$ is the state):

$$ \dot{x} = A(t)x + w(t), \quad t \in T = [0, \theta]. \qquad (1) $$

Here the initial state $x(0) = x_0 \in \mathbb{R}^n$, the input (control/disturbance) $w(t) \in \mathbb{R}^n$ (which is assumed to be a Lebesgue measurable function) and the measurable matrix function $A(t) \in \mathbb{R}^{n \times n}$ are unknown but subjected to given set-valued constraints

$$ x_0 \in \mathcal{X}_0, \quad w(t) \in \mathcal{R}(t), \quad \text{a.e. } t \in T, \qquad (2) $$

$$ A(t) \in \mathcal{A}(t) = \{A \in \mathbb{R}^{n \times n} | \underline{A}(t) \le A \le \bar{A}(t)\}, \quad \text{a.e. } t \in T, \qquad (3) $$

where $\mathcal{X}_0, \mathcal{R}(t)$ are given convex compact sets in $\mathbb{R}^n$, the set-valued map $\mathcal{R}(t)$ is continuous, the matrix functions $\underline{A}(t), \bar{A}(t)$ are continuous. Matrix and vector inequalities ($\le, <, \ge,>$) here and below are understood componentwise. The interval constraints (3) can be rewritten in the form

$$ A(t) \in \mathcal{A}(t) = \{A | \text{Abs}(A - \tilde{A}(t)) \le \hat{A}(t)\}, \quad \tilde{A} = (\underline{A} + \bar{A})/2, \quad \hat{A} = (\bar{A} - \underline{A})/2. \qquad (4) $$

Let $\mathcal{X}(t)=\mathcal{X}(t, 0, \mathcal{X}_0)$ be a reachable set of system (1)–(3) at time $t>0$ that is the set of all points $x \in \mathbb{R}^n$, for each of which there exist $x_0, w(\cdot), A(\cdot)$ that satisfy (2)–(3) and generate a solution $x(\cdot)$ of (1) that satisfies $x(t)=x$. The multivalued function $\mathcal{X}(t), t \in T$, is known as a trajectory (or reachable) tube $\mathcal{X}(\cdot)$.

We presume the sets $\mathcal{X}_0, \mathcal{R}(t)$ to be paralleloptes (then the sets $\mathcal{X}(t)$ are not obliged to be paralleloptopes) and look for external and internal parallelepiped-valued or parallelotope-valued (shorter, polyhedral) estimates $\mathcal{P}^{\pm}(t)$ for $\mathcal{X}(t)$.

By a parallelepiped $\mathcal{P}(p, P, \pi) \subset \mathbb{R}^n$ we mean a set such that $\mathcal{P}=\mathcal{P}(p, P, \pi) = \{x \in \mathbb{R}^n | x=p+\sum_{i=1}^n p^i \pi_i \xi_i, \|\xi\|_{\infty} \le 1\}$, where $p \in \mathbb{R}^n$; $P=\{p^i\} \in \mathbb{R}^{n \times n}$ is such that det $P \ne 0, \|p^i\|_2=1$; $\pi \in \mathbb{R}^n, \pi \ge 0$. It may be said that $p$ determines the center of the parallelepiped, $P$ — the orientation matrix, $p^i$ — the “directions” and $\pi_i$ — the values of its “semi-axes”. We call a parallelepiped nondegenerate if $\pi>0$.

By a parallelootope $\mathcal{P}[p, \bar{P}] \subset \mathbb{R}^n$ we mean a set $\mathcal{P} = \mathcal{P}[p, \bar{P}] = \{x \in \mathbb{R}^n | x = p+\bar{P}\zeta, \|\zeta\|_{\infty} \le 1\}$, where $p \in \mathbb{R}^n$ and the matrix $\bar{P} = \{\bar{p}^i\} \in \mathbb{R}^{n \times m}, m \le n$, may be singular. We call a parallelootope $\mathcal{P}$ nondegenerate, if $m=n$ and det $\bar{P} \ne 0$.

Each parallelepiped $\mathcal{P}(p, P, \pi)$ is a parallelootope $\mathcal{P}[p, \bar{P}]$ with $\bar{P} = P \text{diag } \pi$; each nondegenerate parallelootope is a parallelepiped with $P=\bar{P} \text{diag } \{\|\bar{p}^i\|_2^{-1}\}$, $\pi_i = \|\bar{p}^i\|_2$ or, in a different way, with $P = \bar{P}, \pi = e$, where $e = (1, 1, \dots, 1)^T$.

We call $\mathcal{P}$ an external (internal) estimate for $\mathcal{X} \subset \mathbb{R}^n$ if $\mathcal{P} \supseteq \mathcal{X}$ ($\mathcal{P} \subseteq \mathcal{X}$).

<footnote n="1">¹ The normality condition $\|p^i\|_2=1$ may be omitted to simplify formulas (it ensures the uniqueness of the representation of a nondegenerate parallelepiped).</footnote>
Assumption 1. The set $\mathcal{X}_0 = \mathcal{P}_0 = \mathcal{P}[p_0, \bar{P}_0] = \mathcal{P}(p_0, P_0, \pi_0)$ is a parallelepiped, the sets $\mathcal{R}(t) = \mathcal{P}[r(t), \bar{R}(t)]$ are parallelotopes where $\bar{R}(t) \in \mathbb{R}^{n \times m}$, $m \le n$; $r(\cdot), \bar{R}(\cdot)$ and $\underline{A}(\cdot), \bar{A}(\cdot)$ are continuous vector and matrix functions.

Problem 1. Find some external $\mathcal{P}^+(t)$ and internal $\mathcal{P}^-(t)$ polyhedral estimates<fnref n="2" /> for reachable sets $\mathcal{X}(t): \mathcal{P}^-(t) \subseteq \mathcal{X}(t) \subseteq \mathcal{P}^+(t)$, $t \in T$.

### 3 Auxiliary Discrete Time Systems. Primary Estimates

Following arguments similar to [7], [25, Sec. 3.2] we obtain ODE for the estimates. The first step in this way is to construct estimates for reachable sets $\mathcal{X}[k]$ of auxiliary discrete time systems – the Euler approximations<fnref n="3" /> of the initial system:

$$ 
\begin{align} 
x[k] &= A[k-1]x[k-1] + w[k-1], \quad k=1, \dots, N; \quad x[0] \in \mathcal{P}_0; \tag{5} \\ 
w[k] &\in \mathcal{R}[k] = h_N \mathcal{R}(t_k); \quad A[k] \in \mathcal{A}[k] = \{I + h_N A \mid A \in \mathcal{A}(t_k)\}, \nonumber 
\end{align} 
$$

$t_k=kh_N$, $h_N=\theta N^{-1}$. It is known that $\mathcal{X}[k]$ satisfy the relations $\mathcal{X}[k] = \mathcal{A}[k-1] \circ \mathcal{X}[k-1] + \mathcal{R}[k-1]$, $k=1, \dots, N$, $\mathcal{X}[0] = \mathcal{P}_0$, which involve two operations with sets $\mathcal{A} = \{A \in \mathbb{R}^{n \times n} | A \le A \le \bar{A}\}$ on a set $\mathcal{X} \subset \mathbb{R}^n$: $\mathcal{A} \circ \mathcal{X} = \{y \in \mathbb{R}^n | y = Ax, A \in \mathcal{A}, x \in \mathcal{X}\}$ and the Minkowski sum [25, p.93].

In [18], [19], [20], the ways of constructing primary polyhedral estimates for $\mathcal{A} \circ \mathcal{P}$ and $\mathcal{P}^1 + \mathcal{P}^2$ (where $\mathcal{P}, \mathcal{P}^1, \mathcal{P}^2$ are parallelepipeds or parallelotopes) are described; hence we have the corresponding recurrence relations for external and internal estimates $\mathcal{P}^{\pm}[k]$ for $\mathcal{X}[k]$. Passing to the limit as $N \to \infty$, we obtain the corresponding nonlinear ODE systems for parallelotopes/parallelepipeds $\mathcal{P}^{\pm}(t)$.

### 4 Internal Estimates

We come to the following ODE system for parallelotopes $\mathcal{P}^-(t) = \mathcal{P}[p^-(t), \bar{P}^-(t)]$:

$$ \frac{dp^-}{dt} = \tilde{A}(t) p^- + r(t), \quad p^-(0) = p_0; \qquad (6) $$

$$ 
\begin{align} 
\frac{d\bar{P}^-}{dt} &= \tilde{A}(t) \bar{P}^- + \operatorname{diag} \nu(t, \bar{P}^-; J(t)) \cdot B(\bar{P}^-) + \bar{R}(t) \Gamma(t), \quad \bar{P}^-(0) = \bar{P}_0, \nonumber \\ 
\nu_i(t, \bar{P}^-; J) &= \hat{a}_i^{ji}(t) \cdot \eta_{ji}(t, \bar{P}^-), \quad i = 1, \dots, n, \nonumber \\ 
\eta(t, \bar{P}^-) &= \max\{0, \operatorname{Abs} p^-(t) - (\operatorname{Abs} \bar{P}^-)e\}, \nonumber \\ 
B &= \operatorname{diag} \beta(\bar{P}^-) \cdot \bar{P}^-, \quad \beta_i(\bar{P}^-) = 1 / (e^{i\top}(\operatorname{Abs} \bar{P}^-)e), \quad i = 1, \dots, n, \tag{7} 
\end{align} 
$$

<footnote n="2">² Our estimates will satisfy the upper and lower semigroup properties and the superreachability and subreachability properties similarly to [25, Lemmas 3.3.2, 3.3.4] and [7, Remark 8.2] respectively; these properties are analogues to the semigroup property [25, p.9] for $\mathcal{X}(t)$. Also our set-valued estimates will be continuous.</footnote>

<footnote n="3">³ In connection with the Euler approximations, the papers [9], [32] may be mentioned which analyzed the numerical error of the set-valued method.</footnote>
(the operation of maximum is understood componentwise). Here $\Gamma(t) \in \mathbb{R}^{m \times n}$ is an arbitrary Lebesgue measurable matrix function satisfying $\|\Gamma(t)\| = \max_{1 \le i \le m} \sum_{j=1}^n |\gamma_i^j| \le 1$, a.e. $t \in T$, and $J = \{j_1, \dots, j_n\}$ is an arbitrary permutation of numbers $\{1, \dots, n\}$ or even a measurable vector function $J(\cdot)$ with values $J(t)$ being arbitrary permutations of numbers $\{1, \dots, n\}$. Let $\mathbb{G}$ and $\mathbb{J}$ be the sets of all such functions $\Gamma(\cdot)$ and $J(\cdot)$ respectively.

Later on it is useful to mark out the following case.

**Assumption 2.** Either $\mathcal{R}(t)$ are singletons (then the function $w(\cdot) \equiv r(\cdot)$ may be assumed to be measurable) or $\Gamma(\cdot) \in \mathbb{G}$ is such that $\bar{R}(t)\Gamma(t) \equiv 0$, $t \in T$.

**Theorem 1.** Let the above assumptions about the system (1), (2), (4) be satisfied, $P_0$ be a nondegenerate parallelotope (det $\bar{P}_0 \neq 0$) and $J(\cdot) \in \mathbb{J}$, $\Gamma(\cdot) \in \mathbb{G}$. Then the system (6), (7) has a unique solution $(p^-(\cdot), \bar{P}^-(\cdot))$ at least on some subinterval $T_1 = [0, \theta_1] \subseteq T$, where $0 < \theta_1 \le \theta$, and we have $\det \bar{P}^-(t) \ne 0$, $t \in T_1$. The corresponding nondegenerate parallelotopes $\mathcal{P}^-(t) = \mathcal{P}[p^-(t), \bar{P}^-(t)]$, $t \in T_1$, are internal estimates for the reachable sets $\mathcal{X}(t)$ of the system (1), (2), (4): $\mathcal{P}^-(t) \subseteq \mathcal{X}(t)$, $t \in T_1$. Under Assumption 2, the subinterval $T_1$ coincide with $T$.

*Proof.* Here and below we give mostly only sketches; more details can be found in [21]. The existence, uniqueness and extendability of the solution are obtained using the known results [10, pp. 7,8,10]. In particular, under Assumption 2, we verify that $\mathcal{P}^-(t)$ can not leave the domain where $\det \mathcal{P}^-(t) \ge \delta$ for some $\delta > 0$ and then use [10, p. 10, Theorem 4].

To prove $\mathcal{P}^-(t) \subseteq \mathcal{X}(t)$ we verify the subreachability property: $\mathcal{P}^-(t) \subseteq \mathcal{X}(t, s, \mathcal{P}^-(s))$, $\forall s, t: 0 \le s \le t \le \theta_1$. Fix $t \in T_1$. If $x^* \in \mathcal{P}^-(t)$, then there exists $\xi$ such that $\text{Abs } \xi \le e$ and $x^* = p^-(t) + \bar{P}^-(t)\xi$. Consider $x^* = x^*(t)$ as a function of $t$ (when $\xi$ is fixed). Evidently, $x^*(s) \in \mathcal{P}^-(s)$ also for arbitrary $s \le t$. It remains to check that it is possible to find functions $A(\tau) = \tilde{A}(\tau) + \Delta A(\tau) \in \mathcal{A}(\tau)$ and $w(\tau) \in \mathcal{R}(\tau)$, $\tau \in [s, t]$, such that $x^*(\tau)$ will satisfy (1) for $\tau \in [s, t]$. Differentiating $x^*(\tau)$ with the account (6), (7) we have (the argument $\tau$ is omitted for short): $\dot{x}^* = \tilde{A}x^* + w + \text{diag } \nu B \xi = Ax^* + w + q$, where $w = r + \bar{R}\Gamma\xi \in \mathcal{R}$ (because $\|\Gamma\xi\|_{\infty} \le \|\Gamma\| \|\xi\|_{\infty} \le 1$), $A = \tilde{A} + \Delta A$, $q = \text{diag } \nu B \xi - \Delta A(p^- + \bar{P}^-\xi)$. The desired equality $q = 0$ is achieved if we take $\Delta A$ in the form $\Delta A = \text{diag } \alpha D$, where $D = \{e^{j_1} \cdots e^{j_n}\}^\top$ is a matrix corresponding to a permutation $J=\{j_1, \dots, j_n\}=J(\tau)$ of rows of the unit matrix, and components of the vector $\alpha = \alpha(\tau)$ are calculated by formulas $\alpha_i = 0$, if $|p_{\bar{j}_i}| \le e^{j_i \top} (\text{Abs } \bar{P}^-) e$ (i.e. if $\nu_i = 0$), and $\alpha_i = \nu_i e^{i \top} B \xi / (p_{\bar{j}_i} + e^{j_i \top} \bar{P}^- \xi)$ otherwise. Inequalities $|\alpha_i| \le \hat{a}_{i}^{j_i}$, $i = 1, \dots, n$ (which ensure $A \in \mathcal{A}$) are obtained by obvious estimates. $\square$

Note that Theorem 1 describes the whole family of estimates $\mathcal{P}^-(\cdot)$ where $J(\cdot)$ and $\Gamma(\cdot)$ are parameters.

**Remark 1.** Obviously, we have $\mathcal{X}(t) \supseteq \mathcal{X}^0(t) \equiv \mathcal{P}^{0-}(t)$, $t \in T$, where $\mathcal{X}^0(t)$ are reachable sets of the system (1) under assumptions $x_0 \in \mathcal{P}_0$, $w(\cdot) \equiv r(\cdot)$ and $A(\cdot) \equiv \tilde{A}(\cdot)$, and parallelotopes $\mathcal{P}^{0-}(t)$ are determined by (6), (7) when $\nu \equiv 0$, $\Gamma \equiv 0$. We call these parallelotopes $\mathcal{P}^{0-}(t)$ trivial internal estimates for $\mathcal{X}(t)$.
The following corollary compares internal estimates $\mathcal{P}^-(t)$ for $\mathcal{X}(t)$ satisfying (6), (7) with trivial internal estimates $\mathcal{P}^{0-}(t)$ for $\mathcal{X}(t)$ in the sense of volume. We like to remind that volume of a nondegenerate parallelootope $\mathcal{P} = \mathcal{P}[p, \bar{P}] \subset \mathbb{R}^n$ is equal to $\text{vol} \mathcal{P} = 2^n |\det \bar{P}|$.

**Corollary 1.** Under conditions of Theorem 1, we have $\text{vol} \mathcal{P}^-(t) = \text{vol} \mathcal{P}^{0-}(t) \cdot \exp(\psi_1(t) + \psi_2(t))$, $t \in T_1$, where $\psi_1(t) = \int_0^t \nu(\tau, \bar{P}^-(\tau); J(\tau))^{\top} \beta(\bar{P}^-(\tau)) d\tau$, $\psi_2(t) = \int_0^t \text{tr}(\Xi(\tau, \bar{P}^-(\tau))\Gamma(\tau)) d\tau$, $\Xi(t, \bar{P}^-) = (\bar{P}^-)^{-1}\bar{R}(t)$.

Therefore under additional Assumption 2 we have:

(i) $\text{vol} \mathcal{P}^-(t) \ge \text{vol} \mathcal{P}^{0-}(t)$, and $\text{vol} \mathcal{P}^-(t) > \text{vol} \mathcal{P}^{0-}(t)$ iff $\psi_1(t) > 0$;

(ii) if it is turned out that $\mathcal{P}^-(t) \not\equiv 0$ for all $t \in T$, then $\mathcal{P}^-(t) \equiv \mathcal{P}^{0-}(t)$, $t \in T$.

*Proof.* The expression for $\text{vol} \mathcal{P}^-(t)$ follows from the equality $\det \bar{P}^-(t) = m_0(t) \cdot \exp(\psi_1(t) + \psi_2(t))$, where $m_0(t) = \det \bar{P}_0 \exp \int_0^t \text{tr} \tilde{A}(\tau) d\tau$, which, in turn, can be obtained similarly to [17, p. 293]. Namely, we use the change of variables $\bar{P}^-(t) = \Phi(t) P(t)$, where $\Phi$ satisfies $\dot{\Phi} = \tilde{A}\Phi$, $\Phi(0) = I$, and obtain the relation

$$ \frac{d \det \bar{P}}{dt} / \det \bar{P} = \nu(t, \bar{P}^-(t); J(t))^{\top} \beta(\bar{P}^-(t)) + \text{tr}((\bar{P}^-(t))^{-1} \bar{R} \Gamma) \quad (8) $$

on the base of the known relation $d \det \bar{P}/dt = \det \bar{P} \text{tr}(\bar{P}^{-1}\dot{\bar{P}})$ and (7); then the Liouville formula $\det \Phi(t) = \exp \int_0^t \text{tr} \tilde{A}(\tau) d\tau$ is used.

Assumption 2 yields $\psi_2(t) \equiv 0$. Thus (i) is evident, (ii) is true because we have $\psi_1(t) \equiv 0$ similarly to [20, Corollary 1]. □

In general case (without Assumption 2) we can obtain some differential inclusions which determine internal estimates on the whole time interval $T$. Consider two ways to do that. Following the first way, fix $J(\cdot) \in \mathbb{J}$ and $\Gamma(\cdot) \in \mathbb{G}$; if a denominator of some row of the matrix $B$ vanishes, replace this row by a suitable set. The corresponding differential inclusion determines $\mathcal{P}^-(t)$ on $T$ (see Theorem 2 below), but there is no guarantee for $\mathcal{P}^-(t)$ to be nondegenerate. The second way allows (using some considerations of “local” optimality of the estimate volume) to construct $\Gamma(\cdot)$ to ensure nondegenerate estimates on $T$ (Theorem 3).

Following the first way, consider the matrix differential inclusion

$$ \frac{d\bar{P}^{-}}{dt} \in \tilde{A}(t)\bar{P}^{-} + \text{diag } \nu(t, \bar{P}^{-}; J(t)) \cdot \mathbf{B}(\bar{P}^{-}) + \bar{R}(t)\Gamma(t), \quad \bar{P}^{-}(0) = \bar{P}_{0}, \quad (9) $$

where $\nu(t, \bar{P}^{-}; J(t))$ is defined in (7), and $\mathbf{B}(\bar{P}^{-})$ is the set of all matrices $B(\bar{P}^{-})$ such that each row $e^{i\top} \mathbf{B}$ ($i=1, \dots, n$) satisfy the following conditions

$$ e^{i\top} \mathbf{B} = \begin{cases} e^{i\top} \bar{P}^{-} / (e^{i\top}(\text{Abs } \bar{P}^{-}) e), & \text{if } e^{i\top}(\text{Abs } \bar{P}^{-}) e \neq 0, \\ \text{arbitrary row such that } \|e^{i\top} \mathbf{B}\|_{1} \le 1, & \text{if } e^{i\top}(\text{Abs } \bar{P}^{-}) e = 0. \end{cases} \quad (10) $$

**Theorem 2.** For arbitrary $J(\cdot) \in \mathbb{J}$, $\Gamma(\cdot) \in \mathbb{G}$, there exists a solution $(p^-(\cdot), \bar{P}^-(\cdot))$ of the system (6), (9)-(10) which is determined on the whole $T$, and all solutions of this system determine internal parallelootope-valued estimates $\mathcal{P}^-(t)$ for $\mathcal{X}(t)$, $t \in T$.
Proof. Existence and extendability are obtained using [10, p. 66, Theorem 6]. The inclusions $\mathcal{P}^-(t) \subseteq \mathcal{X}(t)$ are proved similarly to Theorem 1. $\square$

Following the second way under conditions of Theorem 1, assume, without loss of generality, that $\det \bar{P}_0 > 0$. The idea of local optimization arises from (8) and consists in finding the maximal possible velocity of increasing $\det \bar{P}^-(t)$ (therefore $\mathrm{vol} \mathcal{P}^-(t)$) at time $t$, by the choice of the value $\Gamma$, when the value $\bar{P}^- = \bar{P}^-(t)$ has already been found. Consider the set $\Gamma(t, \bar{P}^-)$ of matrices $\Gamma(t, \bar{P}^-)$, which are solutions to the following optimization problem: $\max\{\mathrm{tr}(\Xi(t, \bar{P}^-)\Gamma) | \Gamma \in \mathbb{R}^{m \times n} \text{ s.t. } \|\Gamma\| \le 1\}$. This set $\Gamma(t, \bar{P}^-)$ may be described in the following form:

$$ \mathcal{I}(t, \bar{P}^-) = \{\Gamma(t, \bar{P}^-) = \{\gamma_k^i(t, \bar{P}^-)\} | \gamma_k^i(t, \bar{P}^-) = \mathrm{sign}(\xi_i^k(t, \bar{P}^-)) l_k^i, \quad (11) \\ k = 1, \dots, m, \quad i = 1, \dots, n, \quad L = \{l_k^i\} \in \mathcal{L}\}. $$

Here $\Xi(t, \bar{P}^-) = \{\xi_i^k(t, \bar{P}^-)\} = (\bar{P}^-)^{-1}\bar{R}(t) \in \mathbb{R}^{n \times m}$, and $\mathcal{L}$ is a set of matrices $L = \{l_k^i\} \in \mathbb{R}^{m \times n}$ satisfying conditions $l_k^i \ge 0$, $k = 1, \dots, m$, $i = 1, \dots, n$; $l_k^i = 0$ if $i \notin I_k(t, \bar{P}^-)$, $k=1, \dots, m$, $i=1, \dots, n$; $\sum_{i=1}^n l_k^i = 1$, $k=1, \dots, m$; $I_k(t, \bar{P}^-) = \mathrm{Argmax}\{|\xi_i^k(t, \bar{P}^-)| | i=1, \dots, n\}$, $k=1, \dots, m$, where $\mathrm{sign} z$ is equal to $-1, 0, 1$ for $z < 0$, $z = 0$, $z > 0$ respectively. Consider the matrix differential inclusion

$$ \frac{d\bar{P}^-}{dt} \in \tilde{A}(t)\bar{P}^- + \mathrm{diag}\,\nu(t, \bar{P}^-; J(t))\cdot B(\bar{P}^-) + \bar{R}(t)\mathcal{I}(t, \bar{P}^-), \quad \bar{P}^-(0) = \bar{P}_0, \quad (12) $$

where $\nu(t, \bar{P}^-; J)$ and $B(\bar{P}^-)$ are the same as in (7).

**Theorem 3.** Let the above conditions be satisfied and $\mathcal{P}_0$ be a nondegenerate parallelepiped with $\det \bar{P}_0 > 0$. Then, for each function $J(\cdot) \in \mathbb{J}$, there exists a solution $(p^-(\cdot), \bar{P}^-(\cdot))$ of system (6), (11)-(12), which is determined on the whole interval $T$, and all solutions of this system determine parallelogones $\mathcal{P}^-(t)$ which turn out to be internal nondegenerate parallelepiped-valued estimates for $\mathcal{X}(t)$, $t \in T$.

Proof. We use arguments similar to [17, Theorem 5.2]. Existence and extendability are obtained using [10, p. 66, Theorem 6]. In particular, (8) is used to see that the function $P = \Phi^{-1}\bar{P}^-$ is such that $\det P(t)$ is a nondecreasing function and therefore $P(t)$ can not leave the domain where $\det P(t) \ge \det P(0) > 0$; consequently, solutions to (12) are defined on the whole interval $T$ and determine nondegenerate parallelepiped-valued estimates. The inclusions $\mathcal{P}^-(t) \subseteq \mathcal{X}(t)$ are proved similarly to Theorem 1. $\square$

**Remark 2.** We can choose $J(\cdot)$ in (7), (9) and (12) in different ways, in particular as a constant. A simple way is also to apply a “local” optimization which arises from (8). Fix a natural number $N$ and introduce a grid $T_N$ of times $\tau_k = kh_N$, $k=0, \dots, N$, $h_N = \theta N^{-1}$. Let us, for each $\tau_k \in T_N$, solve the optimization problem which is to maximize $\nu(\tau_k, \bar{P}^-; J)^\top \beta(\bar{P}^-)$ over all possible permutations $J = \{j_1, \dots, j_n\}$ assuming that $\bar{P}^- = \bar{P}^-(\tau_k)$ has already been found. Then we can sequentially construct the piecewise constant function $J(t) \equiv J(\tau_k) \in$
Argmax$_J$ $\nu(\tau_k, \bar{P}^-(\tau_k); J)^\top \beta(\bar{P}^-(\tau_k))$, $t \in [\tau_k, \tau_{k+1})$, $k = 0, \dots, N-1$, and find $\bar{P}^-(\cdot)$. Note that the described procedure is not obliged to give the estimates $\mathcal{P}^-(t)$ with maximal volume even if $N \to \infty$.

# 5 External Estimates

In [18], the ODE systems of two types were obtained for external estimates for $\mathcal{X}(t)$ in the form of parallelepipeds $\mathcal{P}^+(t) = \mathcal{P}(p^+(t), P(t), \pi^+(t))$, where $P(t)$ is a fixed matrix function. Let us restate here, for completeness of the exposition, the ODE system for the more accurate estimates of the type II:

$$ \frac{dp^+}{dt} = \dot{P}P^{-1}p^+ + P(\Phi^{(+)} - \Phi^{(-)})/2 + r, \quad p^+(0) = p_0; \quad (13) $$

$$ \frac{d\pi^+}{dt} = (\Phi^{(+)} + \Phi^{(-)})/2 + \text{Abs}(P^{-1}\bar{R})\text{e}, \quad \pi^+(0) = \text{Abs}(P(0)^{-1}P_0)\pi_0, $$
$$ \text{where } \Phi_i^{(\pm)} = \max_{\xi \in \Xi_i^{\pm}} (\pm P^{-1}(\tilde{A} - \dot{P}P^{-1})x + \text{Abs}(P^{-1})\hat{A}\text{Abs }x)_i, \quad (14) $$
$$ x = p^+ + P\text{diag } \pi^+\xi; \quad \Xi_i^{\pm} = \{\xi \mid \xi \in \mathcal{E}(\mathcal{P}(0, I, e)), \xi_i = \pm 1\}, \quad i=1, \dots, n, $$

the symbol $\mathcal{E}(\mathcal{P})$ denotes the set of all vertices of a parallelepiped $\mathcal{P}=\mathcal{P}(p, P, \pi)$, namely the set of points of the form $x = p + \sum_{j=1}^n p^j\pi_j\zeta_j$, $\zeta_j \in \{-1, 1\}$.

**Theorem 4.** Let Assumption 1 be satisfied and $P(t) \in \mathbb{R}^{n \times n}$ be an arbitrary continuously differentiable function such that $\det P(t) \neq 0$, $t \in T$. Then the system (13), (14) has a unique solution $(p^+(\cdot), \pi^+(\cdot))$ on $T$, and the parallelepipeds $\mathcal{P}^+(t) = \mathcal{P}(p^+(t), P(t), \pi^+(t))$ are the external estimates for the reachable sets $\mathcal{X}(t)$ of the system (1), (2), (4): $\mathcal{X}(t) \subseteq \mathcal{P}^+(t)$, $t \in T$.

*Proof.* The existence, uniqueness and extendability of the solution follow from [10, pp. 7,8,10], the inclusions — from [18, Theorem 1]. □

*Remark 3.* In fact, Theorem 4 describes the whole family of estimates where $P(\cdot)$ is a parameter. Some heuristic ways of choosing $P(\cdot)$ were indicated in [18] (in particular, (i) find $P(\cdot)$ from relations $\dot{P}=\tilde{A}(t)P$, $P(0)=P_0$, or (ii) put $P(t)\equiv I$).

# 6 Examples

Consider some examples. The estimates were calculated using the Euler approximations (5) with $N = 100$ (in fact, the estimates for $\mathcal{X}[k]$ are presented in figures below). But it would be emphasized that different schemes of approximation can be used for solving the obtained differential systems and finding the estimates.

*Example 1.* Let $\tilde{A} = \begin{bmatrix} 0 & 1 \\ -1.5 & 0 \end{bmatrix}$, $\hat{A} = \begin{bmatrix} 0 & 0 \\ 0.1 & 0 \end{bmatrix}$, $\mathcal{R} = \mathcal{P}(\begin{bmatrix} 0 \\ 0 \end{bmatrix}, I, \begin{bmatrix} 0 \\ 0.3 \end{bmatrix})$, $\mathcal{P}_0 = \mathcal{P}((2, 0.5)^\top, I, (0.2, 0.5)^\top)$, $\theta = 3.5$. Fig. 1 (a) presents tubes formed by external (see Remark 3, (i)) and internal estimates for $\mathcal{X}[k]$. The internal ones are obtained
<figure><img src="image_2.png" /><figcaption>Fig. 2. Projections of external and internal estimates for $\mathcal{X}[\cdot]$ and $\mathcal{X}[N]$ in Example 2.</figcaption></figure>
References

1. Artstein, Z., Raković, S.V.: Feedback and Invariance under Uncertainty via Set-Iterates. Automatica. 44 (2), 520–525 (2008)

2. Baier, R., Büskens, C., Chahma, I.A., Gerdts, M.: Approximation of Reachable Sets by Direct Solution Methods of Optimal Control Problems. Optim. Methods Softw. 22 (3), 433–452 (2007)

3. Baier, R., Gerdts, M.: A Computational Method for Non-convex Reachable Sets Using Optimal Control. In: Proceedings of the European Control Conference (ECC), Budapest, Hungary, August 23–26, 2009, pp. 97–102. Budapest (2009)

4. Baier, R., Lempio, F.: Computing Aumanns Integral. In: Kurzhanski, A.B., Veliov, V.M. (eds) Modeling Techniques for Uncertain Systems, Proc. of a Conferences held in Sopron, Hungary, July 6–10, 1992. Progress in Systems and Control Theory, vol. 18, pp. 71–92. Birkhäuser, Boston (1994)

5. Barmish, B.R., Sankaran, J.: The Propagation of Parametric Uncertainty via Polytopes. IEEE Trans. Automat. Control. AC-24 (2), 346–349 (1979)

6. Bushenkov V., Chernykh O., Kamenev G., Lotov A.: Multi-dimensional Images Given by Mappings: Construction and Visualization. Pattern Recognition and Image Analysis. 5 (1), 35–56 (1995)

7. Chernousko, F.L., Rokityanskii, D.Ya.: Ellipsoidal Bounds on Reachable Sets of Dynamical Systems with Matrices Subjected to Uncertain Perturbations. J. Optim. Theory Appl. 104 (1), 1–19 (2000)

8. Digailova, I.A., Kurzhanski, A.B.: On the Joint Estimation of the Model and State of an Under-Determined System from the Results of Observations. Dokl. Math. 65 (3), 459–464 (2002)

9. Dontchev, A.L., Farkhi, E.M.: Error Estimates for Discretized Differential Inclusions. Computing. 41 (4), 349–358 (1989)

10. Filippov, A.F.: Differential Equations with Discontinuous Right-Hand Sides. (Russian). Nauka, Moscow (1985)

11. Filippova, T.F.: Trajectory Tubes of Nonlinear Differential Inclusions and State Estimation Problems. J. Concr. Appl. Math. 8 (3), 454–469 (2010)

12. Filippova, T.F., Lisin, D.V.: On the Estimation of Trajectory Tubes of Differential Inclusions. Proc. Steklov Inst. Math. Suppl. 2, S28–S37 (2000)

13. Gusev, M.I.: Estimates of Reachable Sets of Multidimensional Control Systems with Nonlinear Interconnections. Proc. Steklov Inst. Math. Suppl. 2, S134–S146 (2010)

14. Jaulin, L., Kieffer, M., Didrit, O., Walter, E.: Applied Interval Analysis. Springer-Verlag, London (2001)

15. Kornoushenko, E.K.: Interval Coordinatewise Estimates for the Set of Accessible States of a Linear Stationary System. I–IV. Autom. Remote Control 41, 598–606 (1980), 41, 1633–1639 (1981), 43, 1266–1270 (1983), 44, 203–208 (1983)

16. Kostousova, E. K.: External and Internal Estimation of Attainability Domains by Means of Parallelotopes. (Russian). Vychisl. Tekhnol. 3 (2), 11–20 (1998) (available at http://www.ict.nsc.ru/jct/search/article?l=eng)

17. Kostousova, E.K.: Control Synthesis via Parallelotopes: Optimization and Parallel Computations. Optim. Methods Softw. 14 (4), 267–310 (2001)

18. Kostousova, E.K.: Outer Polyhedral Estimates for Attainability Sets of Systems with Bilinear Uncertainty. J. Appl. Math. Mech. 66 (4), 547–558 (2002)

19. Kostousova, E.K.: On Polyhedral Estimates for Reachable Sets of Discrete-Time Systems with Bilinear Uncertainty. Autom. Remote Control. 72, 1841–1851 (2011)
20. Kostousova, E.K.: On Polyhedral Estimates for Trajectory Tubes of Dynamical Discrete-Time Systems with Multiplicative Uncertainty. Discrete Contin. Dyn. Syst., Dynamical Systems, Differential Equations and Applications. 8th AIMS Conference, suppl., 864–873 (2011)

21. Kostousova, E.K.: On Polyhedral Estimates for Reachable Sets of Differential Systems with a Bilinear Uncertainty. (Russian; to appear). Trudy Instituta Matematiki i Mekhaniki UrO RAN. 18 (4) (2012)

22. Kostousova, E.K., Kurzhanski, A.B.: Guaranteed Estimates of Accuracy of Computations in Problems of Control and Estimation. (Russian). Vychisl. Tekhnol. 2 (1), 19–27 (1997)

23. Krastanov, M., Kirov, N.: Dynamic Interactive System for Analysis of Linear Differential Inclusions. In: Kurzhanski, A.B., Veliov, V.M. (eds) Modeling Techniques for Uncertain Systems, Proc. of a Conferences held in Sopron, Hungary, July 6–10, 1992. Progress in Systems and Control Theory, vol. 18, pp. 123–130. Birkhäuser, Boston (1994)

24. Kuntsevich, V.M., Kurzhanski, A.B.: Calculation and Control of Attainability Sets for Linear and Certain Classes of Nonlinear Discrete Systems. J. Automation and Inform. Sci. 42 (1), 1–18 (2010)

25. Kurzhanski, A.B., Vályi, I.: Ellipsoidal Calculus for Estimation and Control. Birkhäuser, Boston (1997)

26. Kurzhanski, A.B., Varaiya, P.: On Ellipsoidal Techniques for Reachability Analysis. Part I: External Approximations. Optim. Methods Softw. 17, 177–206 (2002)

27. Kurzhanski, A.B., Varaiya, P.: On Ellipsoidal Techniques for Reachability Analysis. Part II: Internal Approximations. Box-valued Constraints. Optim. Methods Softw. 17 (2), 207–237 (2002)

28. Nazin, S.A., Polyak, B.T.: Interval Parameter Estimation Under Model Uncertainty. Math. Comput. Model. Dyn. Syst. 11 (2), 225–237 (2005)

29. Polyak, B.T., Nazin, S.A., Durieu, C., Walter, E.: Ellipsoidal Parameter or State Estimation under Model Uncertainty. Automatica J. IFAC. 40 (7), 1171–1179 (2004)

30. Taras'yev, A.M., Uspenskiy, A.A., Ushakov, V.N.: Approximation Schemas and Finite-Difference Operators for Constructing Generalized Solutions of Hamilton-Jacobi Equations. J. Comput. Systems Sci. Internat. 33 (6), 127–139 (1995)

31. Veliov, V.M.: Second Order Discrete Approximations to Strongly Convex Differential Inclusions. Systems & Control Letters. 13 (3), 263–269 (1989)

32. Wolenski, P.R.: The Exponential Formula for the Reachable Set of a Lipschitz Differential Inclusion. SIAM J. Control Optim. 28 (5), 1148–1161 (1990)

33. Zaslavskii, B.G., Poluektov, R.A.: Control of Ecological Systems. (Russian). Nauka, Moscow (1988)