This paper gives a new procedure for robustness analysis of linear time-invariant (LTI) systems whose state space coefficient matrices depend polynomially on multivariate uncertain parameters. By means of dual linear matrix inequalities (LMIs) that characterize performance of certain LTI systems, we firstly reduce these analysis problems into polynomial matrix inequality (PMI) problems. However, these PMI problems are non-convex and hence computationally intractable in general. To get around this difficulty, we construct a sequence of LMI relaxation problems via a simple idea of linearization. In addition, we derive a rank condition on the LMI solution under which the exactness of the analysis result is guaranteed. From the LMI solution satisfying the rank condition, we can easily extract the worst case parameters.