turkmath.org

Linear matrix inequalities (LMIs) are common in many areas: control theory, mathematical optimization, statistics, etc. Given real symmetric matrices $A_0, . . . , A_g$ consider the linear matrix inequality $L(x) = A_0 + A_1x_1 + · · · + A_gx_g \succcurlyeq0$, where $ \succcurlyeq0$ means positive semidefinite. The solutions set to this LMI is called a spectrahedron and is a convex semialgebraic subset of $\mathbb{R}^g$. We study the question whether inclusion holds between two spectrahedra. Most of our results concern the case where the included spectrahedron is a hypercube, an NP-hard problem introduced and studied by Ben-Tal and Nemirovskii, who identified a tractable relaxation of the original problem. This relaxation is obtained by considering the inclusion problem for the corresponding free spectrahedra. A central issue is: how close is spectrahedral inclusion to its free relaxation? Clearly, inclusion of free spectrahedra implies the inclusion of the corresponding spectrahedra. This talk treats the converse. We show inclusion of spectrahedra implies the inclusion of the corresponding free spectrahedra up to a scaling factor $t$. For the cube, we compute the tight bound $t_{cube}$ with an elegant scalar optimization formula. When the size of the $A$’s is $d\times d$ and $d$ is even, then $t_{cube} = \sqrt{\pi}\;\Gamma(\frac{1}{2}+\frac{d}{4})\Gamma(1+\frac{d}{4})^{-1}$. Critical to our proofs is dilating a tuple of matrices $X$ lying in a free spectrahedron $S$ to a commuting tuple \tilde{X} of self-adjoint operators in $tS$.
This is based on joint work with Bill Helton, Scott McCullough and Markus Schweighofer.