# Strict complementary slackness for semidefinite programs with strong duality

By a theorem of Goldman and Tucker it is known that if a linear program (LP) has a finite valued optimal solution, then there is an optimal primal/dual pair $(x,z)$ satisfying not only complementary slackness (i.e. $x_iz_i=0$), but also strict complementary slackness (i.e. exactly one of $x_i$ and $z_i$ vanishs).

It is known that this property does not carry over to semidefinite programs (SDP). This means, if $(X,Z)$ is an optimal primal/dual pair of an SDP, where $X,Z\in\Bbb R^{n\times n}$ are symmetric positive semi-definite matrices, then we have complementarity (i.e. $XZ=0$), but in general no strict complementarity $\def\rank{\mathrm{rank}}\rank(X)+\rank(Z)=n$.

Now, I am especially interested in SDPs with finite valued optimal solutions and zero duality gap. Is there anything more we can say about strict complementary slackness in the case of strong duality? I actually have never seen an example where it fails, i.e. an example with above properties where all optimal primal/dual pairs $(X,Z)$ lack strict complementarity.

Most of my knowledge about strict complementarity comes from [1] where it is shown that it is a generic property (holds for almost all SDPs in a precise sense). Besides this, strict complementarity was mostly assumed to prove other properties.

Studying certain semidefinite programs arising in spectral graph theory, I discovered a semi-definite primal/dual pair satisfying strong duality but not strict complementarity.

Let $$E=\{12,23,34\}$$ (the edge set of the path graph $$P_3$$) and $$E^{ij}:=(\mathbf e_i-\mathbf e_j)^\top(\mathbf e_i-\mathbf e_j)$$. We use the inner product $$\def\<{\langle}\def\>{\rangle}\:=\mathrm{tr}(XY)$$ on the space of symmetric matrices $$\mathbf S^n$$.

$$\llap{\mathrm{(P)}\qquad} \boxed{\begin{array}{rlr} p^*=\max & \sum_{ij\in E} w_{ij} \\ \mathrm{s.t.} & I-\sum_{ij\in E} w_{ij}E^{ij} \succeq0 \\ & w_{ij}\ge 0,\quad ij\in E \end{array}}$$

$$\llap{\mathrm{(D)}\qquad} \boxed{\begin{array}{rlr} d^*=\min & \mathrm{tr}(X) \\ \mathrm{s.t.} & \\ge 1,\quad ij\in E \\ & X\succeq 0 \end{array}}$$

The common optimal value is $$p^*=d^*=1$$, obtained for

$$w_{12}=w_{34}=\frac12,\quad w_{23}=0,$$

$$X=\frac14\begin{pmatrix} \phantom+1 & -1 & \phantom+1 & -1 \\ -1 & \phantom+1 & -1 & \phantom+1 \\ \phantom+1 & -1 & \phantom+1 & -1 \\ -1 & \phantom+1 & -1 & \phantom+1 \end{pmatrix} = \frac14 (\phantom+1,-1,\phantom+1,-1)^\top(\phantom+1,-1,\phantom+1,-1).$$

Both are the unique solutions of their respective problem (this can easily be seen when interpreting $$\mathrm{(D)}$$ as an embedding problem, but I will leave this out here). As seen, the dual positive semi-definite matrix $$X$$ has rank $$1$$. However, the corresponding matrix

$$Z:=I-\sum_{ij\in E} w_{ij}E^{ij} = \frac12 \begin{pmatrix} 1 & 1 & & \\ 1 & 1 & & \\ & & 1 & 1 \\ & & 1 & 1 \end{pmatrix}$$

is of rank $$2$$. Hence $$\mathrm{rank}(X)+\mathrm{rank}(Z)=3<4$$ and strict complementarity is not satisfied.

Take the SDP program

\begin{align*} \min~& x_3\\ s.t.~& X = \begin{bmatrix} x_1 & x_2 & 0 & 0 \\ x_2 & 0 & 0 & 0 \\ 0 & 0 & x_2 & 0 \\ 0 & 0 & 0 & x_3-2 \\ \end{bmatrix}\succeq \mathbf{0}\\ &x_1,~x_2,~x_3\in\mathbf{R} \end{align*} Its dual can be written as follows (see below why). \begin{align*} \max~& 2z_{44}\\ s.t.~& Z= \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & a^2+\Delta^2& 0 & a \\ 0 & 0 & 0 & 0 \\ 0 & a & 0 & 1 \\ \end{bmatrix}\\ &Z\succeq 0 \end{align*}

Now notice that any feasible solution $$\mathbf{x}$$ of the primal satisfies $$x_2=0$$ because of the zero situated at position $$(2,2)$$; recall that any SDP matrix $$A$$ such that $$A_{ii}=0$$ has only zeros on row and column $$i$$.

Now check that $$X$$ and $$Z$$ share the eigenvector $$\left[\begin{smallmatrix} 0 & 0 & 1 & 0 \\ \end{smallmatrix} \right]^\top$$ with eigenvalue 0, which actually answers the question. No linear combination of the rows of $$X$$ and $$Z$$ that can be equal to this eigenvector, i.e., the rows of $$X$$ and $$Z$$ do not cover the whole space $$\implies rank(X)+rank(Z).

The only detail that remains to be filled is to show that the above expression of the dual is correct. Any feasible $$Z$$ satisfies $$z_{11}=0$$ because the coefficient of $$x_1$$ is zero in the primal objective function. This forces row 1 and column 1 of $$Z$$ to have only zeros. The dual constraint corresponding to $$x_2$$ is $$2z_{12}+z_{33}=0$$; since $$z_{12}=0$$, we have $$z_{13}=0$$. The dual constraint corresponding to $$x_3$$ imposes $$z_4=1$$. There is no constraint on $$z_{24}=a$$; $$z_{22}$$ needs to be greater than or equal to $$a^2$$ so as to have a non-negative principal minor corresponding to rows/columns 2 and 4; we can write $$z_{22}=a^2+\Delta^2$$. Finally, both programs have objective value 2.