Optimization Online


Bad semidefinite programs with short proofs, and the closedness of the linear image of the semidefinite cone

Gabor Pataki (gabor***at***unc.edu)

Abstract: Semidefinite programs (SDPs) -- some of the most useful and pervasive optimization problems of the last few decades -- often behave pathologically: the optimal values of the primal and dual problems may differ and may not be attained. Such SDPs are theoretically interesting and often impossible to solve. Yet, the pathological SDPs in the literature look strikingly similar, and to explain why, our recent paper ("Bad semidefinite programs: they all look the same", SIAM J. Opt, 2017) characterized pathological semidefinite systems by certain {\em excluded matrices}, which are easy to spot in all published examples. Here we give short, and elementary proofs of these results using mostly techniques from elementary linear algebra. Our main tool is a standard (canonical) form of semidefinite systems, from which their pathological behavior is easy to verify. The standard form is constructed in a surprisingly simple manner, using mostly elementary row operations inherited from Gaussian elimination. As a byproduct, we prove that any linear map acting on symmetric matrices can be brought into a standard form; this standard form allows us to easily check whether the image of the semidefinite cone under the given linear map is closed.

Keywords: semidefinite programming; duality; duality gap; duality; pathological semidefinite programs; closedness of the linear image of the semidefinite cone

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 05/19/2017
Entry Accepted: 05/19/2017
Entry Last Modified: 06/11/2018

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