Time domain validation of structured uncertainty model sets

We consider a time domain model validation problem with respect to structured uncertainty model sets. This problem has been first investigated in [3], where a necessary and sufficient condition in terms of bilinear matrix inequalities (BMIs) was derived, and related implementation difficulties were discussed. In this paper, we first analyze the computational complexity of the problem, for which we provide some NP-hardness results. These results help explain the implementation difficulties mentioned in [3]. Next, we present a real μ characterization of the problem. This characterization makes it possible to analyze the validation problem in a systematic manner, by using the available upper and lower bounds, in real μ computation [9]. Moreover, we also consider certain relaxations of the problem and provide several easily implementable randomized algorithms [1].