On avoiding vertexization of robustness problems: the approximate feasibility concept

For a large class of robustness problems with uncertain parameter vector q confined to a box Q, there are many papers providing results along the following lines. The desired performance specification is robustly satisfied for all q [member of] Q if and only if it is satisfied at each vertex [q.sup.i] of Q. Since the number of vertices of Q explodes combinatorically with the dimension of q, the computation associated with the implementation of such results is often intractable. The main point of this note is to introduce a new approach to such problems aimed at alleviation of this computational complexity problem. To this end, the notion of approximate feasibility is introduced, and the theory which follows from this definition is vertex-free. Index Terms--Computational complexity, convex optimization, Monte Carlo methods, robustness analysis and design.