mme_computation.tex

由matlab开发的hybrid系统的描述语言

\chapter{Computing the Bounds}
\label{mme_comp_c}

\section{Theory}

An AD item needs an upper and lower bound for its affine expression as well as a precision epsilon. The DA item
needs upper and lower bounds for the affine expression in the `then'- and `else'-parts. If this data is not
specified by the user, the compiler tries to compute it automatically. If the data is specified, the compiler
tries to find better values. It it succeeds, a warning is displayed, but the computations are done with the user
specified values. All these functionalities are implemented in \function{compute\_minmaxeps}.

For an affine function $f$, minimum and maximum can be computed as:
\begin{align}
\label{mm_from_aff}
f &= a_1 x_1 + a_2 x_2 + \ldots + a_n x_n \\
\min(f) &=\min(a_1 x_1) + \min(a_2 x_2) + \ldots + \min(a_n x_n)  \notag \\
\max(f) &= \max(a_1 x_1) + \max(a_2 x_2) + \ldots + \max(a_n x_n)  \notag \\
\intertext{$\min(a_1 x_1)$ depends on the sign of $a_i$ and can be written as}
\min(a_i x_i) &= \min(a_i \min(x_i), a_i \max(x_i)) \notag \\
\max(a_i x_i) &= \max(a_i \min(x_i), a_i \max(x_i)) \notag
\end{align}


Bounds for all the variables can be specified in the declaration
section of \hysdel{}. If the bounds of some variable $x_u$ are
unknown, we compute them by resorting to the corresponding
definition item. If no such item exists (which is possible as a
variable can be set by directly giving inequalities in the must
section), an error is reported. If $x_u$ is defined in a
\cppclass{Continuous\_item} or \cppclass{Linear\_item}, the bounds
can be computed by \ref{mm_from_aff}. If $x_u$ is defined in a
\cppclass{DA\_item}, the bounds are
\begin{align}
\label{DA_bounds_comp}
x_u &= \text{IF } c \text{ THEN } f_1 \text{ ELSE } f_2 \text{;} \\
\min(x_u) &= \min \{ \min(f_1), \min(f_2) \} \notag \\
\max(x_u) &= \max \{ \max(f_1), \max(f_2) \} \notag
\end{align}
where $c$ is a boolean expression and $f_1$ and $f_2$ are affine functions, for which minimum and maximum can
again be computed by \ref{mm_from_aff}. Using this approach, the bounds are computed recursively.

The precision for the AD-converter is not computed, but simply set
to \code{MLD\_epsilon}. This is a parameter which can be defined
in the declaration section of \hysdel{}. If it is not defined, a
default value of $10^{-6}$ is used.

\section{Call Trace}

The bounds and precision required to translate the AD- and DA-item are computed in
\method{AD\_item}{compute\_minmaxeps} and \method{DA\_item}{compute\_minmaxeps}, respectively. These functions
delegate the work to \method{Item}{compute\_mme\_from\_aff}, which takes an affine function as an argument and
computes the maximum and minimum this function can assume. \method{Item}{compute\_mme\_from\_aff} iterates over
the addends of the affine function and asks each for its minimum and maximum by calling
\method{Affine\_addend}{find\_min} and \method{Affine\_addend}{find\_max}\footnote{\cppclass{Affine\_addend} stores a summand of an affine function. See subsection~\ref{affine_func_s}} . These two methods call
\method{Var\_symbol}{compute\_minmax}, which computes the minimum and maximum of the variable of the addend.

Before the bounds of the variable can be computed, the bounds of all variables in its definition must be known.
The set of these variables is returned by \method{Var\_symbol}{get\_required\_mme}.
\method{Var\_symbol}{compute\_minmax} calls itself recursively for all of these variables. Finally,
\method{Var\_symbol}{compute\_minmax} can call \method{Definition\_item}{compute\_minmax} to compute the bounds of
the variable. \method{Continuous\_item}{compute\_minmax} and \method{Linear\_item}{compute\_minmax} use
equation~\ref{mm_from_aff}, \method{DA\_item}{compute\_minmax} uses equation~\ref{DA_bounds_comp} to compute the
bounds. The other items do not need to implement \function{compute\_minmax}.