Randomized algorithms for robust controller synthesis using statistical learning theory

By now it is known that several problems in the robustness analysis and syn thesis of control systems are NP-complete or NP-hard. These negative result s force us to modify our notion of "solving" a given problem. An approach t hat is recently gaining popularity is that of using randomized algorithms, which can be used to solve a problem approximately, most of the time. We be gin with the premise that many problems in robustness analysis and synthesi s can be formulated as the minimization of an objective function with respe ct to the controller parameters. It is argued that, in order to assess the performance of a controller as the plant varies over a prespecified family, it is better to use the average performance of the controller as the objec tive function to be minimized, rather than its worst-case performance, as t he worst-case objective function usually leads to rather conservative desig ns. Then it is shown that a property from statistical learning theory known as uniform convergence of empirical means (UCEM) plays an important role i n allowing us to construct efficient randomized algorithms for a wide varie ty of controller synthesis problems. In particular, whenever the UCEM prope rty holds, there exists an efficient (i.e., polynomial-time) randomized alg orithm. Using very recent results in statistical learning theory, it is sho wn that the UCEM property holds in any problem in which the satisfaction of a performance constraint can be expressed in terms of a finite number of p olynomial inequalities, In particular, several problems such as robust stab ilization and weighted H-2/H-infinity-norm minimization are amenable to the randomized approach. (C) 2001 Elsevier Science Ltd. All rights reserved.