Linear Matrix Inequalities, Positivstellensätze and Coin Tossing

Abstract: 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 semialgebraic subset of R^g. Given a spectrahedron S_L, the matrix cube problem of Ben-Tal and Nemirovskii asks for the biggest cube [-r,r]^g included in S_L. We solve a relaxation of this problem based on “matricial’’ spectrahedra. The key to this is complete positivity and real algebraic geometry. To estimate the error inherent in the matricial relaxation we employ probabilistic methods and an old result of Rev. Simmons on flipping biased coins.