Generating and measuring instances of hard semidefinite programs

Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal–dual strictly complementary optimal solution pair. On the other hand, there exist Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if a constraint qualification, e.g., Slater’s condition (strict feasibility) holds. Measures of strict feasibility, also called distance to infeasibility, have been used in complexity analysis, and, it is known that (near) loss of strict feasibility results in numerical difficulties. In addition, there exist SDP problems which have a zero duality gap but no strict complementary primal–dual optimal solution. We refer to these problems as hard instances of SDP. The assumption of strict complementarity is essential for asymptotic superlinear and quadratic rate convergence proofs. In this paper, we introduce a procedure for generating hard instances of SDP with a specified complementarity nullity (the dimension of the common nullspace of primal–dual optimal pairs). We then show, empirically, that the complementarity nullity correlates well with the observed local convergence rate and the number of iterations required to obtain optimal solutions to a specified accuracy, i.e., we show, even when Slater’s condition holds, that the loss of strict complementarity results in numerical difficulties. We include two new measures of hardness that correlate well with the complementarity nullity.