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 exists 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. And, 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. In this paper, we introduce a procedure for generating hard instances of SDP. We then introduce two measures of hardness and illustrate empirically that these measures correlate well with the size of the gap in strict complementarity as well as with the asymptotic local convergence rate, and also with the number of iterations required to obtain optimal solutions to a specified accuracy. In addition, our numerical tests show that no correlation exists between the complementarity gaps and recently introduced geometrical measures or with Renegar’s condition number. We include tests on the SDPLIB problem set.
Citation
Department of Combinatorics & Optimization University of Waterloo Waterloo, Ontario N2L 3G1, Canada Research Report CORR 2006-01