Applications of Mixed QE/Probabilistic Methods for Nonlinear Feedback Design

C.T. Abdallah ^{1  
*}Department of Electrical and Computer Engineering
University of New Mexico
Albuquerque, NM 87131, USA
{chaouki}@eece.unm.edu

ABSTRACT

The use of quantifier elimination methods in control design has been recently advocated and has proven to be a viable alternative in both linear and nonlinear (but polynomial cases). Unfortunately, the computational costs of QE algorithms has so far limited the spread of such approaches. As an example, while the static output feedback problem (SOF) is known to be decidable using QE but its computational complexity is thought to be NP. In fact many control problems can be reduced to decidability problems or to optimization questions which can then be reduced to the question of finding a real vector satisfying a set of inequalities. Our research deals mainly with control design problems where these inequalities are multinomial functions of the unknown variables.

On the other hand, recent work on statistical learning theory has suggested that by softening the goal of control design, we may be able to answer such decidability problems for larger classes of systems. Such systems may include: Polynomial nonlinear systems, Systems with sigmoidal functions, and Pfaffian systems.

We will see that decidability questions may not be answered exactly given a reasonable amount of resources, and recent research has focused on ``approximately" answering these questions ``most of the time", and having ``high confidence'' in the correctness of the answers. Our Plan of attack is then to study the following:

• Which control questions can be answered? or which problems are solvable? This is the realm of QE Decision Theory, and will give a yes/no answer.
• Which control problems are solvable but difficult? which problems are solvable but at a prohibitive cost? This is the realm of Complexity Theory, and will tell us which decidable problems are not ``practically'' solvable.
• What do we do about ``approximately'' solving those problems which are costly to solve exactly? This is the realm of Stochastic Algorithms (Monte Carlo), and its relationship to QE constitutes the bulk of this research.

We report here on how to use the complementary approaches of QE and statistical learning theory to solve fixed-structure control problems and we report on on-going work for the control of nonlinear Pfaffian systems (which include polynomials) along with some improved sample bounds in the statistical learning theory.