On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty

We present efficiently verifiable sufficient conditions for the validity of specific NP-hard semi-infinite systems of linear matrix inequalities (LMIs) arising from LMIs with uncertain data and demonstrate that these conditions are tight up to an absolute constant factor. In particular, we prove that given an n x n interval matrix U-rho = {A \ \A(ij)-A*(ij)\ less than or equal to rhoC(ij)}, one can build a computable lower bound, accurate within the factor pi/2, on the supremum of those rho for which all instances of U-rho share a common quadratic Lyapunov function. We then obtain a similar result for the problem of quadratic Lyapunov stability synthesis. Finally, we apply our techniques to the problem of maximizing a homogeneous polynomial of degree 3 over the unit cube.