Chaouki T. Abdallah, Gregory L. Heileman, and Don R. Hush
Department of Electrical and Computer Engineering
University of New Mexico, Albuquerque, NM 87131, USA.
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 , 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 , ,, , and . In addition, The case of dependent coefficients is also much more complicated. The Edge Theorem  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  and  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 , 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.