Randomized algorithms for robust controller synthesis using statistical learning theory: A tutorial overview

By now it is well known that several problems in the robustness analysis an d synthesis of control systems are NP-complete or NP-hard. These negative r esults force us to modify our notion of "solving" a given problem. If we ca nnot solve a problem exactly because it is NP-hard, then ive must settle fo r solving it approximately. If we cannot solve all instances of a problem, ive must settle for solving "almost all" instances of a problem. An approac h that is recently gaining popularity is that of using randomized algorithm s. The notion of a randomized algorithm as defined here is somewhat differe nt from that in the computer science literature, and enlarges the class of problems that can be efficiently solved. We begin with the premise that man y problems in robustness analysis and synthesis can be formulated as the mi nimization of an objective function with respect to the controller paramete rs. It is argued that, in order to assess the performance of a controller a s the plant varies over a prespecified family, it is better to use the aver age performance of the controller as the objective function to be minimized , rather than its worst-case performance, as the worst-case objective funct ion usually leads to rather conservative designs. Then it is shown that a p roperty from statistical learning theory known as uniform convergence of em pirical means (UCEM) plays an important role in allowing us to construct ef ficient randomized algorithms for a wide variety of controller synthesis pr oblems. In particular, whenever the UCEM property holds, there exists an ef ficient (i.e., polynomial-time) randomized' algorithm. Using very recent re sults in statistical learning theory, it is shown that the UCEM property ho lds in several problems such as robust stabilization and weighted H2/Hinfin ity-norm minimization. Hence it is possible to solve such problems efficien tly using randomized algorithms.