\documentstyle[IEEEtran,amssym]{article}
\tolerance 10000
\def\USS{\Sigma_{\exists\exists}}
\def\TSS{\Sigma_{\forall\exists}}
\def\CSS{\Sigma_{\exists\forall}}
\def\GSS{\Sigma_{\frak{Qq}}}
\def\Ab{({\bf A,b})}
\def\dual{{\rm dual}\;}
\def\o{\overline}
\def\u{\underline}

\begin{document}

\title{Linear Static Systems Under Interval Uncertainty:
       Algorithms To Solve Control And Stabilization Problems}
\author{Sergey P. Shary}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ }

\maketitle

\begin{abstract}
This paper analyzes mathematical and computational aspects
linear static systems under interval uncertainty.

By an interval uncertainty, we mean that only intervals of possible
values are known for 
input data and for the system's parameters. In other words, for each
of this parameters $p$, we 
know an estimate $\tilde p$, and we
know the upper bound for possible error $\tilde p-p$ of this estimate.
\end{abstract}

\auffil{The author is with 
Computer Center, Krasnoyarsk, Russia, email
shary@cckr.krasnoyarsk.su.}

\section{Description of a Linear (Static) System}
\subsection{Schematic Description}
Let us denote the input and the output of the linear system by
by vectors $x\in\Bbb{R}^n$ and $b\in\Bbb{R}^m$ respectively. Usually, the
following structural scheme is used as a model for linear static systems:
\begin{equation}
\label{StruScheme}
\begin{minipage}[c]{80mm}
\unitlength 0.9mm
\begin{picture}(80,22)
\put(22,0){\line(1,0){36}}
\put(22,0){\line(0,1){20}}
\put(22,20){\line(1,0){36}}
\put(58,0){\line(0,1){20}}
\thicklines
\put(2,10){\vector(1,0){11}}   \put(13,10){\line(1,0){9}}
\put(58,10){\vector(1,0){11}}  \put(69,10){\line(1,0){9}}
\put(7,13){\makebox(0,0){$x$}} \put(72,13){\makebox(0,0){$y$}}
\put(40,10){\makebox(0,0){$b= Ax$}}
\end{picture}
\end{minipage}
\smallskip
\end{equation}
How is this system described in mathematical terms?

\subsection{Mathematical Description: Idealized Case} 
In the ideal case, when we can neglect the measurement inaccuracies, 
we can assume that we know (or can determine) precisely:
\begin{itemize}
\item all $n$ components $x_j$ of the input $x$;
\item all $m$ components $b_i$ of the output $b$;
\item all the components $a_{ij}$ of the 
$m\times n$ matrix $A$.
\end{itemize}
In this case, relation between
input and output is describe by a linear equation
\begin{equation}
\label{LinRela}
b = Ax
\end{equation}

\subsection{Mathematical Description: A More Realistic Case (Of
Interval Uncertainty)}
The assumption that we know the parameters precisely is an
idealization. In reality, we can only determine the {\it intervals}
that contain the desired values:
\begin{itemize}
\item for each of $n$ components of the input $x$, we know the {\it
interval} ${\bf x}_j$ that contains the (unknown) actual value $x_j$;
\item all for each of $m$ components of the output $b$, we know the
interval ${\bf b}_i$ that contains the (unknown) actual value $b_i$;
\item for each of $m\times n$ components of the matrix $A$, we know
the {\it interval} ${\bf a}_{ij}$ that contains the (unknown) actual
value of $a_{ij}$.
\end{itemize}
In this case, the relation between
input and output is describe by an interval analog of the system (2):
\begin{equation}
{\bf A} x = {\bf b},
\label{ILAS}
\end{equation}
where ${\bf A} = (\,{\bf a}_{ij})$ and ${\bf b} = ({\bf b}_i)$.

\section{Problems}
For every linear system, usually, two kinds of problems are solved:
\begin{itemize}
\item {\it direct problems}, when we know the input, and we want to
predict the output;
\item {\it inverse problems}, when we know the output, and we want to
estimate the input.
\end{itemize}
Both in the idealized case, and in the case of interval uncertainty, 
direct problems are easy to solve. Therefore, in this paper, we will
analyze inverse problems. 

In ideal (non-interval) case, 
an inverse problem consists of solving a system (\ref{LinRela}) with
known $A$ and $b$. In case of interval uncertainty, we also have to
somehow ``solve'' the interval linear algebraic system (ILAS)
(\ref{ILAS}).
In this case, however, it is not automatically clear what a
``solution'' means. Actually, as we will see, several solutions make
sense here. 

\section{Possible Interpretations Of Interval Uncertainty, and
Corresponding Formulations Of The Inverse Problem For Linear Systems}
One and the same interval can describe two different types of
uncertainty. Let us illustrate these two types of uncertainty on a
simplified example, in which
only one coefficient $a_{11}$ of the
matrix $A$ is not known precisely. Then, the relation (\ref{ILAS}) can
means two different things:
\begin{itemize}
\item First, it can mean that we have one one linear system with fixed
(but unknown) parameters. For this system, we do not know the exact
value of $a_{11}$, but we know that it belongs to the interval ${\bf
a}_{11}$. For this particular system, and for the input $x$, the
output belongs to the vector interval $\bf b$. In mathematical terms,
this means that for {\it some} $A\in {\bf A}$, we have $Ax\in {\bf
b}$. Another situation that corresponds to this interpretation is
when the changes in the value of the parameter are possible, but we
have no control over these changes. In this case, still, we can only
guarantee that there is a value of this parameter for which the
desired inclusion $Ax\in {\bf b}$ holds. 
\item Second, it can mean that we have several similar systems; the
values of $a_{11}$ for these systems are different, but they all lie
in the interval ${\bf a}_{11}$, and, potentially, all numbers from
this interval can be represented as the values of $a_{11}$ for some
system from this class. In this case, a natural interpretation of the
relation (\ref{ILAS}) is that for {\it all} possible values of
$A\in {\bf A}$, we have $Ax\in {\bf b}$. Another situation when a
similar interpretation is possible is when we have one system, but we
can {\it control} the values of this parameter.   
\end{itemize}
In the second case, when the condition describes what happens
$\forall A\in {\bf A}$, the equation (\ref{ILAS}) contains more
information about the system. Therefore, this prevailing type of
information is called {\it uncertainty of the I-st type}.
Correspondingly, the case when the condition is $\exists A\in {\bf A}$
is called {\it uncertainty of the II-nd type}. 

Different components of the coefficients matrix $A$ and of the output
vector $b$ can correspond to different types of uncertainty. So, in
order to describe the most general case, we must do the following:
\begin{itemize}
\item Let the entire set of the index pairs $(i,j)$ (that describe
components $a_{ij}$ of the matrix $A$) be 
divided into two non-intersecting parts:
\begin{itemize}
\item[$\bullet$] $\Omega' = \{ \omega'_1, \ldots,
\omega'_p \}$ and 
\item[$\bullet$]$\Omega'' = \{ \omega''_1, \ldots, \omega''_r \}$.
\end{itemize}
\item[] Here, $p+r=m\cdot n$. These sets have the following interpretation:
\begin{itemize}
\item[$\bullet$]If $(i,j)\in\Omega'$, then the parameter 
$a_{ij}$ is of the first type of
uncertainty (uncontrolled {\it perturbation}). 
\item[$\bullet$]If $(i,j)\in\Omega''$, the the parameter
$a_{ij}$ is of the second type of
uncertainty ({\it control}). 
\end{itemize}
\item
Similarly, we introduce two non-intersecting sets
of integer indices:
\begin{itemize}
\item[$\bullet$]
 $\Theta' = \{ \vartheta'_1, \ldots, \vartheta'_s \}$ and
\item[$\bullet$]
$\Theta'' = \{ \vartheta''_1, \ldots, \vartheta''_t \}$, 
\end{itemize}
\item[] such that $\Theta'\cup\Theta''
= \{ 1,2,\ldots,m \}$. These sets have the following interpretation:
\begin{itemize}
\item[$\bullet$] If $i\in\Theta'$, then the parameter 
$b_{i}$ is of the first type of
uncertainty.
\item[$\bullet$]If $i\in\Theta''$, the the parameter
$b_{ij}$ is of the second type of
uncertainty.
\end{itemize}
\end{itemize}
Some of the sets
$\Omega'$, $\Omega''$, $\Theta'$, $\Theta''$ may be empty. 
The above-mentioned interpretation enables us to formulate what we
mean by a solution of the ILAS.
\smallskip

\noindent{\bf Definition.} {\sl We define
the {\it set of $\,\frak{Qq}$-solutions} to
 the interval linear system
(\ref{ILAS}) as follows:
$$\GSS\Ab=\{x\in\Bbb{R}^n\,|$$
$$(\forall a_{\omega'_1}\in{\bf a}_{\omega'_1})\ldots
(\forall a_{\omega'_p}\in{\bf a}_{\omega'_p})$$
$$(\forall b_{\vartheta'_1}\in{\bf b}_{\vartheta'_1})\ldots
(\forall b_{\vartheta'_s}\in{\bf b}_{\vartheta'_s})$$
$$(\exists a_{\omega''_1}\in{\bf a}_{\omega''_1})\ldots
(\exists a_{\omega''_r}\in{\bf a}_{\omega''_r})$$
\begin{equation}
\label{SolutionSet}
(\exists b_{\vartheta''_1}\in{\bf b}_{\vartheta''_1})\ldots
(\exists b_{\vartheta''_t}\in{\bf b}_{\vartheta''_t}) \\
(Ax = b)\}
\end{equation}
where the quantifier $m\times n$-matrix $\frak{Q} = (\,\frak{Q}_{ij})$ and
$m$-vector $\frak{q} = (\frak{q}_i)$ are such that
$$
\frak{Q}_{ij} =
\left\{ \begin{array}{ll}
\forall, & \mbox{if } \ (i,j)\in\Omega',\\[1mm]
\exists, & \mbox{if } \ (i,j)\in\Omega'',
\end{array} \right.
\quad
\frak{q}_i =
\left\{ \begin{array}{ll}
\forall, & \mbox{if } \ i\in\Theta',\\[1mm]
\exists, & \mbox{if } \ i\in\Theta''.
\end{array} \right.
$$
We will also call the set (\ref{SolutionSet}) the {\it solution
set of the type $\frak{Qq}$}.}
\smallskip

This general definition contains all known solutions of interval
analysis as particular cases:
\begin{itemize}
\item{\em the united solution set}
$$
\USS\Ab =$$ $$ \{x\in\Bbb{R}^n
\mid (\exists A\in{\bf A})(\exists\,b\in{\bf b})(Ax = b)\},
$$
formed by the solutions of all systems $\,Ax = b\,$ with $A\in{\bf A}\,$
and $\,b\in{\bf b}$ (historically first and, undoubtedly, the most
popular of the solution sets to ILAS),
\item{\em the tolerable solution set}
$$
\TSS\Ab =$$ $$ \{x\in\Bbb{R}^n
\mid(\forall A\in{\bf A})(\exists\,b\in{\bf b})(Ax=b)\},
$$
formed by all vectors $x\in\Bbb{R}^n$, such that the product $Ax$ falls
into $\bf b$ for any $A\in{\bf A}$,
\item{\em the controlled solution set}
$$
\CSS\Ab =$$ $$ \{x\in\Bbb{R}^n
\mid(\forall\,b\in{\bf b})(\exists\,A\in{\bf A})(Ax = b)\},
$$
formed by vectors $x\in\Bbb{R}^n$ such that for any desired $b\in{\bf b}$
we can find an appropriate $A\in{\bf A}$ satisfying $Ax = b$,
\end{itemize}
These particular cases are extreme points of the class of all possible
solution sets to (\ref{ILAS}).

\section{An Even More General Definition Is Possible, e.g., In Game
Theory And Decision Making}
The above definition (4) is not the most general interpretation of
(\ref{ILAS}). Indeed, in {\it game theory}, and in {\it multi-stage
decision making}, we must not only describe which parameters are
controllable, but also what parameters are controllable by whom, and
in what order. It is possible, e.g., that players move in turn, and 
a parameter $a_{1i}$ is
chosen by the first player on his $i-$th move, and the 
parameter $a_{2i}$ is chosen by the second player on his $i-$th move.
Then, if the condition $Ax\in{\bf b}$ 
means that the first player has won,
then the equation (\ref{ILAS}) can be interpreted as follows: There
exists such a first move of the first player that, no matter how the
second one moves, the first can move again, etc, and get $Ax$ to be in
$\bf b$, i.e., as:
$$\exists a_{11}\forall a_{21}\exists a_{12}\forall a_{22} ... (Ax\in
{\bf b}).$$
In general, we can have an arbitrary number of quantifier
combinations. 

In the present paper, we will only consider the set (4), in which 
{\em all occurrences of the
universal quantifier $\forall$ precede to occurrences of the existential
quantifier $\exists\,$}. In logical terms, we can rephrase this
condition by saying that the corresponding formula must have an 
{\em AE-form}.

\section{Main Result}
To formulate our results, we must introduce the following denotations.

For the interval linear system ${\bf A}x = {\bf b}$, we define interval
matrices ${\bf A}^\forall = ({\bf a}^\forall_{ij})$ and ${\bf A}^\exists
= ({\bf a}^\exists_{ij})$ and interval vectors ${\bf b}^\forall =
({\bf b}^\forall_i)$ and ${\bf b}^\exists = ({\bf b}^\exists_i)$ of the
same size as $\bf A$ and $\bf b$ as follows:
$${\bf a}^\forall_{ij} =
\left\{ \begin{array}{rl}
{\bf a}_{ij}, & \mbox{if } \ \frak{Q}_{ij} = \forall,\\[1mm]
0, & \mbox{otherwise},
\end{array} \right.$$
$${\bf a}^\exists_{ij} =
\left\{ \begin{array}{rl}
{\bf a}_{ij}, & \mbox{if } \ \frak{Q}_{ij} = \exists,\\[1mm]
0, & \mbox{otherwise},
\end{array} \right.$$
$${\bf b}^\forall_i =
\left\{ \begin{array}{rl}
{\bf b}_i, & \mbox{if } \ \frak{q}_i = \forall,\\[1mm]
0, & \mbox{otherwise},
\end{array} \right.$$
$${\bf b}^\exists_i =
\left\{ \begin{array}{rl}
{\bf b}_i, & \mbox{if } \ \frak{q}_i = \exists,\\[1mm]
0, & \mbox{otherwise}.
\end{array} \right.$$
Thus ${\bf A} = {\bf A}^\forall + {\bf A}^\exists$ and ${\bf b}
= {\bf b}^\forall + {\bf b}^\exists$. The fundamental result of our
research is
\smallskip

\noindent{\bf PROPOSITION 1.} {\it 
The point $x$ belongs to the solution set $\GSS\Ab$ if and only if
\begin{equation}
\label{Characterization}
{\bf A}^\forall x - {\bf b}^\forall
\;\subseteq\;
{\bf b}^\exists - {\bf A}^\exists x.
\end{equation}}

\section{It Is Very Difficult To Describe The Set Of All Solutions,
So, Instead, Let Us Find Some Solutions}
It is not hard to prove that for all $\frak Q$ and $\frak q$,
the intersection of the solution set $\GSS\Ab$
with each orthant of the space $\Bbb{R}^n$ is a convex polyhedron.
So, in principle, the set of all $x$ that satisfy the condition (5) is
a union of $2^n$ convex polyhedra. 

Each polyhedron can be easily described, but since there are $2^n$ of
them (as many as orthants), the resulting length of the 
direct description of $\GSS\Ab$ grows exponentially with $n$. As a
result, even from moderate values of $n$, this 
description becomes practically useless.

This is not because the method is bad: 
even the problems of deciding 
whether the united solution set and the controlled solution set are empty
or not are known to be NP-hard. 

Because of this, instead of trying to describe the solution set
itself, to try to find an element from this set. In other words, we
arrive at the following problem:
$$\mbox{\sl Find an interval vector}$$
$$\mbox{\sl that is contained
in the solution set}$$
$$\mbox{\sl $\GSS\Ab$ (if it is nonempty)}$$
\begin{equation}\label{Problem}
\mbox{\sl of the interval
linear system.}
\end{equation}
Several particular cases of this problem have direct practical
interpretation:
\begin{itemize}
\item For the tolerable solution set $\TSS\Ab$,
the problem (\ref{Problem}) is the classical
{\em linear tolerance problem} with numerous and fruitful practical
applications. 
\item For $\GSS\Ab = \CSS\Ab$ or $\GSS\Ab = \USS\Ab$
the problem (\ref{Problem}) is the {\em control problem} or the
{\em identification problem} respectively for the interval linear system
\cite{Sha95}.
\item The linear tolerance problem can be also interpreted as 
a problem of stabilization
within the required output state corridor $\bf b$ for the system of
which {\em all} parameters $a_{ij}$ are subjected to bounded perturbations.
\item If some $a_{ij}$ are disturbing parameters while some are
controlled ones,
and all $\frak{q}_i = \exists$, $i = 1,2,\ldots,m$, then we come to the
stabilization problem with a control possibility, or, in other words, to
the problem of insuring survival of the system. 
\item Alternately, if a part of
$a_{ij}$'s are disturbing parameters and a part of them are controlled
while all $\frak{q}_i = \forall$, $i = 1,2,\ldots,m$, then we have the
control problem under bounded perturbations.
\end{itemize}

\section{A New Method Of Solving The Problem (\ref{Problem})}
In this paper, we present a new, algorithmically efficient
approach to the analysis of the linear static systems under interval
uncertainty, namely, to the solution of the problem (\ref{Problem}).

The underlying idea of our result is unusual for interval
computations: it uses the concept of 
{\em interval algebraic solution} to the interval equation,
that is, an interval vector ${\bf x}=({\bf x}_1,...,{\bf x}_n)$, 
for which ${\bf Ax}$
(interpreted as a normal interval product) coincides with $\bf b$.

To be more precise, we reduce the 
problem (6) to the 
problem of finding algebraic interval solution to a special systems of
equations in the {\em extended Kaucher interval arithmetic $\Bbb{IR}$}
\cite{Kaucher}, thus reducing the original problem to a purely algebraic
problem of the numerical analysis. 

This reduction does not always work: there exist cases in which the
set of solutions (4) is not empty,  but
the corresponding algebraic problem has no solutions. However, if the
algebraic problem does have a solution, then we can solve the 
problem (\ref{Problem}) as well. And, in many reasonable cases, the
algebraic problem does have a solution.

To formulate our result, let us briefly recall what Kaucher arithmetic
is. In this formalism, the basic elements are  
the pairs $[\,\u{x},\,\o{x}\,]$ of real numbers,
for which (unlike standard interval arithmetic) the condition 
$\u{x}\leq\o{x}$ is not required.
Thus, $\Bbb{IR}$ is obtained from the set of standard intervals 
by adding {\em improper} intervals $[\u{x},
\o{x}],\;\u{x} > \o{x}$, to the set I$\Bbb{R} = \{[\u{x},\o{x}]\mid
\u{x},\o{x}\in\Bbb{R},\u{x}\leq\o{x}\,\}$ of the {\em proper} intervals
and the real numbers. Proper and improper intervals (the two major parts
of $\Bbb{IR}$, can change places as the result of the duality mapping
$$
\dual :\Bbb{IR}\rightarrow\Bbb{IR},
$$
defined as $\dual[\u{x},\o{x}] = [\o{x},\u{x}]$.
\smallskip

\noindent{\bf PROPOSITION 2.} 
{\it If the proper interval vector ${\bf x}=({\bf x}_1,...,{\bf x}_n)$
is an algebraic interval
solution of the equation
\begin{equation}
\label{MainSystem}
( {\bf A}^\forall + \dual{\bf A}^\exists ){\bf x}
= \dual{\bf b}^\forall + {\bf b}^\exists ,
\end{equation}
then ${\bf x}\subseteq\GSS\Ab$, i.e., the interval vector ${\bf x}$
is a solution to the problem (\ref{Problem}).}
\smallskip

This algebraic approach is remarkable for its property to almost
always give solutions to the problem (\ref{Problem}) which are {\em maximal
by inclusion}:
\smallskip

\noindent{\bf PROPOSITION 3.} {\it
If the proper interval vector ${\bf x}$ is an inclusion-maximal
algebraic interval solution to the system (\ref{MainSystem}), then it is
also an inclusion-maximal interval vector contained in $\GSS\Ab$,
i.e., it
presents an inclusion-maximal solution to the problem
(\ref{Problem}).}
\smallskip

\section{Other Related Results}
We have also:
\begin{itemize} 
\item investigated existence and uniqueness of the algebraic
interval solutions, 
\item proposed a number of practical numerical algorithms
to compute algebraic solutions 
(in particular, the subdifferential Newton method) and
\item proved convergence of these algorithms.
\end{itemize}

\begin{thebibliography}{99}

\bibitem{Kaucher} E.~Kaucher, ``Interval analysis in the extended
   interval space $\Bbb{IR}$'', {\it Computing}, Suppl.~2, 1980, pp.~33--49.

\bibitem{Sha95} S.~P. Shary, ``Algebraic approach to the interval
   linear static identification, tolerance and control problems, or One more
   application of Kaucher arithmetic'', {\it Interval Computations}, 1995, to
   appear.

\end{thebibliography}

\end{document}