and 
satisfying the cone inequalities,
we must consider the three components separately:
satisfy the complementarity condition if
, i.e., the matrix product 
,
and the strict complementarity condition if, in addition, 
is strictly positive definite. Alternatively, let
denote the eigenvalues of 
and 
denote the eigenvalues of 
.
Then satisfy the complementarity condition if,
for all i, the product 
is zero, and the
strict complementarity condition if, for all i, exactly one of
the pair 
and 
is zero.
for brevity, and likewise 
:
x,z satisfy the complementarity condition if 
,
and the strict complementarity condition if, in addition,
for each block i, exactly one of the pair
is zero, and exactly one of the pair
is zero. Consequently, for each block, either
the vectors 
and 
are both nonzero boundary points, or
one is zero and the other is in the interior of the quadratic cone.
satisfy the complementarity
condition if 
is zero, and the
strict complementarity condition if,
for each i, exactly one of the pair 
and 
is zero.
where 
, 
and 
are structures as before,
and tol is a tolerance
This routine first checks the global complementarity condition
.
If violated, it quits immediately with 
.
Otherwise, it checks strict complementarity block by block,
using the square root of tol to determine
whether the relevant quantities are sufficiently close to zero.
The output vectors v.s and v.q and
scalar v.l indicate the result for each block, with a
value of 1 if strict complementarity holds in that block, and 0 if it
is violated. The summary flag strictc is then set to the minimum
value of v.s, v.q and v.l.
The SDPpack routines are generally able to solve problems for which strict
complementarity fails to hold, but the convergence rate is markedly slower,
and generally less accuracy is achieved.
Note the use of the square root of the tolerance in scomp.m,
since if strict complementarity is violated, usually quantities which
are mathematically zero are not reduced to very small values.
The reason for the square root is as follows. Suppose that an
SDP where strict complementarity fails to hold is approximately
solved, obtaining computed solutions and with
. This implies that the pairwise computed
eigenvalue products satisfy 
.
For an index i for which strict complementarity
holds, one computed eigenvalue of the pair is typically small
(about the same order of magnitude as 
) and the other is not.
For an index for which strict complementarity
fails, both computed eigenvalues in the pair typically have order
of magnitude
only 
, even though both are zero at the true solution.
If 
returns 
,
check the output parameter v
to identify which blocks are relevant, and use the routines blkeig
(for the semidefinite part) and qcpos (for the quadratic part)
to investigate further (see below). Consider also experimenting with
different values for tol.
An example of a simple SDP for which strict complementarity fails is given in the sample Matlab session in Appendix B. The ladder2 Steiner tree example in Appendix C is an example of a QCLP for which strict complementarity fails.
