**
Chaouki T. Abdallah, Gregory L. Heileman, and Don R. Hush
Department of Electrical and Computer Engineering
University of New Mexico, Albuquerque, NM 87131, USA.**

**Introduction**

The stability of uncertain polynomials is an important problem in the analysis and design of control systems and has always been an active area of research. The problem was elegantly solved in the continuous-time case and for independent coefficients by the celebrated Kharitonov theorem [1], which reduces the stability test of a family of polynomials to that of 4 special members of that family.

The discrete-time or the general -stability
case has proven to be much more elusive,
although partial results are available in special cases [2],
[3],[4], [5], and [6]. In addition,
The case of dependent coefficients is also much more complicated. The
*Edge Theorem* [7] provides a test in these cases where the
stability of the family of polynomials is equivalent to that of the edges
in the parameter space. The number of polynomials to check is still
however infinite.

The problems attacked in all of these papers boil down to a most basic question: Is the set where the coefficients of an uncertain polynomial reside, a subset of the set whose elements correspond to stable polynomials? The answers to this question is contingent on finding the general stability set for a given-order polynomial.

This paper concentrates on the following simple question: Can we learn the set of parameters such that the coefficients for the polynomial,

such that all roots of *p*(*s*) = 0 lie in a region termed the
stable region? The region may be the open Unit circle, the open
left half plane, or any other desired region of the complex plane. A
related problem which may be easily solved is to check whether a given set
of parameters corresponds to a
-stable polynomial. This can be achieved by solving for the
roots of the particular polynomial or by testing for the satisfaction of
a set of inequalities (Routh-Hurwitz, Jury Tests). Our problem is much
more difficult, since we would like to determine, as accurately as
possible, the set of all polynomials of order *n* which are -stable.
We will assume that the -stability region is described by a set
of inequalities in the coefficients of .

A related problem which may be easily solved is to check whether a given set of coefficients corresponds to a -stable polynomial. This can be achieved by solving for the roots of the particular polynomial or by testing for the satisfaction of a set of inequalities (e.g., Routh-Hurwitz, Jury tests).

Because the problem of determining *p*(*s*) in the most general case
has proved to be an intractable task, we ask the question: Is it possible to
learn a ``good'' approximation to *p*(*s*)?. A related problem was
studied in [8] and [9] where the sets of parameters are obtained using
a ``set inversion'' approach, even when the polynomial coefficients depended on the
parameters in a highly nonlinear fashion.

The objective of this paper is to introduce some learning theory concepts
to the study of stability of uncertain polynomials. The approach relies on
the basic idea that although the set of coefficients and the set of parameters
corresponding to stable polynomials is geometrically complicated, we may be able to learn
it from examples, rather than determine it analytically.
More exactly, we would like to consider the possibility of learning from
examples an approximate solution to this problem. In doing so we would like
to be able to say something about how well the solution can be approximated,
and whether an efficient (i.e., polynomial-time) algorithm for learning exists.
The first of these issues is information-theoretic in nature. Specifically,
we must determine if the examples themselves convey enough information to
allow some learning algorithm to use them to construct a good
approximation. The later issue, which is complexity-theoretic in nature, can
only be addressed if the former issue can be answered in the affirmative.
In this paper we demonstrate that there is no information-theoretic barrier
to efficient learning of the stability set for an uncertain polynomial.
The paper will present an algorithm and several examples illustrating how the
stability region in the space of parameters may be learned for a large class of
polynomial families. The coefficients *a*(*q*) depend on *q* in a polynomial or more
general Pfaffian fashion [10], which allow us to obtain a bound on the number
of samples needed to learn an approximation of the stability region, and to have a
high degree of confidence in the accuracy of our region.

Wed Apr 1 15:25:21 MST 1998