Solving generic parametric linear matrix inequalities

Abstract

We consider linear matrix inequalities (LMIs) $A=A_0+x_1{A}_1+...+x_n{A}_n⪰0$ with the $A_i$'s being $m\times m$ symmetric matrices, with entries in a ring $\mathcal{R}$. When $\mathcal{R}=\mathbb{R}$, the feasibility problem consists in deciding whether the $x_i$'s can be instantiated to obtain a positive semidefinite matrix. When $\mathcal{R}=\mathbb{Q}[y_1,...,y_t]$, the problem asks for a formula on the parameters $y_1,...,y_t$, which describes the values of the parameters for which the specialized LMI is feasible. This problem can be solved using general quantifier elimination algorithms, with a complexity that is exponential in n. In this work, we leverage the LMI structure of the problem to design an algorithm that computes a formula $\hat{I}¦$ describing a dense subset of the feasible region of parameters, under genericity assumptions. The complexity of this algorithm is exponential in n, m and t but becomes polynomial in $n$ when $m$ and $t$ are fixed. We apply the algorithm to a parametric sum-of-squares problem and to the convergence analyses of certain first-order optimization methods, which are both known to be equivalent to the feasibility of certain parametric LMIs, hence demonstrating its practical interest.