Solving generic parametric linear matrix inequalities
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909754158219264 |
|---|---|
| author | Naldi, Simone Din, Mohab Safey El Taylor, Adrien Wang, Weijia |
| author_facet | Naldi, Simone Din, Mohab Safey El Taylor, Adrien Wang, Weijia |
| contents | We consider linear matrix inequalities (LMIs) $A = A_0 + x_1 A_1 + ... + x_n A_n \succeq 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 $Φ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_01487 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving generic parametric linear matrix inequalities Naldi, Simone Din, Mohab Safey El Taylor, Adrien Wang, Weijia Symbolic Computation Algebraic Geometry We consider linear matrix inequalities (LMIs) $A = A_0 + x_1 A_1 + ... + x_n A_n \succeq 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 $Φ$ 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. |
| title | Solving generic parametric linear matrix inequalities |
| topic | Symbolic Computation Algebraic Geometry |
| url | https://arxiv.org/abs/2503.01487 |