A hierarchy of polyhedral approximations of robust semidefinite programs

Robust semidefinite programs are NP-hard in general. In contrast, robust linear programs admit equivalent reformulations as finite-dimensional convex programs provided that the problem data are parameterized affinely in the uncertain parameters; and that the underlying uncertainty set is described by an affine slice of a proper cone. In this paper, we propose a hierarchy of inner and outer polyhedral approximations to the positive semidefinite (PSD) cone that are exact in the limit. We apply these polyhedral approximations to the PSD cone to obtain a computationally tractable hierarchy of inner and outer approximations to the robust semidefinite program, which are similarly exact in the limit. We investigate the strengths and limitations of the proposed approach with a detailed numerical study.