- at ICCOPT II and MOPTA-07, August 12-17/06. McMaster Univ. with Hua Wei.
- Abstract: 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 {\em hard instances} of \SDP\!. In this paper, we introduce a procedure for generating hard instances of \SDP\!. We then introduce two {\em measures of hardness} and illustrate empirically that these measures correlate well with the {\em complementarity nullity} (the dimension of the common nullspace of primal-dual optimal pairs), as well as with the asymptotic local convergence rate and the number of iterations required to obtain optimal solutions to a specified accuracy. %Our numerical tests show %that, in general, a larger the complementarity gap the slower the %local convergence rate is, and thus the more iteration numbers it takes. In addition, our numerical tests show that no correlation exists between the complementarity nullity and recently introduced geometrical measures or with Renegar's condition number. We include tests on the \SDPLIB problem set.