Optimization Online


Bad semidefinite programs: they all look the same

Gabor Pataki (gabor***at***unc.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/2010
Entry Accepted: 11/12/2010
Entry Last Modified: 05/14/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society