Duality theory is a central concept in semidefinite programming (SDP), just like it is in linear programming, since in optimization algorithms a dual solution serves as a certificate of optimality. However, in SDP, unlike in LP, ``pathological'' phenomena occur: nonattainment of the optimal value, and positive duality gaps between the primal and dual problems. This research was motivated by the curious similarity of pathological SDP instances appearing in the literature. We prove an exact, combinatorial type characterization of badly behaved semidefinite systems, ie., show that ``all bad SDPs look the same''. We also prove that all badly behaved semidefinite systems can be reduced to a minimal such system with just one variable, and two by two matrices in a well defined sense. Our characterizations imply that recognizing badly behaved semidefinite systems is in NP and co-NP in the real number model of computing. For general conic linear programs we give a geometric ``sandwich theorem'' to characterize well- and badly behaved systems; this result yields an exact characterization for the class of nice cones, of which the SDP result is a special case. |