\documentstyle[IEEEtran]{article}
\begin{document}
\tolerance 10000
\title{Planar Geometry Problems Motivated 
by Robustness of Linear Systems}
\author{B. Ross Barmish}

\pagestyle{myheadings}

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

\maketitle

\auffil{The author is with the 
Department of Electrical and Computer Engineering,
University of Wisconsin-Madison, Madison, Wisconsin 53706.}

Over the last decade, there has been a resurgence of research on
robustness analysis for linear systems whose mathematical models
include uncertain parameters. No statistical description for these
parameters is assumed --- only interval bounds are given. This lecture
will focus on a number of planar geometry problems which arise in this
context. In some cases, ``clean'' polynomial-time solutions can be
given; in other cases, exponential-time solutions are available but
become ``impractical'' to implement as the number of uncertain parameters
increases. This leads to a number of fundamental questions about
computational complexity; e.g.,~see~\cite{nem}.

Stability of a linear feedback system is determined by the roots
of its characteristic polynomial. If this polynomial involves system
parameters known only within given bounds, the classical robust stability
problem arises. One approach to the solution of this problem involves
generation of the so-called {\it value set}.  This set lies in the
complex plane and is a function of the frequency variable~$\omega \geq 0$.
The ability to generate the value set in graphics makes it possible to solve
robustness problems in a computer-aided context. 

To be more specific, the notation~$q$ is used to denote a vector of real
uncertain parameters and~$p(s,q)$ is assumed to be a polynomial having
coefficients depending continuously on~$q$. Hence, we can write 
$$
p(s,q) = s^n + a_{n-1}(q)s^{n-1} + \cdots + a_1(q)s + a_0(q)
$$
with each~$a_i(q)$ being a real continuous function. The given data also
consists of lower and upper bounds for each component~$q_i$ of~$q$.
Hence, we use the notation~$Q$ for the box describing the domain of~$q$.

Now, given a fixed frequency~$\omega \ge 0$, we set~$s= j\omega$ and
formally define the {\it value set} $p(j\omega,Q) = \{p(j\omega,q): q \in Q\}$.
Note that~$p(j\omega,Q)$ is the image of the multi-dimensional box~$Q$
under the mapping~$p(j\omega,\cdot)$. The importance of the value set is
derived from the following fact: If~$p(s,q^0)$ is stable (all roots
having negative real part) for at least one member~$q^0 \in Q$, then 
robust stability (stability for all~$q \in Q$) is guaranteed if and only
if the {\it Zero Exclusion Condition} $0 \not \in  p(j\omega,Q)$ is
satisfied for all $\omega \ge 0$. This type of stability condition goes 
back quite far in the literature; for example, see~\cite{fd} for
historical purposes and~\cite{bar} for a more recent exposition. 

The first part of this lecture will be a review of those cases
for which the value set generation problem has already been solved.
For example, if each component of~$q$ enters into only one
coefficient of~$p(s,q)$, then Kharitonov's interval polynomial
result~\cite{khar} emerges as a consequence of value set rectangularity.
For the case when the coefficients~$a_i(q)$ are affine
linear functions, the value set is readily shown to be a convex polygon.
This leads to the Edge Theorem~\cite{bart}. Finally, for the more
general case when~$q$ enters nonlinearly, only very limited results
are available. In this regard, perhaps the strongest result to date is
the Mapping Theorem: For the case of multilinear dependence on the 
uncertain parameters, this theorem provides a simple recipe for generation
of the convex hull of the value set; see~\cite{zade}. Namely, this convex hull
is the two-dimensional convex polygon whose vertices are obtained by evaluationof~$p(j\omega,q)$ with~$q$ restricted to the vertices of the bounding box~$Q$.
More precisely, denoting the set of vertices of~$Q$ by
$\{q^1,q^2,\ldots,q^L\}$,
the Mapping Theorem indicates that 
$$\mbox{conv}\;p(j\omega,Q) = $$ 
$$\mbox{conv}\{p(j\omega,q^1),p(\omega,q^2),\ldots,p(j\omega,q^L)\}.$$

The second part of this lecture will concentrate on new results
obtained in collaboration with Tempo; see~\cite{bt94}. A 
{\it Generalized Mapping Theorem} will be presented and it will
be argued that this theorem enhances the class of nonlinear dependencies
for which the convex hull can be generated. The point of view taken in
this work is that the value set generation problem is ill-posed unless
computability considerations are taken into account. This leads to
consideration of the current work in light of existing results on 
computational complexity. 


\begin{thebibliography}{99}

\bibitem{nem} A. Nemirovskii, ``Several NP-Hard Problems
Arising in Robust Stability Analysis,'' {\it Mathematics of Control
Signals and Systems}, 1993, Vol.~6, pp.~99--105.

\bibitem{fd} R. A. Frazer and W. J. Duncan, ``On the Criteria for 
Stability for Small Motions,'' {\it Proceedings of the Royal Society}, A,  
1929, Vol.~124, pp.~642--654.

\bibitem{bar} B. R. Barmish, {\bf New Tools for Robustness
of Linear Systems}, Macmillan, New York, 1994.

\bibitem{khar}
V. L. Kharitonov, 
``Asymptotic Stability of an Equilibrium Position of a Family of
  Systems of Linear Differential Equations,''  
{\it Differentsial'nye Uravneniya}, 1978, Vol.~14,  
pp.~2086--2088. 

\bibitem{bart} A. C. Bartlett, C. V. Hollot and L. Huang,  
``Root Locations of an Entire Polytope of Polynomials: 
It Suffices to
  Check the Edges,''
{\it Mathematics of Control, Signals and Systems}, 1988, Vol.~1, 
pp.~61--71.

\bibitem{zade} L. A. Zadeh and C. A. Desoer, {\bf Linear System Theory},
Mc-Graw-Hill, New York, 1963. 

\bibitem{bt94} B. R. Barmish and R. Tempo, {\bf On Mappable Nonlinearities
in Robustness Analysis}, Technical Report~ECE-94-18, Department of
Electrical and Computer Engineering, University of Wisconsin, 1994.

\end{thebibliography}

\end{document}