Exact Algorithms for Linear Matrix Inequalities
Exact Algorithms for Linear Matrix Inequalities
Let $A(x) = A_0+x_1A_1+\cdots+x_nA_n$ be a linear matrix, or pencil, generated by given symmetric matrices $A_0,A_1,\ldots,A_n$ of size $m$ with rational entries. The set of real vectors $x$ such that the pencil is positive semidefinite is a convex semialgebraic set called spectrahedron, described by a linear matrix inequality. We design …