% From owner-reliable_computing@interval.usl.edu Sat Mar 20 20:46:57 1999
% X-NUPop-Charset: IBM 8-Bit
% Date: Sat, 20 Mar 99 20:30:10 CET  
% From: "Jiri Rohn" <rohn@uivt.cas.cz>
% Reply-To: rohn@uivt.cas.cz
% To: reliable_computing@interval.usl.edu
% Subject: tolerance and control solutions
% Sender: owner-reliable_computing@interval.usl.edu
% Content-Length: 5488
% X-Lines: 112
% Status: RO

\documentstyle[12pt]{article}
\pagestyle{plain}\parskip=0.8\baselineskip\parindent=0cm
\newcommand{\ai}{{\bf A}}\newcommand{\bi}{{\bf b}}
\newcommand{\axd}{[Ax-\Delta|x|,Ax+\Delta|x|]}

\begin{document}
\begin{flushright} March 20, 1999 \end{flushright} \bigskip
Dear colleagues,

The recent request on the net by K. Ros{\l}aniec has reminded me of a
remarkable similarity in descriptions of general solutions, tolerance
solutions, and control solutions of linear interval systems which, as far
as I know, has never been stated explicitly yet.

Let $\ai=[A-\Delta,A+\Delta]$ be an $m\times n$ interval matrix and
$\bi=[b-\delta,b+\delta]$ an interval $m$-vector. For an $x\in R^n$
denote
$$\ai x=\{A'x;\,A'\in\ai\}.$$
Then, as is well known,
$$\ai x=\axd.$$
There are three basic types of solutions:
\begin{itemize}
\item[1)] $x$ is called a solution if $\ai x\cap\bi\neq\emptyset$, i.e.
if $A'x=b'$ for some $A'\in\ai$, $b'\in\bi$. It is well known that $x$ is a
solution if and only if
\begin{equation} |Ax-b|\leq\Delta|x|+\delta \label{1} \end{equation}
holds (Oettli and Prager 1964).
\item[2)] $x$ is called a tolerance solution if $\ai x\subseteq\bi$,
i.e. if for each $A'\in\ai$ there exists a $b'\in\bi$ such that
$A'x=b'$. Tolerance solutions were implicitly introduced by Nuding and
Wilhelm and studied since (as far as I know) by Neumaier, R., Deif, Shary,
Shaydurov and Shary, Kelling and Oelschl\"agel, Kelling, Lakeyev and Noskov,
and Beaumont. The set of tolerance solutions is described by
\begin{equation} |Ax-b|\leq-\Delta|x|+\delta \label{2} \end{equation}
(my paper of 1986). The proof of it is easy since $\ai x\subseteq\bi$ is
equivalent to $\axd\subseteq[b-\delta,b+\delta]$ which leads to
(\ref{2}).
\item[3)] $x$ is called a control solution if $\bi\subseteq\ai x$, i.e.
if for each $b'\in\bi$ there exists an $A'\in\ai$ such that $A'x=b'$.
Control solutions were introduced and studied by Shary. The set of
control solutions can be described by
\begin{equation} |Ax-b|\leq\Delta|x|-\delta. \label{3} \end{equation}
I think in this form it has never been published. The proof again
follows immediately from $[b-\delta,b+\delta]\subseteq\axd$. An
alternative description was given by Lakeyev and Noskov.
\end{itemize}
By comparing the results (\ref{1}), (\ref{2}) and (\ref{3}), we may
observe a remarkable similarity: the descriptions differ from each other
in the right-hand side signs only. Nevertheless, there are essential
differences hidden behind these apparently similar descriptions:
\begin{itemize}
\item[a)] The set of tolerance solutions, given by (\ref{2}), is a
convex polyhedron which may be described by a set of linear
inequalities. This can be easily seen if we realize that an $x$ solves
(\ref{2}) if and only if there is a $y$ such that
\begin{equation} |Ax-b|+\Delta y\leq\delta,\label{4} \end{equation}
$$|x|\leq y$$
holds, the latter being equivalent to
$$\Delta y-\delta\leq Ax-b\leq\delta-\Delta y,$$
$$-y\leq x\leq y,$$
where the absolute values have vanished. Another description of this
sort is contained in my 1986 paper. Hence, existence of a tolerance
solution can be checked by a linear programming technique (i.e., by a
polynomial-time algorithm), and in a positive case also found by this
technique.
\item[b)] On the other hand, the solution set and the control solution
set, described by (\ref{1}) and (\ref{3}), are both generally nonconvex,
as it can be seen on specific examples. Moreover, the problem of
checking whether the solution set, or the control solution set, are
nonempty is NP-hard to decide, even for square interval matrices.
This result is due to Lakeyev and Noskov. I give here another,
simplified version of their proof. Given an $n\times n$ interval matrix
$[A-\Delta,A+\Delta]$, consider an $(n+1)\times (n+1)$ interval matrix
$\ai=[A'-{\Delta}',A'+{\Delta}']$ and an $(n+1)$-dimensional interval
vector $\bi=[b-\delta,b+\delta]$ with
$$     A'=\left(\begin{array}{cc}A&0\\0^T&0\end{array}\right),\,
{\Delta}'=\left(\begin{array}{cc}\Delta&0\\e^T&0\end{array}\right),\,
b=(0,\ldots,0,1)^T,\,\delta=0.$$
Since $\delta=0$, the solution set and the control solution set coincide
in view of (\ref{1}), (\ref{3}). Hence, a (control) solution exists if
and only if
$$|Ax|\leq\Delta|x|,$$
$$1\leq e^T|x|$$
has a solution, which is equivalent to existence of an $x'\neq 0$
satisfying
$$|Ax'|\leq\Delta|x'|.$$
Thus a solution (or control solution) exists is and only if
$[A-\Delta,A+\Delta]$ is singular, the latter case being known to be
NP-hard to check (Poljak and R. 1988). Hence, checking existence of a
solution (or of a control solution) is NP-hard as well.
\end{itemize}
Summing up, the hardness of checking is determined by the sign of the
term $\Delta|x|$ on the right-hand sides of (\ref{1}), (\ref{2}),
(\ref{3}). The ``$+$'' sign implies NP-hardness, whereas the ``$-$''sign
leads to polynomial solvability, which is explained by (\ref{4}). Also,
there are other consequences of (\ref{2}), (\ref{3}): each tolerance
solution satisfies $\Delta|x|\leq\delta$, each control solution satisfies
$\Delta|x|\geq\delta$; if $x$ is both tolerance and control solution
simultaneously, then it must satisfy
$$Ax=b,\,\Delta|x|=\delta$$
(hence, in the square case it must be $x=A^{-1}b$ and
$\Delta|A^{-1}b|=\delta$).

I apologize to those of you to whom this text brings little new; I hoped
for some people this unified approach might be of interest.

With best wishes,
\bigskip\bigskip\\
Jiri Rohn

\end{document}