Stochastic algorithms for exact and approximate feasibility of robust LMIs

In this note, we discuss fast randomized algorithms for determining an admissible solution for robust linear matrix inequalities (LMIs) of the form F(x, Delta) less than or equal to 0, where 0 is the optimization variable and Delta is the uncertainty, which belongs to a given set Delta. The proposed algorithms are based on uncertainty randomization: the first algorithm finds a robust solution in a finite number of iterations with probability one, if a strong feasibility condition holds. In case no robust solution exists, the second algorithm computes an approximate solution which minimizes the expected value of a suitably selected feasibility indicator function. The theory is illustrated by examples of application to uncertain linear inequalities and quadratic stability of interval matrices.