-
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.