We call a conic linear system (P) Ax \leq_K b {\em well behaved}, if for all $c$ objective functions the value of \sup \, \{ \, \la c, x \ra \, | \, Ax \leq_K b \, \} and of its dual agree, and the latter is attained, when finite. We call $(P)$ {\em badly behaved,} when not well behaved. We give simple conditions for a conic system to be well- and badly behaved, and exactly characterize such systems over a broad and important class of cones, called {\em nice} cones. We characterize badly behaved semidefinite systems via certain excluded matrices, which are easy to spot in all such systems that appear in the literature. We show how to reformulate semidefinite systems in a certain standard form. The reformulation allows us 1) to prove that the question ``Is a semidefinite system well behaved?'' is in NP \cap co-NP in the real number model of computing, and to verify the status of a system in polynomial time, by elementary arguments; 2) to deduce that in well-behaved semidefinite systems we can choose optimal dual matrices with a predefined block-diagonal structure for {\em all} objective functions; 3) to systematically generate all well behaved systems by a simple algorithm. Our main tool is one of our recent results on the closedness of the linear image of a closed, convex cone.
Citation
Technical report, Department of Statistics and Operations Research, University of North Carolina at Chapel Hill