Introduction

Several interesting control system design and analysis problems can be reduced to quantifier elimination (QE) problems as shown in [3],[7],[1],[11],[12]. The first attempt by Anderson et al.[3] was made in 1970's, but at that time the algorithm of QE was very intricate and no appropriate software was available. However, recently some improved algorithms have been developed by several authors (see [5],[6],[19]) and implemented on computers (see [10],[15],[16]). By virtue of the considerable developments of both algorithms and software in QE methods, we explore the application of the QE theory to control problems of great practical interest.

Many control problems and design specifications are described by using matrix inequalities. Here we focus on LMI and BMI problems; When $A \in$ R $^{n\times n}$ is (semi) positive definite, we denote it by $A >_d 0 \ ( \geq_d 0).$ A linear matrix inequality (LMI) is a matrix inequality of the form

$$F(x)=F_0+ \sum_{i=1}^mx_i F_i$$ (1)

where $x \in$ R^m is the variable vector and $F_i=F_i^T \in$ R $^{n\times n}$ for $i=0,\cdots,m$. And a bilinear matrix inequality (BMI) is of the form

$$G(x,y) = G_{0,0}+ \sum_{i=1}^{n_x} x_i G_{i,0} + \sum_{j=1}^... ..._j G_{0,j} + \sum_{i=1}^{n_x} \sum_{j=1}^{n_y} x_i y_j G_{i,j}$$ (2)

where $x \in$ R^n_x, $y \in$ R^n_y, $G_{i,j} = G_{i,j}^T \in$ R $^{n\times n}$ for $i \in \{ 0, \cdots, n_x\},$ $j \in \{ 0, \cdots, n_y\}$.

A number of important problems can be are reduced to the optimization problems with LMI or BMI constraints. The problem of minimizing a linear objective function in $x \in$ R^m subject to LMI constraint,

$$\begin{array}{cl} minimize & c^T x \\ subject \ to \ & F(x) \geq_d 0 \end{array}$$ (3)

where $c \in$ R^m, is called semidefinite programming (SDP). SDP problem is solved numerically as convex optimization problems (see [4],[20]). But when we consider the real parametric uncertainties the problems are not always convex (often become non-convex) and most of such methods does not work.

Moreover, we also consider extended SDP (ESDP) i.e. the extension of the SDP obtained by replacing LMI constraint by BMI

$$\begin{array}{cl} minimize & c^T x + b^T y \\ subject \ to \ & G(x,y) \geq_d 0 \end{array}$$ (4)

where $c \in$ R^n_x, $b \in$ R^n_y. Though BMIs includes much wider variety of control problems than LMIs, BMI problems are non-convex and, in general, hard to find the solution numerically.