Calculus of unbounded spectrahedral shadows and their polyhedral approximation

The present thesis deals with the polyhedral approximation and calculus of spectrahedral shadows that are not necessarily bounded. These sets are the images of the feasible regions of semidefinite programs under linear transformations. Spectrahedral shadows contain polyhedral sets as a proper subclass. Therefore, the method of polyhedral approximation is a useful device to approximately describe them using members of the same class with a simpler structure. In the first part we develop a calculus for spectrahedral shadows. Besides showing their closedness under numerous set operations, we derive explicit descriptions of the resulting sets as spectrahedral shadows. Special attention is paid to operations that result in unbounded sets, such as the polar cone, conical hull and recession cone. The second part is dedicated to the approximation of compact spectrahedral shadows with respect to the Hausdorff distance. We present two algorithms for the computation of polyhedral approximations of such sets. Convergence as well as correctness of both algorithms are proved. As a supplementary tool we also present an algorithm that generates points from the relative interior of a spectrahedral shadow and computes its affine hull. Finally, we investigate the limits of polyhedral approximation in the Hausdorff distance in general and, extending known results, characterize the sets that admit such approximations. In the last part we develop concepts and tools for the approximation of spectrahedral shadows that are compatible with unboundedness. We present two notions of polyhedral approximation and show that sequences of approximations converge to the true set if the approximation errors diminish. In combination with algorithms for their computation we develop an algorithm for the polyhedral approximation of recession cones of spectrahedral shadows. Finiteness and correctness of all algorithms are proved and properties of the approximation concepts are investigated.