Fast Algorithms for Exact and Approximate Feasibility of Uncertain LMIs

We discuss fast randomized algorithms for determining an admissible solution for robust linear matrix inequalities (LMIs) of the form F(x, Δ)⩽0, where x is the optimization variable and Δ is the uncertainty, which belongs to a given set Δ. The proposed algorithm is based on uncertainty randomization: it finds a solution in a finite number of iterations with probability one, if a strong feasibility condition holds. Otherwise, it computes a candidate 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