Solving generic parametric linear matrix inequalities
Résumé
We consider linear matrix inequalities (LMIs) A = A_0 + x_1A_1 + ... + x_nA_n ⪰ 0 with the A_i's being m×m symmetric matrices, with entries in a ring R. When R = ℝ, the feasibility problem consists in deciding whether the x_i's can be instantiated to obtain a positive semidefinite matrix. When R = ℚ[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 Φ 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.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|---|
| Licence |
