Optimization Online


On positive duality gaps in semidefinite programming

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

Abstract: We study semidefinite programs (SDPs) with positive duality gaps, i.e., different optimal values in the primal and dual problems. the primal and dual problems differ. These SDPs are considered extremely pathological, they are often unsolvable, and they also serve as models of more general pathological convex programs. We first fully characterize two variable SDPs with positive gaps: we transform them into a standard form which makes the positive gap easy to recognize. The transformation is very simple, as it mostly uses elementary row operations coming from Gaussian elimination. We next show that the two variable case sheds light on larger SDPs with positive gaps: we present SDPs in any dimension in which the positive gap is certified by the same structure as in the two variable case. We analyze an important parameter, the {\em singularity degree} of the duals of our SDPs and show that it is the largest that permits a positive gap. We complete the paper by generating a library of difficult SDPs with positive gaps (some of these SDPs have only two variables), and a computational study.

Keywords: semidefinite programming; duality gaps

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

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 06/27/2018
Entry Accepted: 07/03/2018
Entry Last Modified: 06/27/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