SU-CS238V FEB132025

Key Sequence Notation New Concepts Important Results / Claims overapproximate inclusion functions Questions Interesting Factoids reachability for non-linear systems Standard reachability analysis for Linear Dynamical System is not great, because polytopes don’t stay polytopes when we apply non-linear operations.
The general vibe, then, is to take a non-linear thing and bound them using a polytope.
interval arithmetic We can’t propagate polytopes though non linear systems; but we can propagate intervals.
Suppose we have an interval:

\begin{equation} [x] = \left\{x \mid x_1 \leq x \leq x_2\right\} \end{equation}

Let’s define some operations
interval counterpart of addition \begin{equation} [x] + [y] = \left{x+y \mid x \in [x], y \in [y]\right} \end{equation}
We could actually compute the interval explicitly:

\begin{equation} [x] + [y] = [x_1 + y_1, x_2 + y_2] \end{equation}

we can just add the intervals together
interval counter part of binary operators \begin{equation} [x] \cdot [y] = \left{x \cdot y \mid x \in [x], y \in [y]\right} \end{equation}
specifically… \begin{equation} [x] + [y] = [x_1 - y_2, x_2 - y_1] \end{equation}

\begin{equation} [x] \times [y] = [\min \left(x_1y_1, x_1y_2, x_2y_1, x_2y_2\right), \max \left(x_1y_1, x_1y_2, x_2y_1, x_2y_2\right)] \end{equation}

notably! this last thing is not defined if any of the intervals contains 0.
for monotone function f:

\begin{equation} f\left([x]\right) = [f\left(x_1\right), f\left(x_2\right)] \end{equation}