On positive duality gaps in semidefinite programming

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.

Article

Download

View PDF