# DIFFICULTIES OF THE ц APPROACH

4.6.1 COMPUTATION OF /x BOUNDS

• Computing the exact value of the s. s.v. is an NP hard problem (Braatz et al., 1994), so that the computational burden of the algorithms, which compute the exact value of /x, is necessarily an exponential function of the size of the problem. It is consequently impossible to compute the exact value of /x for large dimension problems. A usual solution is to compute n upper and lower bounds instead of the exact value. The as­sociated algorithms can be exponential time (like the algorithms which compute the exact value of /x), or more interestingly polynomial time. Even if the gap between the ц bounds can not be guaranteed a priori when using polynomial time algorithms, good results can be obtained in realistic examples: this will be illustrated in the following.

• From a computational point of view, a (skewed) /x upper bound is typically obtained as the solution of a convex or quasi-convex optimiza­tion problem, namely a Linear Matrix Inequality problem (Boyd et al., 1994; Gahinet et al., 1995).

Conversely, methods which compute a /x lower bound are generally heuristic, and the computational burden is required to be low. The most classical solution consists in solving in an heuristic way a non convex optimization problem: a ц lower bound corresponds indeed to a local optimum of this non convex optimization problem, whereas the exact value of /X corresponds to the global optimum of this optimization prob­lem.

The idea is more precisely to obtain the lower bound as the limit of a fixed point iteration Xk+i = f(xk), which is obtained by rewriting the ne­cessary conditions of optimality as f{x) = x (Packard et al., 1988; Young and Doyle, 1990). Note however that the associated power algorithms are not guaranteed to converge, and that the final result depends on the initialization of the fixed point iteration. This will be further detailed in the following. 

Д = diag(5ilqi). Remember the unit hypercube D is defined in equa­tion (1.20). An upper bound Д of p{M) gives a sufficient condition of nonsingularity of the matrix I — MA, which is thus guaranteed to be nonsingular for all parametric uncertainties Д inside (1 /JI)D.

Note also that an upper bound Ji of the s. s.v. becomes a lower bound (1/Д) of the m. s.m., so that a lower bound к* of the robustness margin kmax is finally obtained as: In the context of a robust stability problem in the presence of paramet­ric uncertainties, closed loop stability can thus be guaranteed inside the hypercube kbD in the space of uncertain parameters.

Conversely, a lower bound p of p(M) gives a sufficient condition of singularity of the matrix I – MA, i. e. there exists a real model perturb­ation Д* Є (1 /p)D, with I — MA* singular (in the context of a robust stability problem, Д* is a destabilizing model perturbation).

The usefulness of a p lower bound is twofold. As a first point, p gives a measure of the conservatism of the upper bound p, by examining the tightness of the interval [p, Д] which contains the exact value of p. As a second point, an associated worst-case model perturbation Д * is usually provided with p by the computational algorithm.