Georgia Institute of Technology College of Sciences

Given a tuple A=(A_1,...,A_g) of symmetric matrices of the same size, the affine linear matrix polynomial L(x):=I-\sum A_j x_j is a monic linear pencil. The solution set S_L of the corresponding linear matrix inequality, consisting of those x in R^g for which L(x) is positive semidefinite (PsD), is called a spectrahedron. It is a convex basic closed semialgebraic subset of R^g. Given a spectrahedron S_L, the matrix cube problem of Nemirovskii asks for the biggest cube [-r,r]^g included in S_L. We solve a relaxation of this problem based on``matricial’’ spectrahedra and estimate the error inherent in this relaxation. The talk is based on joint work with B. Helton, S. McCullough and M. Schweighofer.