  


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 coNP 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 wellbehaved semidefinite systems we can choose optimal dual matrices with a predefined blockdiagonal 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 (Semidefinite 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/2010 Modify/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  