##
Complementarity and Nondegeneracy in Semidefinite Programming

###
Farid Alizadeh, Jean-Pierre Haeberly and Michael Overton

Primal and dual nondegeneracy conditions are defined for semidefinite
programming. Given the existence of primal and dual solutions, it is shown
that primal nondegeneracy implies a unique dual solution and that dual
nondegeneracy implies a unique primal solution. The converses hold if
strict complementarity is assumed. Primal and dual nondegeneracy assumptions
do not imply strict complementarity, as they do in LP. The primal and dual
nondegeneracy assumptions imply a range of possible ranks for primal and
dual solutions $X$ and $Z$. This is in contrast with LP where nondegeneracy
assumptions exactly determine the number of variables which are zero.
It is shown that primal and dual nondegeneracy and strict complementarity
all hold generically. Numerical experiments suggest probability distributions
for the ranks of $X$ and $Z$ which are consistent with the nondegeneracy
conditions.