- Bad semidefinite programs: they all look the same Gabor Pataki (gaborunc.edu) Abstract: 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. Keywords: Semidefinite programming; duality; exact characterizations Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Technical report, Department of Statistics and Operations Research, University of North Carolina at Chapel Hill Download: [PDF]Entry Submitted: 11/12/2010Entry Accepted: 11/12/2010Entry Last Modified: 05/14/2014Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.