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× n interval matrix U_ρ=\, |Aᵢⱼ-A^*ᵢⱼ|≤ρ Cᵢⱼ\, one can build a computable lower bound, accurate within the factor π 2, on the supremum of those ρ for which all instances of U_ρ 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.